树形网络子图中心度的研究

树形网络子图中心度的研究 树形网络子图中心度的研究,信息科学, 李发旭 约2804字 [摘要]研究具有树形网络拓扑结构的子图中心度,通过仿真分析得到节点数固定的树形网络拓扑结构的子图中心度与网络拓扑结构的最大度之间的关系,以及在度序列相同的情况下不同拓扑结构对子图中心度的影响,仿真结果显示这种更能清楚的显示网络的局部聚类和无标度特性。 [关键词]子图中心度树形网络仿真局部聚类无标度特性 中图分类号:TP3文献标识码:A文章编号:1671-7597(2009)0920095-01 一、引言 复杂网络是复杂系统的高度抽象,它充满着自然界、工程界和社会界,如细胞中的新陈代谢网络、科研合作网络、经贸网络、互联网以及电力网等等[1]。这些实际网络都具有共同的全局结构特征,如小世界、无标度和聚类特性,但具有相似的全局结构特性的网络却可能具有非常不同的局部结构特征。因此,理解网络的局部拓扑结构及其产生机理是非常重要的。 如果 ,说图是图的子图。子图描绘了从局部层次刻画一个给定网络的相互连接的特定模式。每一个实际网络都是它的一组特定的子图刻画的,然而,并不是所有的子图都具有相同的重要性。不同类型的复杂网络通常需要使用不同的中心度指标来进行刻画,典型的中心度指标包括度(Degree Centrality)、紧密度(Closeness Centrality)、介数(Betweenness Centrality)、特征向量中心度指标[2](Eigenvector Centrality)和子图中心度等指标(Subgraph Centrality)。 在复杂网络中存在大量的树状拓扑结构,如星形网络和路网。因此,研究树形网络的子图中心度具有广泛的代性,有助于识别网络的典型局部特征,并从局部结构上来理解复杂网络的设计原理。本文主要研究的问题是:节点数固定的树形网络拓扑结构的平均子图中心度与网络拓扑结构的最大度之间的存在何种联系;在度序列相同的情况下不同拓扑结构对子图中心度的影响。本文主要提出了通过研究子图中心度的特性来研究网络拓扑结构的局部特性的方法,并给出了仿真的结果。 二、子图中心度[2] 子图中心度(Subgraph Centrality,简记SC)刻画了网络的局部特性,区分了网络中的节点在不同子图中的的参与情况,根据每个节点在不同子图中的参与情况将其排序给出对网络所做的贡献。子图中心度是用起始和终止于该节点的闭迹的数量来刻画网络中的节点在不同子图中的参与的一种方法。每个闭迹都是一个连通子图,子图中心度就是统计一个节点在网络中的不同连通子图中参与的次数。 令是阶简单图,这个图的谱就是图的邻接矩阵的特征值的集合,图的谱的密度其实就是邻接矩阵特征值的密度,通过谱距直接给出它的拓扑性质。比如,网络图中起止点是的长度为的闭迹个数,就是谱距 ,可以写成如下的形式: 我们定义节点的子图中心度就是在网络图中起止点为节点的不同长度闭迹的总和。这个总和包括所有子图中平凡和非平凡的闭迹。网络中随着节点的闭迹长度的增加,对中心度的影响将会减小,闭迹的贡献度也将随着减小。网络中节点的子图中心度定义为: 令是邻接矩阵的主特征值,对于任意的非负整数和节点 ,有 ,对(2)公式,每一项都是非负的,并且收敛于 三、仿真分析 在仿真分析中,通过对所有10个节点9条边的树形图进行的分析,得到了相关的研究数据。通过对仿真数据的分析得到了节点的度序列与平均子图中心度之间的关系图(如图1所示)。通过仿真图可以发现树形拓扑结构的最大度和平均子图中心度之间存在线性关系,即树形拓 扑结构的最大度越大,网络的平均子图中心度也越大。从网络的拓扑结构看,如果网络中度较大的节点比较少,而度较小的节点很多时,则这种节点度分布的无标度性导致了该网络的子图中心度较大。这也进一步说明了度大的节点参与到了更多的子图中,该节点对网络的贡献值较大。 为了更好的说明不同的拓扑结构和其最大度之间的关系,这里选取几种典型的树形拓扑结构(如图2所示)进行分析,并得到了相关数据(如表 1所示)。以上数据显示星形网络的最大度最大,其平均子图中心度也最大;而路中的最大度最小,其子图中心度也最小。 另外,通过仿真分析发现节点的度序列相同情况下,出现了平均子图中心度不同的情况,这种情况说明虽然节点的度序列相同,但是若节点连接的邻居节点的度大时其平均子图中心度也相对较大,而节点连接的邻居节点的度小时其平均子图中心度也相对较小。例如在下面的两种拓扑结构中,我们观察到这两个图中移除节点 后,属于同构的图,通过公式(4)计算得到两图的平均子图中心度。但是不移除节点 后,将其连接到其它节点上如图2所示,则两图的度序列分布相同,但图的平均子图中心度不相同。图3(a)的平均子图中心度,图3(b)的平均子图中心度 。在两种图中节点 都连接到了度为2的节点 上,但在图3(a)中节点又连接到了度为2的节点 上;而在图3(b)中节点 又连接到了度为7的节点上。图3(a)比图3(b)中节点 间接连接的节点的度较高,这种间接的影响导致了节点 在图3(a)中的子图中心度小于图3(b)中子图中心度,因此图3(a)的平均子图中心度小于图3(b)的平均子图中心度。 图3两种节点度序列相同情况下的拓扑结构 四、结论 本文通过研究平均子图中心度的方法来分析节点数和边数固定的树形网络拓扑结构的局部特性,重点分析了节点的度分布和平均子图中心度之间的关系。通过仿真分析我们观察到树形拓扑结构的最大度和平均子图中心度之间存在线性关系,即树形拓扑结构的最大度越大,网络的平均子图中心度也越大。在度序列相同的不同拓扑结构中,若节点连接的邻居节点的度大时其平均子图中心度也相对较大,而节点连接的邻居节点的度小时其平均子图中心度也相对较小,仿真结果显示这种方法更能清楚的显示网络的局部聚类和无标度特性。 基金项目:国家自然基金项目资助(No.60863006) 参考文献: [1]Albert R,Barabási A.Statistical mechanics of complex network.Reviews of Modern Physics[J].2002,74(1):47-97. [2]E.Estrada,J.A.Rodriguez-Velazquez,A Juan,Subgraph Centrality in Complex Network. Physical Review E72[J].046105(2005). [3]汪小帆、李翔、陈关荣,复杂网络理论及其应用[M].北京:清华大学出版社,2006. [4]周涛、柏文洁、汪秉宏等,复杂网络研究概述[J].物理,2005(1):31-36. 作者简介: 李发旭,女,青海湟中人,硕士,主要研究方向:复杂网络,理论计算机。