具有双峰效应特性的复杂网络模型研究

刘胜久，李天瑞，珠 杰,3，王红军

(1.西南交通大学信息科学与技术学院，成都 611756；2.四川省云计算与智能技术高校重点实验室，成都 611756；3.西藏大学计算机科学系，拉萨 850000)

具有双峰效应特性的复杂网络模型研究

刘胜久1,2，李天瑞1,2，珠 杰1,2,3，王红军1,2

(1.西南交通大学信息科学与技术学院，成都 611756；2.四川省云计算与智能技术高校重点实验室，成都 611756；3.西藏大学计算机科学系，拉萨 850000)

为解决BA网络模型采用增长与择优处理节点之间的连接而导致节点连接数目无限增长等不足，通过对BA网络模型的节点连接策略改进，即通过引入节点最大连接数目，设置新增节点连接数目亚线性增长并采用Logistic函数得到了一种度分布具有双峰效应特性的BE网络模型，并给出了其若干性质。该模型可应用于解释经济、社会等现实生活中的两极分化现象，而且通过调整其参数可实现峰的移动和缩放，在极限情况下BE模型可退化成BA模型。

复杂网络; 无标度; 双峰效应; Logistic函数

0 引言

复杂网络最初属于图论的研究范畴，起源于欧拉对著名的哥尼斯堡七桥问题的研究，对复杂网络的系统性研究可追溯到上世纪中叶。20世纪60年代，Erdos和Renyi提出了一种完全随机的网络模型——ER随机网络，由此建立起的随机图理论被公认为是在数学上开创了复杂网络理论的系统性研究[1]，并引领了后续近半个世纪对复杂网络的研究。ER网络模型采用随机方式处理节点之间的连接，由此得到的网络度分布呈泊松分布，与真实网络并不完全相符。1999年Barabasi和Albert采用增长与择优处理节点之间的连接，提出了BA网络模型[2]。BA网络模型揭示了复杂网络的无标度性质，构造出节点的度分布服从幂律分布的无标度网络。由于BA网络模型可较好地解释真实网络的部分特性，受到了人们极大的关注，对其改进也成为复杂网络研究的重点，并相继提出了确定性无标度网络模型[3]、局域演化网络模型[4]等多种网络模型。BA两种网络模型所对应的小世界网络节点度分布不同于ER随机网络的泊松分布，但是这二个网络模型的节点度分布均只有一个尖峰，属于典型的单峰分布。在现实生活中，常常出现类似于两极分化的双峰效应现象，而经典的网络模型对此难以刻画。本文通过对BA网络模型新增节点连接数目、既有节点连接概率及节点最大连接数目的改进，构建出一个度分布具有双峰效应特性的复杂网络模型，可应用于解释经济、社会等领域中的两极分化现象。

设图G=(V,E)是一个无向无环无权图，其中V={v1,v2,…,vi,…}(1≤i≤|V|)是网络中所有节点的集合，E={e1,e2,…,ej,…}(1≤j≤|E|)是网络中所有边的集合，且有E⊆V×V。|V|表示图G中的节点数目，|E|表示图G中的边数目。

定义1[5]图G中节点vi的度d(vi)是指图中与该节点直接相连的节点的数目。

对于拥有|V|个节点的图G而言，d(vi)的最小值对应于vi为孤立节点，即没有任何节点与vi相连，此时有d(vi)=0；d(vi)的最大值对应于除vi外的所有节点均与vi相连，此时有d(vi)=|V|-1，故有0≤d(vi)≤|V|-1。

定义2[5]图G的节点度分布是指图G中节点度的概率分布或频率分布(统称分布)。

度分布是对一个图中节点度数的总体描述，对于随机图而言，其度分布指的是图中节点度数的概率分布。对于任一非负整数d，度数为d的节点在图G中所有节点中所占的比例P(d)表述为[6]

(1)

显然有：

(2)

当然，也可以用图G中节点度的频数来描述度分布，此时式(1)及式(2)表述为

(3)

(4)

在描述图G的度分布时，式(1)与式(3)和式(2)与式(4)的效果是一样的。

