自相似复杂网络的分形特征分析

摘要:针对自相似复杂网络的研究进展情况,阐述了自相似复杂网络的形成过程,讨论了容量维数和信息维数这两类分形维数的优缺点和应用,并对复杂网络的平均最短路距离、群集系数和顶点度分布等三个统计属性进行详细介绍,从而揭示自相似复杂网络的分形特征。

关键词:复杂网络;自相似;容量维数;信息维数;分形特征

中图分类号:TP393文献标识码:A文章编号:1009-3044(2010)21-5959-03

An Analysis of the Fractal Feature of Self-similar Complex Networks

MAO Ke-hong,LI Guang-song

(Department of Information Engineering, Guangdong Textile Polytechnic, Foshan 528041, China)

Abstract: In view of research progress of self-similar complex networks, this paper describes the formation process of self-similar complex networks, discusses the advantages and disadvantages and applications of two types of fractal dimensions which are volume dimension and information dimension, and described in detail the average shortest distance , the cluster coefficient and the vertex degree distribution to reveal the fractal feature of self-similar complex networks.

Key words: complex networks; self-similarity; volume dimension; information dimension; fractal feature

1 自相似复杂网络的研究进展讨论

Erdos和Renyi在1960年应用随机图理论提出了随机拓扑模型来研究复杂网络。近年来许多研究复杂网络理论的学者发现:在现实的复杂网络中得到的许多实验数据和结果与随机拓扑模型并不符合,因此需要建立新的网络模型来描述实际网络。Watts和Strgatz于1998年提出了描述现实网络的小世界模型,他们在文章中描述了现实网络所具有的大聚簇和短平均路径距离的特征。然而,现实世界中的复杂网络,在很多情况下其实有极少数的节点拥有大量的连接,而许多节点却只有少量连接的特点,这些特点同样无法用随机拓扑模型来解释。不久后,Barabasi和Albert提出了无尺度模型,他们认为增长性和择优连接这两个基本原理决定了互联网等现实复杂网络具有无尺度性。尽管小世界模型与无尺度模型刻画了复杂网络的基本特征,但都是基于对现实复杂网络进行理想化的前提下得出的结论。然而,对于复杂网络的自相似分析特征研究则是利用网络节点之间的互动特性来解释网络的微观演化过程,如C.M.Song与S.Havlin等人利用重构化理论来揭示复杂网络的自相似分形特征 ,R.Guimera与L.Danon在研究中利用邮件系统来揭示社区结构的自相似分形特征。以上的研究方法并不能从复杂网络的动态增长性方面揭示复杂网络的自相似分形特征。最近,陶少华等研究者在文献[7]-[8]中分别研究了基于信息维数与容量维数的复杂网络的自相似性,建立了基于自相似分型特征的网络演化模型,并且说明动态增长的复杂网络的确是自相似的。本文阐述了自相似复杂网络的形成过程,讨论其分形维数和统计属性,从而揭示自相似复杂网络的分型特征,有助于更清晰地了解自相似复杂网络的体系结构。

2 自相似性复杂网络的形成

在分形几何的研究中,自相似是相似中的一种特殊情况,它是指系统的部分和整体之间具有某种相似性,这种相似性不是两个无关事物间的偶然近似,而是在系统演化中必然出现并始终保持的 。基于这一事实,陶少华等在文献[8]中提出了复杂网络的自相似原理,即复杂网络在演化的过程中将始终保持自己特征状态的相对稳定性,从而使它的整体和部分、部分与部分之间呈现出某种相似性。自相似网络起初是通过节点之间的关系来传递信息而形成的。首先,每个节点能够自动获得本身的信息,并且节点之间有一种相互作用,能够彼此建立联系并传递信息。若传递的信息具有相似性或者相同之处,则建立连接并同属一类。在现实网络中可以描述为一下过程:

1) 节点m对自己有认知,获得关于自己的信息,假设它有(n1,n2,…,nk)个特征,并且节点mi向其周围的其它节点传递信息,若节点彼此之间传递的信息具有相同之处或相似性,则建立连接。

2) 若网络中加入新的节点qi(q1,q2,…,qk),同时新节点与老节点彼此向对方传递信息,若新节点与网络中任何一个老节点有相似性,则建立连接。

3) 若节点m的n1,n2,…,nk个特征与节点qi(q1,q2,…,qk)有相似的信息并且建立连接,则有:

即节点qk与m的相似信息都属于m的自身特征。

此时,我们称节点之间具有以下性质:

1) 传递性:若m～q且q～s,则m～s;

2) 对称性:若m～q,则q～m;

3) 反身性:m～m。

其中,“～”表示相似性。

综上所述,节点m具有的特征是形成相似性的基础。在t时刻节点m与q相连,经过t时刻之后,假设演化为具有100个节点的局部网络S1。在S1的基础上继续有新节点与老节点相连接,形成具有1000个节点的局部网络S2,则S1与S2相似。随后形成具有10000个节点的局部网络S3,直至最终形成网络F。则S2与S3相似,S3与F相似,因此整个网络是自相似的。于是陶少华等人利用分形几何中刻画自相似集合的数学方法 得到了如下定理来刻画自相似网络:

定理1 S1,S2,…,Sm是子网络集合, 若存在数c满足条件0

S1～c1S2

S2～c2S3

…

Sm～ciF

则称Sm是相似的,0

3 自相似网络的分形维数

3.1 自相似复杂网络的容量维数

由于分形具有形态的不规则性,不能用传统的欧氏几何语言来描述,一般集合的分形维数大于其拓扑维数,因此分形维数一般为非整数,对于它的估算,是目前自相似复杂网络研究中的一个重要问题。而在所有不同定义的分形维数中,其中计盒维数也称为容量维数(具体定义请参见文献[6])则是应用得最多的。陶少华等在文献[8]的研究中,应用容量维数来描述复杂网络的自相似分形特征,给出了计算自相似复杂网络的容量维数的具体方法,并用此方法分析了复杂网络在不同阶段的容量维数,得出维数相同(或相近)时,复杂网络具有自相似分形特征。因此,我们在计算自相似复杂网络或者自相似图形的分形维数时,采用圆片(或方块)去填充(或覆盖)被计算的对象,统计覆盖所需的方块数来计算其分形维数。如此方法计算的分形维数我们称为容量维数:若用长度为λ尺子去测长度为L的线段,L与λ之比为N。其中N的大小与λ的长短有关,λ越小,则N越大:。对于Dc维的物体有:

。

取对数可得自相似复杂网络的容量维数:。

3.2 自相似性复杂网络的信息维数

在自相似复杂网络的分形维数计算中.最常用的是容量维数。然而容量维数的计算只考虑了覆盖整个网络的盒子数,而没有考虑在一个盒子内所包含的节点的个数。显然,应用容量维数揭示复杂网络的自相似分形特征有一定的局限性。鉴于此,陶少华等人在文献[7]中,对自相似容量维数的算法进行了以下改进:

1) 对每个覆盖的盒子按照填充程度(即所包含的节点多少)进行逐个编号;

2) 统计出自相似分形结构落入第i个盒子的概率pi(λ):

由上式推导出信息公式为:

。

于是我们可以得到自相似复杂网络的信息维数公式为:

从而可以计算信息维数用以研究复杂网络的自相似分形特征。

在分形几何和自相似复杂网络理论的研究中,容量维数和信息维数是最常用的分形维数,其优点是因其算法简单、快速、估算精确。因此在验证自相似复杂网络的分析特征时,得到研究者的广泛采用。

4 量化自相似复杂网络分形维数的三个统计属性

平均最短路径距离(l)、群集系数(c)、顶点度分布(p(k))是复杂网络的三个统计属性,许多学者在研究中均采用次三个统计属性来量化分形维数,从而揭示自相似复杂网络的演化过程。下面我们简单介绍它们的定义:

假设一个包含n个节点的网络,我们称l是复杂网络中节点之间的平均最短路径距离:

其中,dij是从节点i到节点j的最短距离。

群集系数是自相似复杂网络的另一个重要的统计属性,它刻画了自相似复杂网络的小聚集形态。群集系数可用以下公式来量化:,其中Ci为节点i的局部群集系数(i=1,2,…,n)。而Ci的计算式子如下:。对于此公式的理解是,网络节点i,它通过ki条边与其它ki个网络节点相连接。如果这ki个邻居是群集的一部分,则在它们之间有ki(ki-1/2)条边相连接。于是,ki个邻居之间实际有的边数Ei与总边数ki(ki-1/2)之比就给出了节点i的局部聚集系数Ci。

顶点度分布用分布函数p(k)来表示,即网络中度数为k的顶点个数占顶点总个数的比例。

量化自相似复杂网络的分形维数过程可以描述如下:当形成一个小的局部复杂网络时,我们就来计算它的平均最短路径距离l1,群集系数c1与顶点度分布p(k1)。继续增加节点形成大的局部复杂网络时,计算它的平均最短距离l2,群集系数C2与顶点度分布p(k2)。再继续增加节点形成一个更大的局部复杂网络时,同样计算它的平均最短距离l3,群集系数C3与顶点度分布p(k3)。然后以l1为方块去覆盖整个复杂网络的平均路径长度l,计算需要l1的块数N(l1)。于是,可以得到自相似容量维数为。然后以l1与l2去覆盖整个复杂网络的平均路径长度,计算需要多少块l2与l3,分别计算出它们的自相似容量维数,Dc2和Dc3。如果Dc1,Dc2与Dc3是取相同值或相近值,则说明此复杂网络是自相似的。

同理,利用局部复杂网络的群集系数与顶点度分布作为方块来覆盖整体复杂网络,也可以分别计算出自相似复杂网络的容量维数。因此,我们可以从自相似复杂网络的三个统计属性来量化其分形维数,并加以分析验证复杂网络确实具有自相似分形特征。

5 结束语

自相似复杂网络的分形特征是基于分形几何理论与复杂网络理论结合的研究结果,引起了众多研究者的关注,而基于分形维数和平均最短路径距离、群集系数、顶点度分布等统计属性来揭示自相似复杂网络的分形特征是非常重要的研究方法。因此,本文分析了自相似复杂网络的形成过程以及其分形维数、统计属性,有助于人们了解复杂网络的分形特征的体系结构。

参考文献:

[1] Erdos Prey A. On the evolution of Random Graphs [J].Publ Math Inst Hung Acad Sci, 1960, 5:17-61.

[2] Watts D J, Strogatz S H. Collective Dynamics of "Small-world" Networks [J].Nature, 1998, 393:440-442.

[3] Barabasi A L, Albertr. Emergence of Scaling in Random Networks [J].Science,1999,286(15): 509-5l2.

[4] Song Chao-ming, Havlin S, Makse H A. Complex networks are self-similar [J]. Nature, 2004,433.

[5] Guimera R, Danon L, Dlaz-Guilera A,et a1.Self-similar community structure in a network of human interactions [J]. Physical Review E, 2003,68.

[6] Falconer K J. Fractal Geometry: Mathematical Foundations and Applications [M]. New York: John Wiley and Sons, 1990.

[7] 陶少华.基于信息维数的复杂网络自相似性研究[J].计算机工程与应用, 2007, 43(15):108-110.

[8] 陶少华.基于容量维数的复杂网络自相似性研究[J].计算机工程, 2008, 34(2):175-177.

[9] 方爱丽,孙丽瑶.复杂网络的分形特征及其实证研究[J].计算机工程, 2009, 45(20):52-56.

注:本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文

推荐访问:特征 分形 分析 网络