基于网络结构熵研究网络演化的一种新方法
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于网络结构熵研究网络演化的一种新方法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要:为了定量描述网络的发展演化,提出了一种网络结构熵的演化表达形式,为更好研究网络的异质性提供了刻画度量,阐述了利用这种方法研究网络演化的原因及通用性。同时,以Internet AS 网络为例。求出了其随时间演化关系,指出这种网络的演化发展的方向及其异质性的变化趋势。
关键词:复杂网络;网络结构熵;Internet AS 网络
中图分类号:TP393文献标识码:A文章编号:1009-3044(2010)10-2527-02
A New Research Method Based on Network Structure Entropy for the Network Evolution
LIU Xue-jun
(The Department of Communication Engineering, Engineering College of Chinese Armed Police Force, Xi'an 710086, China)
Abstract: In order to descripe the evolution of the network, a network structure entropy of evolution was expressed, for the research of network hetroplasmy provided the characterition metric, elaborate the reason and versatility of network evolution with this method . At the same time, for the Internet AS network, find their relationship and pointed out that this network evolution and heterogeneity in the direction of development.
Key words: complex networks; network structure entropy; Internet AS networks
熵是一个物理学概念,熵是事物不确定性的度量。可以理解为系统内部混乱度的度量。一般来讲,系统宏观状态拥有的微观状态越多,可能情况就越多,系统的不确定性也就越大,而微观状态越多表明系统内部运动越富有多样性,越混乱无序,从而熵越大;反之,系统微观状态越少,系统内部状态越单一化,越有序,熵就越小[1]。
现实世界的许多系统都可以用复杂网络[2]进行描述,这种网络既不是规则网络,也不是随机网络,而是一种具有与这两者不同的统计特性的网络,其中,最具影响的是小世界网络和无标度网络。本文主要讨论无标度网络。如:论文引用网络、WWW网络等。研究发现,无标度网络具有很强的非同质性,即,大部分节点只有少数几个连结,而极少数节点却具有大量的连结,这样的网络是一种非均匀的网络,其度分布服从幂律分布。网络中每个节点和其它K个节点相连接的概率正比于k-γ,这里γ为常数,且γ≥0。刻画这种非同质性时可以借助其分布指数,指数越大,度分布曲线下降越快,网络的非同质性越强,反之,则越弱。正如文献[3]指出的,现实世界的复杂网络,度分布曲线并不是完全规则的曲线,通过拟合得到的曲线也并不完全精确。于是人们把熵的概念引入复杂网络中用来刻画网络的非标度性。而本文正是在此基础之上,研究了利用网络结构熵研究网络演化的方法,并探讨了Internet AS层网络的演化规律。
1 网络结构熵及研究网络演化的方法
由文献[3]知网络结构熵可表示为:
(1)
其中,Ii是节点i的重要度,,N是网络中的节点数,显然ki≥0。
可以证明,当网络完全均匀时所有节点的度值相同,这是网络中所有节点具有相同的重要度Ii=1/N此时,熵获得最大值:
(2)
当网络完全不均匀时,网络中的连结呈星型结构,即有一个中心节点和网络中所有其它节点都相连,其度值为N-1(N是网络的节点数),而网络中其它节点的度值都为1,此时得到的网络结构熵的最小值:
(3)
由(1)(2)(3)知网络结构熵、网络结构熵的最大值、最小值都和网络规模有关。其中网络结构熵除了和网络规模有关外,还和各个项的取值有关,由以上三式可得:
Emin≤E≤Emax(4)
显然,对于某个节点数N确定的网络来讲,如果仅网络的总边数发生变化而导致网络在不断的演化,那么网络结构熵E的变化只能在有(4)式确定的范围内,为消除节点数对网络结构熵的影响,文献[5]提出了网络的标准结构熵,即:
(5)
上式求解过程利用了特定网络的最大值,最小值,排除了节点数的影响,但依然是局限于节点数固定的网络,一旦网络节点数发生变化,由于分子和分母只针对固定节点数得到的,因而改变前后的网络结构变化并不能通过熵值的变化来进行判断。也就是说对于节点数变化或者动态演化网络而言,如何运用网络结构熵来研究网络的演化呢?进而如何说明网络异质性的变化呢?本文提出以下方法:
(6)
网络结构熵取得最大值表明网络完全均匀,式(6)表示网络结构熵与完全均匀网络的偏离程度,值越小说明网络越接近完全均匀网络。即如果E=0,则E=Emax说明网络是完全均匀的。利用式(6)可以衡量网络的演化,即(6)式值如果不断的递减,则说明网络是朝着均匀方向发展;若不断的递增,则说明网络朝着非均匀方向发展。通过变化可以确定网络的发展演化趋势。实际上式亦可改写成下式:
(7)
可以说通过(6)(7)式来确定网络和完全均匀网络及完全非均匀网络的接近程度是一种利用网络结构熵研究网络演化的好方法,这种方法对于节点数变化的网络同样适用。由于它们表示的是和本规模下完全均匀网络或者完全非均匀网络的接近程度,即克服了标准网络结构熵的局限性和不足。下面,就这一方法应用于研究Internet AS 层的网络演化,同时应用(6)(7)相互印证。
2 Internet AS 层网络的演化发展及分析
通过对CAIDA项目在网上所的数据进行相应的处理,获得了自2001年3月1日到2007年5月25日的Internet AS 层节点连结相关数据,我们以20天为一个数据点进行处理,即把每20天内得到的数据看成是一个网络,共可以得到108个数据点,按照时间先后进行排列,并画出相应的演化图,其中图1是网络和完全均匀网络的偏离程度的时间演化图。
由图1可知Internet AS 层节点网络的网络结构熵随着时间的演化与完全均匀网络的偏离程度有逐渐减少的趋势,也就是说(6)式中E越小,虽然这种幅度并不大,其原因是Internet AS 层网络在一个比较短的时间段内不可能发生比较大的变化,接点数和边的数目也就不会发生较大的改变,同时网络结构熵还与各个节点的重要度有关,图中各个数据点在所画的直线上下波动,波动的幅度不大,这就造成了网络结构熵和均匀网络的接近度在不断的上下波动,但始终沿着这条曲线在减小。其中最大的E=0.1880,最小的E=0.1564,下降了16.82%。
在开始时刻E=0.1723,统计的终止时刻的E=0.1590,下降幅度为7.76%,表明网络比开始时刻更加接近完全均匀网络,接近程度近了7.76%。这也说明了随时间的发展,网络结构趋向于向均匀网络方向发展。
以上是利用(6)式所进行的分析,对于(7)式分析亦有相同的结论。下面的图2是根据(7)所做的演化图。
3 结论
本文在网络结构熵的相关概念基础上提出了运用网络结构熵研究复杂网络演化发展的新方法,同时指出了利用标准结构熵直接来研究网络演化的弊端和局限性。这种研究网络演化的方法具有一般性,对于复杂网络的演化问题均可以采用这种方法。实际上,这种方法是利用了数学中的逼近法研究网络演化的方法。本文以Internet AS层网络为例,从两个方向研究了该网络的演化规律,指出了该层网络的演化规律趋势。
参考文献:
[1] 陈宜生.物理学家[M].天津:天津大学出版社,2005.
[2] Alert R,Barabasi A L.statistical mechanics of complex networks[J].Reviews of Moderm physics,2002,74(1):47-97.
[3] 郭雷,许晓鸣.复杂网络[M].上海:上海科技出版设,2006.
[4] 谭跃进,吴津.网络结构熵及其在非标度网络中的应用[J].系统工程理论与实践,2004,24(6):1-3.