定义3[5]图G的阶数是指图G中的节点数目|V|。

图的阶数是描述图的规模的重要参数。

1 研究现状

1.1 复杂网络模型研究现状

当前对复杂网络模型的研究主要集中两个方面：对BA无标网络模型等经典网络模型的研究与改进及新型网络模型的构建等。

在对经典网络模型的研究方面，王杰等[7]以复杂网络理论为基础，分析海运网络的拓扑结构具有无标度特性，并改进了BA网络模型中的节点连接概率，通过实验验证了海运网络具有小世界网络特征。Galiceanu等[8]对具有无标度网络特性的聚合物进行研究，借鉴动力学研究方法，对松弛度量和静态行为进行研究，重点分析了刚度参数和网络规模对其动力特性的影响，尤其是对其连通性的影响。辜芳琴[9]及曹玉芬[10]等对BA网络模型等无标度网络模型从不同的视角进行了研究。

在对新型网络模型的研究方面，刘浩然等[11]基于节点批量到达的Poisson网络模型提出了一种具有容侵优化特性的无标度拓扑模型，并在构建拓扑时引入剩余能量调节因子和节点度调节因子，得到了一种容错性与容侵性兼具且幂律指数可调的无标度拓扑结构。Emmerich等[12]对嵌入式无标度网络的结构和功能特性进行研究，并对比分析了嵌入式无标度网络与非嵌入式无标度网络的异同，发现空间嵌入对网络的化学距离和脆弱性影响显著。韩丽[13]及Ruiz等[14]针对真实网络的特点构造出不同的无标度网络模型。

复杂网络是复杂系统的高度抽象，得到了人们极大的关注。周涛等[15]列出了目前复杂网络研究面临的最主要的10个挑战，对复杂网络的研究具有重要的指导意义。此外，对通信网络[16]、社交网络[17]等其他类型真实网络的研究也是复杂网络研究的重点。

由上表明对BA无标度网络模型等经典网络模型的持续改进是复杂网络研究中的一个重要内容。其次，如何将经典网络模型与真实世界的各项特性结合起来，以构建出新的网络模型是复杂网络研究的另一大趋势。

1.2 双峰效应与两极分化

双峰效应是指化学元素中镧系元素的原子半径随原子序数的增长并不是单调减小，而是在Eu和Yb处出现峰和在Ce处出现谷的现象[18]。除此之外，原子体积、密度、原子的热膨胀系数、第三电离子能、前三个电离能的总和、原子的电负性、一些化合物的熔点、沸点等也出现这种效应。在现实生活中，双峰效应突出的表现为经济、社会等领域中的两极分化现象。对两极分化的成因，有地区差距、城乡差距、分配差异等不同的理论[19]，但都有失偏颇，对其根源仍莫衷一是。目前较认可的说法是多种内因与外因综合作用的结果，是社会发展阶段的必然，但迄今仍然缺乏直观、形象的模型或理论对此给出可信、合理的解释。

复杂网络的两极分化现象在真实网络中广泛存在，典型的代表之一便是万维网[20]。万维网的度分布高度弥散，呈现出重尾分布形式的幂律分布，具有明显的两极分化倾向。此外，科学家合作网络中某一节点的近邻节点的介数分布也具有两极分化特性[21]，称为漏斗效应，也具备双峰效应的特点。由于BA无标度网络可对复杂网络的两极分化现象进行一定程度的刻画，对BA无标度网络的研究成为复杂网络研究的重点。

1.3 Logistic函数

Logistic函数是一种常见的S形函数，是Verhulst在研究人口增长时命名的，其提出的人口增长模型被命名为Logistic模型，区别于Malthus模型[22]。

Malthus模型的微分方程形式表述为

(5)

Logistic模型的微分方程形式表述为

(6)

