复杂网络中新指标潜数的设计方案与分析

1、复杂网络中新指标 -潜数的设计与分析任维雅 1摘要： 依据度信息和节点连接关系构造出复杂网络的新指标-潜数，阐述了节点的先导潜数和后导潜数对网络节点影响力的刻画作用，通过实验分析了先 导潜数、后导潜数、网络潜数与网络其他基本指标的关系，以及先导潜数的 分布特征。实验展示了基于先导潜数和基于度的两种节点删除策略对网络摧 毁程度的作用效果，反映了基于先导潜数删除策略的优越性。最后计算了 BA 网络、 WS 网络、 NW 网络的网络潜数，结果表明网络潜数可作为网络中特有 的稳定网络特征之一。关键词： 复杂网络；影响力；指标；潜数中图分类号： O231 文献标志码： ADesign and Analy

2、sis of Complex network sNew Index-Laner1RenWei-ya1(1College of Information System and Management, National University of DefenseTechnology,Changsha,410073,ChinaAbstract : A new complex network sindex Laner is constructed based on degree information andnodes connection.The paper explained the network

3、s nodes influence which described by ex-lanner and post-lanner. Through experiments ， we analyzed the relationship between ex-lanner ， post-lanner ， network-lanner and other network s basic index ， and we analyzedthe ex-lanners distribution character as well.Experiments reflected the network been de

4、structed effect under two node delete strategies-node degree based and node ex-lanner based, the result illuminated the superiority of ex-lanner based strategy. Finally we computed the BA network,WS network and NW networks network-lanner,and the outcomesrevealed thenetwork- lanner has been one of th

5、e own steady network character in networks.Keywords: Complex network。 influence。 Index。 Lanner0 引言复杂网络的小世界特征 0 和无标度性 质2的发现，使得复杂网络的的研究进入 了一个新的高潮，经历十余年的发展，复 杂网络已经逐步走向了成熟并越来越引人 注目，甚至被一些学者称为“网络的新科 学” 3。复杂网络的一系列指标逐渐帮助 人们揭开它神秘的面纱。多数复杂网络的 指标都是基于网络连接图进行构造，节点 和节点之间可以通过不同的路径到达，而 网络中一个节点也不可避免地和周围的节 点具有相互影响关系。本

6、文基于复杂网络 中节点相互连接关系构造了新的统计指 标，实验证明依据潜数的攻击策略比依据 度的攻击策略对网络的毁伤性更大。1潜数1.1潜数定义潜数描述的是节点之间的相互关系， 假定在一个复杂网络中进行信息传递，任 一个节点到达其所有邻居节点的概率都是 该节点度的倒数，于是任意两节点之间存 在一个最大到达概率，定义：1, 一个节点对自身的潜数是0，记为二；2, 节点i到节点j的最大到达概率为节点i对节点j的潜数，记为丨；3, 节点i对网络所有节点的潜数之和 为节点i的先导潜数，记为4, 网络所有节点对节点j的潜数之和为节点j的后导潜数，记为5, 所有节点的先 后）导潜数之和除 以网络节点数目（N

7、为网络的网络潜数， 记为O节点先导潜数的计算过程，实际上是 一个信息从自身出发向外传递的过程，节 点的先导潜数反映的是一个节点对网络中 其他节点的影响力；节点后导潜数的计算 过程，实际上是一个信息从外界输入自身 的过程，节点的后导潜数则反映了网络中 其他节点对某个节点所产生的影响力。潜数和节点之间的最短路径并不相 同，节点i到节点j的潜数为二者的最大 到达概率，而到达概率和节点度又有着直 接关系，所以在最大到达概率路径上并不 等于最短路径。1.2潜数特点通过分析特殊网络 星型网络和环形 网路）发现：在没有孤立节点的网络中， 先导潜数和后导潜数的取值范围分别为：，匚丨。由于概率的累积性，某个节点

8、的先导 潜数受一定局部区域内的节点影响最大。 某节点的先导潜数越小则说明该节点对其 周围节点的影响力越大；某节点的后导潜 数越小，表明其周围节点对该节点的影响 力越小。例如，星型网络中心节点的先导 潜数达到了 1，则说明该节点对网络其余 节点产生了所能产生的最大影响力；同 时，中心节点的后导潜数正比于网络规 模，说明其受到的外界影响力很大，而边 缘节点的后导潜数为1,说明这些节点所受到的影响力已经到达了最小。由于先 后）导潜数的取值范围，易 知在没有孤立节点的网络中，网络的网络 潜数不小于1，网络潜数可以理解为网络 节点的平均影响力或者是平均受影响力。选取复杂网络中几种经典的网络进行 潜数分析

9、，即：BA网络2，WS网络、 NW网络和ER随机图9。分析发现：先导潜数与节点度的关系和网络类型 有关，如在 BA网络中是幕律关系，在 WS网络中是无关的，在 NW网络中是负 线性相关关系；后导潜数与节点度一直呈 正相关关系。实验发现，网络潜数与聚类系数呈负 相关关系，与平均路径长度呈正相关关 系，但网络潜数与同配系数 是无关的。1.2.1先导潜数分布先导潜数的分布和网络类型等因素有 关，如在 BA网络中是 Weibull分布，在 NW 网络中是正态分布， WS网络中当重 连概率p较小时（如0.05服从指数分布 二 的 Weibull分布），当重连概率p较大时（实验表明大于0.1，服从正态分布

10、。在BA网络中先导潜数均有良好的Weibull 分布趋势。图 1 为 m=2, n=1000 其中n为网络规模，m为网络增长时新节 点连接的节点个数）的 BA网络中先导潜 数分布直方图。在 WS网络中，重连概率 p较小时有良好的指数分布趋势。图2为p=0.05，n=1 000的 WS网络中先导潜数 分布直方图。在WS网络中p较大p0.1）时先导 潜数均有良好的正态分布趋势。图3为p=0.2，n=1000时 WS网络中先导潜数分 布直方图。在NW网络中，先导潜数均图1BA网络先导潜数密度直方图,m=2,n=1000图2WS网络先导潜数密度直方图 ，p=0.05,n=1000有良好的正态分布趋势

11、与p无关）。图 4为p=0.2，n=1000时NW 网络中先导潜 数分布直方图。图3 WS网络先导潜数密度直方图,p=0.2,n=1000图4 NW网络先导潜数密度直方图,p=0.2,n=1000以上各网络密度分布的matlab检验曲线都接近直线，说明样本数据较符合分 布假设。1.2.2先 后）导潜数与节点度的相关性先导、后导潜数与节点度的相关系数 （实验平均值 如表1、2。后导潜数普遍与节点度有很好的线性 正相关性；先导潜数则不然，如在WS网络中，先导潜数和度呈现出很弱的相关 性。n=200n=500n=1 000BA网络,m=2-0.7722-0.6166-0.6968BA网络,m=1-0

12、.4869-0.4650-0.482 8WS 网络,p=0.3-0.3319-0.2049-0.2069WS网-0.053 3-0.162 9-0.1345络,p=0.05NW 网络,p=0.2-0.9863-0.9830-0.9857NW网络-0.955 6-0.9669-0.983 5p=0.05ER随机网络-0.950 2-0.953 7-0.958 7表1先导潜数与节点度相关系数n=200n=500n=1 000BA网络,m=20.988 50.992 90.994 5BA网络,m=11.000 01.000 01.000 0WS 网络,p=0.30.865 20.911 50.895

13、 7WS网0.810 60.701 70.710 2络,p=0.05NW 网络,p=0.20.995 30.997 90.999 1NW网络0.973 70.987 30.994 8p=0.05ER随机网络0.984 70.993 60.996 6表2后导潜数与节点度相关系数2复杂网络的潜数分析2.1网络抗毁性分析中的节点删除策略我们往往关心如何以最快的方式摧毁 一个网络，本节依据删除策略逐个删除网络中的节点，并同步计算网络所有连通子 图大小的和，和网络的聚类系数。以网络 所有连通子图的大小和来作为网络被摧毁 程度的评判标准之一，而不是采用最大连 通子图大小，是因为这样可以更好地反映 出网络被

14、摧毁的整体效果。我们采用2种节点删除策略进行对比：方案1,基于节点度依次删除网络中的 节点，即依次去除网络中度最大的节点， 如果度最大的节点不唯一，则随机选取一 个。方案2,基于节点先导潜数 节点影响 力）依次删除网络中的节点，即依次去除 网络中先导潜数最小的节点，如果先导潜 数最小的节点不唯一，则随机选取一个。根据上一小节中先导潜数与度的相关 性，选取二者相关性很低的WS网络（n=500, p=0.2作为实验网路，以反映两种方案的优劣。相比于依据节点度的删除策略，依据 节点影响力的删除策略，使得网络所有连 通子图大小之和下降的更快，网络的聚类 系数也下降的更快，这说明依据节点先导 潜数的删除

15、策略使摧毁网络的效果更好。 即依次删除影响力最大的节点，会使网络 的整体性遭到更快的破坏。网络所有连通子图大小之和与删除步 骤关系如图5。网络聚类系数与删除步骤 关系如图6。图5网络所有联通子图大小之和与删除步骤关系 图，横坐标为删除步骤，纵坐标为所有连通子图 大小和；方形为度删除策略，加形为先导潜数删 除策略。图6网络聚类系数与删除步骤关系图，横坐标为 删除步骤，纵坐标为聚类系数；方形为度删除策 略，加形为先导潜数删除策略。2.2BA,WS,NW网络的网络潜数分析实验分析了 BA网络 新节点与2个 老节点相连，即 m=2 ）的网络节点数目 n 从1取到200时网络潜数 PLN的变化情 况，其

16、网络潜数随着网络规模的增大，呈 对数形式缓慢上升，如图7。另外当 n=500 时，PLN=2.45， n =1000 时， PLN=2.617。同样分析了 NW网络 初始网络中每 个节点与最近2个节点相连，即 K=4 ）的 网络节点数目n从1取到200时PLN的变化 情况，PLN随着n的增大，呈Rayleigh 分 布上升后缓慢下降并趋向于1，如图8，matlab的分布检验曲线趋于直线。另外当 n=500 时，PLN=1.0109 ， n=1000 时， PLN=1.0055。在WS网络K=4 ）中，n从1取到 200时网络潜数的变化情况如图9，PLN随着n的增大，呈对数形式缓慢上升，另 外当

17、 n=500 时，PLN=1.979，n=1000 时， PLN=2.037。NW 网络中，连接概率 p增 大的过程，就是从局部耦合到全局耦合的 过程，这个过程对网络潜数产生的影响如 图 10，p 取 0.05、0.075、0.1、0.2、0.3、 1时，网络潜数随着重连概率p的减少呈整体下降趋势，p=1时网络潜数达到最小 值，即 PLN=1。在WS网络中，重连概率 p减小时， 网络潜数PLN整体呈下降趋势，p取0、 0.05、0.1、0.2、0.3，0.5 时，对于潜数的 影响如图11。图7 BA网络的网络潜数走势图，横坐标为网络 节点数目，纵坐标为网络潜数。20 4D a BU IDO H

18、l 140I EDIBO ZE图11 WS网络的网络潜数走势图，重连概率与 网络潜数走势图，横坐标为网络节点数目，纵坐标为PLN。图8 NW网络的网络潜数走势图，连接概率 p=0.2,横坐标为网络节点数目，纵坐标为网络潜 数。图9WS网络的网络潜数走势图，重连概率 p=0.2,横坐标为网络节点数目纵坐标为网络潜 数。1.6网络潜数与网络节点数目的这种对数 关系，使得网络潜数成为了网络的一个稳 定特征。网络潜数越大，则说明网络中节 点的平均影响力越小，同时节点平均所受 影响力越大，说明网络的性能较差。BA网络的网络潜数较高，它虽然作为许多人 类活动自组织而形成的网络，但从这一点 看来，该网络并不

19、容乐观。3结束语定义了潜数，并通过先导潜数来描述 节点的对外影响力，分析了依据网络类型 的先导潜数分布，发现后导潜数与度具有 普遍的高度相关性。依据节点影响力的节 点删除策略，使得网络的整体被摧毁程度 下降地更快，说明了先导潜数的意义。通 过研究经典 BA网络、WS网络、NW 网 络的网络潜数曲线特点，发现不同网络所 具有的稳定特征。潜数在实际网络中的应用，网络的网 络潜数特征研究以及潜数计算的算法优化 都将是下一步继续研究的目标。o.a町百IIILIIIIIII204D60801DD12014C1301K1200图10 NW网络的网络潜数走势图，连接概率与 网络潜数走势图，横坐标为网络节点数

20、目，纵坐标为PLN。参考文献1 Watts D J, Strogatz S H. Collective dynamics of sma-World networks. Nature, 1998, 393(6684:440442.2 Barabasi A L, Albert R. Emerge ncy of scaling in random networks. Science, 1999, 286(5439:509512.34567891011121314Barabasi A L. Linked: The New Science of Networks. Massachusetts: Pers

21、us Publishing,2002.Newman M E J, Watts D J. Renormalization group analysis of the small-world network model. Phys. Lett.A,1999,263:341346.Newman M E J. The structure and function of complex networksJ. SIAM Review, 2003, 45(2:167256.Albert R., Jeong H., Baarabasi A. L. Error and attack tolerance of c

22、omplex networksJ. Nature, 2000, 406(6794:378-382.Newman M E J. Assortative mixing in networksJ. Physical Review Letters, 2002, 89(20:20871.Gallos L. K., Cohen R., Argyrakis P., Bunde A., Havlin S. Stability and topology of scale-free networks under attack and defense strategiesJ. Physical ReviewLett

23、ers,2005, 94(18:188701.Erdos P, Renyi A. On the evolution of random networks. Science,1999,286(5439: 509512. 汪小帆，李翔，陈关荣编著.复杂网络理论及其应用 M. 北京：清华大学 出版社， 2006.Fronczak A, Fronczak P,and Holyst J A. ,Mean-field theory for clustering coefficients in Barabasi Albert networks, Phys. Rev. E,2003,68:046126. Cohen R,Havlin,S. Scale-free networks are ultrasmall.