Malthus模型的实质是指数增长，而Logistic模型是阻滞增长。按照Malthus模型，人口数量是没有上限的，即人口可以无限增长，这显然不符合自然规律。当人口数量不太大时，Malthus模型——指数增长模型可以较好地反映人口增长的特点[23]，但人口的增长会带来能源消耗及资源消耗的增长，而能源与资源的总量是一定的，也即在人口增长的同时，自然资源、环境条件等因素对人口持续增长的阻滞作用会越来越显著。当人口数量较少时，人口的相对增长率可以视为常数，但当人口增加到一定数量时，相对增长率则会随着人口的持续增加而逐渐减少，此时Malthus模型并不适用，而Logistic模型——阻滞增长模型就更为适用了。Logistic模型在其他领域也得到了许多成功的应用[24-25]。

本文拟将Logistic模型应用于网络模型的节点连接中，对经典的BA网络模型进行改进，构建出一个度分布呈现出双峰效应特性的BE(Bimodal Effect)网络模型。

2 具有双峰效应特性的BE复杂网络模型

2.1 经典复杂网络模型的不足

经典的BA网络模型在新增节点与既有节点建立连接时采用择优连接的策略，隐含着一个假设：一个节点可以与任意多个节点建立连接，即节点的连接数目是没有上限且可以无限增长。由此得到的网络度分布呈单峰形态的幂律分布，即节点的度分布只有一个峰值。在实际情况中，这个假设是不成立的。一个节点维持与另一个节点的连接需要消耗能源与资源，而不可能与任意多个节点建立连接，必然存在最优连接数目与最大连接数目。理论与实验均表明，在真实网络中，这样的最大连接数目M是存在的，如在社交网络中，邓巴数字表明，M=150，被称为150定律[26]。不同的网络有不同的最大连接数目M，可通过理论分析、实验测试或经验知识等得到M。

此外，在经典的BA网络模型中，新增节点自始至终总是选择固定数目的既有节点并与之建立连接。在实际情况中，这个假设也不尽合理。随着节点数目的增长而导致网络规模的扩大，一方面，新增节点在与既有节点建立连接时会有更多数目的既有节点可供选择，另一方面，更大规模的网络意味着有更多数目的既有节点期待与新增节点建立连接。这样，新增节点与既有节点建立连接的数目不应设定为常数C，而应设定为网络规模即节点数目|V|的函数f。但f的增长速率不能超过节点数目的增长速率，应满足0

2.2 一种具有双峰效应特性的复杂网络构建方法

经典的BA网络模型的要点一是节点增长，二是度数高的节点优先连接。它是基于初始网络G0，逐个添加节点，每个新增节点均与固定数目的n个既有节点建立连接且优先选择度数高的节点建立连接，并添加m个节点，该模型可记为BA(G0,n,m)。对于某个既有节点vi而言，若其在原网络中的度为d(vi)，则新加入的节点与其建立连接的概率pi为

(7)

即新增节点与既有节点建立连接的概率pi与既有节点的已有连接数目成正比，表述为

pi∝d(vi)

(8)

我们对BA(G0,n,m)模型进行3个方面的改进，得到了一个度分布具有双峰效应特性的BE网络模型，记为BE(G0,f,m,M)。其表示基于初始网络G0，每个新增节点均与f(|V|)个节点建立连接，共添加m个节点，且新增节点通过Logistic函数选择既有节点进行连接以及最大连接数目为M。BA和BE两种网络模型的对比如表1所示。

表1 BA与BE两种网络模型的对比Tab.1 Comparison of Network Models between BA and BE

对BA网络模型进行3个方面的改进：

1) 设定网络中节点的最大连接数目为常数M，而不是无穷大；

2)采用Logistic模型连接代替择优连接来处理新增节点与既有节点之间的连接。于是新增节点与度为d(vi)的既有节点vi建立连接的概率pi可以表述为

(9)

对BA网络模型及其改进模型——BE网络模型进行分析，可以得到以下结论。

定理1 BE网络模型中新增节点与既有节点vi建立连接的概率pi与既有节点的已有连接数目d(vi)及剩余连接数目(M-d(vi))二者的乘积成正比，即：

(10)

证明：对于任意的既有节点vi而言，其与新增节点建立连接的概率等于新增节点与该节点建立连接的概率pi，如式(9)所示。对于式(9)右边分式的分母有：

(11)

式(11)与节点vi无关，对任意节点而言均相等。故pi只与式(9)右边分式的分子有关，即为式(10)所示。定理1得证。

定理2 在极限情况下BE网络模型与BA网络模型是等价的。

证明：对BE网络模型BE(G0,f,m,M)而言，在极限情况下，当M→∞且f取线性函数——常数函数f=n0≤|V0|时，有：

(12)

此时BE(G0,f,m,M)可表述为BE(G0,n0,m)，与BA(G0,n,m)等价，即当M→∞且f取常数函数时，BE网络模型就是BA网络模型。定理2得证。

定理2表明在极限情况下，选择合适的新增节点连接数目、既有节点连接概率以及节点最大连接数目，BE网络模型可以退化成BA网络模型，即BA网络模型是BE网络模型的特例。

此外，由于节点的最大连接数目为M的前提条件对任意新增节点仍然适用，即新增节点的节点连接数目也不能超过M。于是可以得到定理3。

定理3 对BE模型BE(G0,f,m,M)而言，f、V0、m、M四者应满足f(|V0|+m)≤M，其中V0为图G0的节点集合。

证明：用反证法。假设f(|V0|+m)>M，对BE模型BE(G0,f,m,M)而言，当初始网络G0新增第m个节点时，对该新增节点而言，与之相连的节点数目为f(|V0|+m)，由于节点的最大连接数目为M，而f(|V0|+m)>M，与前提条件矛盾，故假设不成立。定理3得证。

2.3 具有双峰效应特性的复杂网络仿真分析

从图1-5可以看出，具有双峰效应特性的复杂网络模型——BE(G0,f,m,M)的度分布不同于随机网络的泊松分布、小世界网络的指数分布、无标度网络的幂律分布或其他形式的单峰分布，而是呈现出双峰分布的特点，其中BE3尤为显著。从BE2、BE3、BE4可以看出，在新增节点数目m不变的情况下，通过调整最大连接数目M，可以实现两个尖峰的移动及缩放，且尖峰的移动及缩放与M正相关；从BE1、BE3、BE5可以看出，在最大连接数目M不变的情况下，通过调整新增节点数目m，也可以实现两个尖峰的移动及缩放，但尖峰的移动及缩放与m负相关。通过合理地设置并调整新增节点数目及最大连接数目可以实现单峰分布及双峰分布的相互转化。特别地，在极端情况下，双峰分布也会退化成单峰分布，如BE5所示，验证了在最大连接数目M趋近于无穷且新增节点连接数目函数f为常数的情况下，BE网络模型就是BA无标度网络模型。选择其他类型的亚线性函数f可以得到类似的结论。

图1 BE1= BE(G0,f,5 000,400)的网络度分布图Fig.1 Degree distribution of BE1=BE(G0,f,5 000,400)

图2 BE2= BE(G0,f,10 000,300)的网络度分布图Fig.2 Degree distribution of BE2=BE(G0,f,10 000,300)

图3 BE3= BE(G0,f,10 000,400)的网络度分布图Fig.3 Degree distribution of BE3=BE(G0,f,10 000,400)

从图1-5还可以看出，在节点连接数目存在上限、既有节点采用Logistic函数与新增节点建立连接且新增节点连接数目亚线性增长的情况下，出现了类似双峰效应的两极分化现象。经济、社会等领域中两极分化现象的自然出现、漫长演化及最终消亡等可以通过BE网络模型中参数m及M的协同变化体现出来。在BE网络模型中，其度分布呈现自然的双峰分布，这可以理解为两极分化的自然出现；随着m及M的变化，BE网络模型中会出现峰的移动及缩放，这可以理解为两极分化的漫长演化；最终，随着m及M的调整，BE网络演化的最终结果是双峰退化成单峰，这可以理解为两极分化的最终消亡。因此，BE网络模型在一定程度可用于刻画经济、社会发展的历程中出现的两极分化现象。

图4 BE4= BE(G0,f,10 000,500)的网络度分布图Fig.4 Degree distribution of BE4=BE(G0,f,10 000,500)

图5 BE5= BE(G0,f,20 000,400)的网络度分布图Fig.5 Degree distribution of BE5=BE(G0,f,20 000,400)

3 结论

经典的BA无标度网络模型采用增长与择优连接策略处理节点之间的连接，隐含着节点连接数目可以无限增长等方面假设，与实际情况不完全相符。本文对BA网络模型进行了3个方面的改进：1)引入节点最大连接数目；2)设置新增节点连接数目亚线性增长；3)采用Logistic函数，从而得到一种度分布具有双峰效应特性的BE网络模型，有别于经典网络模型的泊松分布、指数分布、幂律分布等其他形式的单峰分布。在极限情况下，BE网络模型会退化成经典的BA网络模型。BE网络模型节点最大连接数目及新增节点数目等参数的协同变化会导致峰的移动及缩放，这可以较好地解释经济、社会等领域中的两极分化的自然出现、漫长演化及最终消亡。后续工作的重点是结合真实网络的各项特性对BE网络模型进行深入的分析研究，包括如何通过参数的合理设置来分析双峰移动及缩放的具体特点，进而实现对双峰分布形态的精准调控以分析双峰分布未来的发展趋势。此外，将BE网络模型度分布双峰效应的特性与经济、社会等领域中的两极分化结合起来研究，分析两极分化的成因、趋势与特点也是后续研究的重要内容。

[1]Erdos P,Renyi A.On random graphs I[J].Publicationes Mathematicae,1959,6:290-297.

[2]Barabasi A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.

[3]Barabasi A L,Ravasz E,Vicsek T.Deterministic scale-free networks[J].Physica A,2001,299(3/4):559-564.

[4]Li X,Chen G R.A local-world evolving network model[J].Physica A,2003,328(1/2):274-286.

[5]张先迪,李正良.图论及其应用[M].北京:高等教育出版社,2005.

[6]Newman M E J.The structure and function of complex networks[J].SIAM Review,2003,45(2):167-256.

[7]王杰,李雪.基于改进BA模型的海运复杂网络演化研究[J].武汉理工大学学报(交通科学与工程版),2013,37(3):496-500.Wang Jie,Li Xue.Analysis of shipping complex network evolving based on improved BA model[J].Journal of Wuhan University of Technology(Transportation Science & Engineering),2013,37(3):496-500.

[8]Galiceanu M,Reis A S,Dolgushev M.Dynamics of semiflexible scale-free polymer networks[J].Journal of Chemical Physics,2014,141(14):144902.

[9]辜芳琴，樊锁海.BA 无标度网络的双向演化模型[J].暨南大学学报(自然科学版),2013,34(5):475-478.Gu Fangqin,Fan Suohai.The two-way evolution model of a BA scale-free network[J].Journal of Jinan University(Natural Science & Medicine Edition),2013,34(5):475-478.

[10] 曹玉芬,侯振挺,范伟平.随机 BA模型的度分布[J].数学理论与应用,2009,29(2):24-26.Cao Yufen,Hou Zhenting,Fan Weiping.Degree-distribution of a variant of BA model[J].Mathematical theory and Applications,2009,29(2):24-26.

[11] 刘浩然,尹文晓,董明如,等.一种强容侵能力的无线传感器网络无标度拓扑模型研究[J].物理学报,2014,63(9):090503.Liu Haoran,Yin Wenxiao,Dong Mingru,et al.Study on the scale-free topology model with strong intrusion-tolerance ability in wireless sensor networks[J].Acta Physica Sinica,2014,63(9):090503.

[12] Emmerich T,Bunde A,Havlin S.Structural and functional properties of spatially embedded scale-free networks[J].Physical Review E,2014,89 (6):062806.

[13] 韩丽,刘彬,李雅倩,等.能量异构的无线传感器网络加权无标度拓扑研究[J].物理学报,2014,63(15):150504.Han Li,Liu Bin,Li Yaqian,et al.Studies on weighted scale-free topology in energy heterogeneous wireless sensor network[J].Acta Physica Sinica,2014,63(15):150504.

[14] Ruiz V E,Mitchell D G V,Greening S G,et al.Topology of whole-brain functional MRI networks:Improving the truncated scale-free model[J].Physica A,2014,405:151-158.

[15] 周涛,张子柯,陈关荣,等.复杂网络研究的机遇与挑战[J].电子科技大学学报,2014,43(1):1-5.Zhou Tao,Zhang Zike,Chen Guanrong,et al.The opportunities and challenges of complex networks research[J].Journal of University of Electronic Science and Technology of China,2014,43(1):1-5.

[16] Rangan S,Rappaport T S,Erkip E.Millimeter-wave cellular wireless networks:Potentials and challenges[J].Proceedings of the IEEE,2014,102(3):366-385.

[17] Liang Xiaohui,Zhang Kuan,Shen Xuemin,et al.Security and privacy in mobile social networks:Challenges and solutions[J].IEEE Wireless Communications,2014,21(1):33-41.

[18] Mei Bo,Bi Jinshun,Bu Jianhui,et al.Transconductance bimodal effect of PDSOI submicron H-gate MOSFETs[J].Journal of Semiconductors,2013,34(1):014004.

[19] 卫兴华.我国当前贫富两极分化现象及其根源[J].西北师大学报(社会科学版),2012,49(5):1-9.Wei Xinghua.Understanding the polarization between the rich and the poor in China[J].Journal of Northwest Normal University(Social Sciences),2012,49(5):1-9.

[20] Albert R,Jeong H,Barabasi A L.Diameter of the World Wide Web[J].Nature,1999,401(6749):130-131.

[21] 郭世泽,陆哲明.复杂网络基础理论[M].北京:科学出版社,2012.

[22] Taira K.Introduction to diffusive logistic equations in population dynamics[J].Journal of Applied Mathematics and Computing,2002,9(2):289-347.

[23] Qu J G,Cui Y H,Yang A M,et al.The study for the prediction model of China population growth[J].Journal of Computers,2011,6(10):2076-2083.

[24] Wattimena R K,Kramadibrata S,Sidi I D,et al.Developing coal pillar stability chart using logistic regression[J].International Journal of Rock Mechanics and Mining Sciences,2014,58(2):55-60.

[25] Idlango M A,Gear J A,Shepherd J J.Survival to extinction in a slowly varying harvested logistic population model[J].Applied Mathematics Letters,2014,26(11):1035-1040.

[26] Arnaboldi V,Guazzini A,Passarella A.Egocentric online social networks:Analysis of key features and prediction of tie strength in Facebook[J].Computer Communications,2013,36(10/11):1130-1144.

(责任编辑 耿金花)

Research on Complex Network Model with the Bimodal Effect

LIU Shengjiu1,2,LI Tianrui1,2,ZHU Jie1,2,3,WANG Hongjun1,2

(1.School of Information Science and Technology,Southwest Jiaotong University,Chengdu 611756,China；2.Key Lab of Cloud Computing and Intelligent Technique,Sichuan Province,Chengdu 611756,China；3.Department of Computer Science,Tibetan University,Lasa 850000,China)

The method of growth and preferential attachment applied by the classic BA scale-free network model to deal with connections between nodes of network will result in unlimited connections and other defects.This paper improves the method of connections of BA network model by introducing the maximum number of connections,having a sub-linear growth in the number of connections of new nodes and using Logistic function.Then a new network model named BE with a bimodal degree distribution is obtained.Its several properties are also provided.This model may be applied to explain the socio-economic polarization in the real world well.Moreover,the shifting and zooming of the peak may be achieved by adjusting its parameters.BE network model will be degenerated to BA network model in the limiting case.

complex network; scale-free; bimodal effect; logistic function

1672-3813(2017)01-0046-06；

10.13306/j.1672-3813.2017.01.007

2015-10-08：

2016-04-28

国家自然基金项目(61573292，61262058，61152001)；中国科学院自动化研究所复杂系统管理与控制重点实验室开放课题(20110102)

刘胜久(1988-)，男，湖北随州人，博士，主要研究方向为复杂网络，自然语言处理等。

TP393.0

A