基于邻节点总度数与随机区分度的无标度网络模型研究

耿星晨 陈玮

摘 要：运用复杂网络基础知识，基于BA无标度网络模型构造方法，参考随机初始吸引度网络的优点与不足，提出了一种改进的无标度网络演化模型。该模型以节点区分度代替随机初始吸引度，使旧节点对于新节点的单方面吸引转变为两节点间的相互作用，更突出了不同节点间的差异性；考虑节点的实际影响力，以邻节点总度数作为择优连接标准，避免忽视潜在的重要节点，使网络更符合现实情况。通过实验仿真与分析，验证了该模型服从幂律分布，初始区分度对网络演化具有重要影响，且模型具有更小的邻节点总度数，网络的“贫富悬殊”程度降低，可以模拟更复杂的现实情况。

关键词：复杂网络；无标度网络；邻节点度数；幂律分布；随机区分度

DOI：10.11907/rjdk.172982

中图分类号：TP393

文献标识码：A 文章编号：1672-7800（2018）006-0190-04

Abstract：Based on the construction method of BA scale-free network model，this paper uses the basic knowledge of complex network and considers the advantages and disadvantages of random initial attraction network to propose an improved scale free network evolution model.In this model， the initial attraction degree is replaced by the division degree，then the old node's unilateral attraction to the new node is transformed into the interaction between the two nodes， which makes the differences between nodes more prominent； it also considers the actual influence of nodes and uses the total degree of neighbor node as the standard of preferential attachment， which avoids the negligence of potential important nodes， and makes the network more realistic.Through simulation and analysis， it verifies the model follows power-law distribution and the initial discrimination has important influence on the network evolution， and the model has a smaller total degree of nodes， the gap of the network between the rich and the poor decreases， it can simulate more complex reality.

Key Words：complex network； scale-free network； adjacent node degree； power law distribution； random division

0 引言

通過复杂网络中的无标度网络模型研究社会网络越来越多[1]。BA无标度网络模型是由Barabási 和 Albert[2]于1999年提出的一种经典的无标度网络模型，考虑了实际网络的增长特性和优先连接特性，揭示复杂网络的无标度特性，对现实世界的基本特点有较为准确的模拟[3]。

然而，BA网络节点间的连接概率仅仅依据原节点自身的度数，易造成节点度数 “贫富差距”过于悬殊。在现实网络中，节点选择不仅取决于自身度数，还必须考虑节点自身特性、实际影响力等因素，因而无法较好地模拟复杂的现实情况。

文献[4]提出了基于DMS模型[5]的随机初始吸引度网络模型，通过对节点加入随机的初始吸引因子，较好地体现了节点自身特性对新节点的影响。该模型虽然对现实模拟起了一定的改善作用，但原节点对新节点仍然是单方面吸引，网络依然 “贫富差距”悬殊。

针对上述不足，本文基于BA无标度网络模型，从节点的实际影响力出发，考虑不同节点间的双向选择性，通过邻节点总度数与随机区分度对传统模型进行改进。

1 传统BA无标度网络

研究表明，包括Internet、人际关系网和城市交通网在内的众多现实网络，其节点的度分布函数具有幂律形式[7-10]。由于这类网络节点的度无明显的特征长度，所以被称为无标度网络[11]。BA无标度网络模型作为首个同时具备节点增长与优先连接的网络模型，具有明显的小世界特性[12]，其稳态度分布函数为：

显然其度指数与网络规模m是无关的。BA无标度模型构造算法如下：

2 基于DMS模型的随机初始吸引度网络模型

传统BA无标度网络仅仅通过节点的度数大小决定连接概率，对于现实网络的情况过于简化。为了对现实网络进行更深入的研究和分析[10-11]，需要对节点本身的特性进行明确表达。网络中的旧节点会对新加入的节点产生某种吸引力，吸引力大小只与自身特性有关。将节点内在具有的对新节点的吸引力定义为吸引因子[12]，用α表示，某个节点i的吸引因子表示为α-i，由此提出随机初始吸引度网络模型，该网络演化过程为：

（1）最初时网络存在m-0个节点，这些节点随机获取了一个吸引因子，在每个时间步加入一个新节点，新节点会与已存在的m个旧节点连接，m≤m-0。

（2）新节点与已存在的某个旧节点i相连接的概率：

在该模型中，节点的度数和吸引因子共同决定了连边概率，于是就出现了即使某些节点度数不是很大，依旧会因为自身的吸引力强大而与很多节点产生连接的现象。

3 改进的无标度网络演化模型

3.1 随机初始区分度因子

虽然随机初始吸引度网络中的旧节点对新节点有着不同的吸引力，但由于旧节点的吸引度值仍然是定值，则对于以后出现的所有新节点，吸引度较大的旧节点始终保持吸引力的优势，这种特性加剧了各节点度数的差异性。在众多现实网络中，例如合作关系网络，人与人之间的联系常常是双向选择的，即新旧节点的互相吸引才会使双方拥有更大的连接可能性。

这里对每个节点随机加入一个反映其本身特性的参数β（0≤β≤β-max），叫作节点区分度因子，表示该节点与某种指标的不同程度。当β为0时，该节点的自身特征与标准情况完全一致；当β为β-max时，则与标准情况的所有特征都不同。旧节点i的区分度因子为β-i，新加入节点p的区分度因子为β-p，两者间的实际吸引力以Δβ-ip表示：

显然，两个节点的β值越接近，两者间的相似度越高越容易发生连接，这与人际交往中的“人以群分”现象很相似。

3.2 邻节点总度数与实际影响力

一般认为，节点度数越大，节点在网络中就越重要[13]，新节点会倾向于与度数大的节点进行连接，造成度数大的节点随着时间步的推移度数越来越大[14-15]。但是，实际网络中存在着一种如图1所示的常见现象，节点2和节点3具有较大度数，但它们的邻节点却都是度数很小的节点，而节点1虽然本身的度数很小，但它所连接的节点却都是度数较大的节点。在信息传播网络[16]、社交网络等现实网络中，节点1往往比节点2和节点3拥有更大的潜在影响力[17]，应当获得更大的连接概率。因此，按照BA网络或随机初始吸引度网络方法，仅仅只考虑节点本身的度数，极易忽略这类潜在的重要节点。

为了更好地模拟现实网络，凸显潜在的重要节点，就需考虑各节点的邻节点总度数，用L-i表示节点i的邻节点总度数，则：

3.3 改进的网络演化模型

基于邻节点总度数以及节点间不同的吸引关系，本文对BA无标度网络模型的构造规则进行修改，得到一种改进的演化模型，生成规则如下：

3.4 邻节点总度数数学分析

显然，方差越小，各节点度数与平均度数的偏离程度越小，{k-j}越稳定。所以当∑jL-j变小时，方差也随之变小，各节点度数间的差异也会变小。

通过上述分析可知，初始条件相同时，网络的邻节点总度数越小，则节点度数间的差异越小，连边的分布越均匀，网络的“贫富差距”程度越小。

4 实验与仿真

4.1 度分布

用MATLAB實现该算法，对改进后的网络模型进行仿真。设置初始参数m-0=3，m=3，N=3 000，考虑到节点区分度的随机性对最终结果带来的可能影响，始终令初始区分度因子β服从（0，1）的均匀分布。经过多次实验后，得到改进模型的度分布概率如图2所示，节点度为3的概率最大，之后呈现下降趋势，而度数超过10的节点概率都很小，趋近于0，此结果表明该模型服从幂律分布，属于无标度网络。

4.2 区分度因子β的影响

当保持初始参数值（m-0=3，m=3，N=1 000）不变时，使α、β分别服从（0，α-max）、（0，β-max）的均匀分布，多次实验后的结果取平均值，分别得到两种模型的节点度数最大值、最小度数节点占总节点数的比例随α-max、β-max的变化关系，如图3、图4所示。实验结果表明：同等规模的网络，对于较小的α-max，随机初始吸引度模型的节点度数最大值与度最小节点的比例变化较为明显，但随着α-max增大到一定程度后，它们几乎不再受α影响；而β的取值范围不断增大时，改进模型的节点度数最大值与度最小节点的比例都会逐渐下降，整个网络的“贫富差距”逐渐改善，但网络依旧服从幂律分布。这是由于随着网络规模的不断变大，随机因子对择优概率的影响逐渐减小，因此通过适当增大随机因子的取值范围可以使其影响力保持得更久。但随机初始吸引度模型的单方面吸引使α的早期节点获得更多的连接，模型的“贫富差距”仍然很大。本模型的双向选择性使得网络演化时连边的分布更加均匀，在需要重点考虑节点间相互作用的实际问题中，对β选择恰当的取值范围，可以实现对不同现实情况的模拟。

4.3 邻节点总度数比较

对于相同规模的初始全连通网络（m-0、m、N相同），BA模型、随机初始吸引度模型和本文模型最终的总度数相同，前两种模型中将节点分为大度数节点和小度数节点两类，而本文则从度数k-i和邻节点总度数L-i两方面考虑，这样节点大致分为4类：k-i大L-i大、k-i大L-i小、k-i小L-i大、k-i小L-i小，若忽略随机因子带来的影响，则第一类优先连接，第二类与第三类的择优概率视具体情况而定，第四类连接概率最小，从而使得BA模型中大度数节点的连边在本模型中会被潜在的重要节点（第三类）分走一些。因此，理论上本模型的连边分布会更加分散，即前两种模型的邻节点总度数之和普遍大于本模型。

令m-0=3，m=1，这样可以出现更多的潜在重要节点，为降低α、β的影响，令它们服从（0，1）的均匀分布，3种模型整体的邻节点总度数的平均值随网络规模N的变化关系如图5所示。图5结果表明：总体而言，本模型的邻节点总度数是最小的，说明网络中的潜在重要节点获得了更多的连边，从而使网络边的分布相对均匀，更符合现实情况。

5 结语

本文在传统BA无标度网络基础上，提出了以邻节点总度数和节点之间区分度为主要标准的无标度网络演化模型。通过赋予节点随机的区分度因子，使节点的自身特点更加突出，节点间的连接具有了双向选择性；用邻节点总度数代替节点本身的度数，使潜在重要节点得到了较大的连接概率，更加符合现实情况。根据实际情况，对模型中的参数进行适当设置，可以模拟多种现实网络，该模型为人们在更复杂的背景下模拟社会网络提供了参考。

参考文献：

[1] 孙立晟，何东之.改进无标度网络模型研究[J].电子设计工程，2016，24（6）：115-120.

[2] A L BARABASI，R.ALBERT. Emergence of scaling in random networks[J]. Science，1999，286（5439）：509-512.

[3] 马路，卢罡，郭俊霞.基于时变差别适应度的网络演化模型[J].计算机工程，2017，43（4）：94-99.

[4] 邓竞伟.基于随机初始吸引度的BA无标度网络演化模型研究[D].长春：东北师范大学，2009.

[5] DOROGOVTSEV S N，MENDES J F F，SAMUKHIN A N.Structure of growing networks with preferential linking[J]. Physical Review Letters，2000，85（21）：4633-4636.

[6] 郭鹏飞，张捷，吕明，等.无线通信网络的建模及故障传播[J].计算机工程与应用，2015，51（3）：1-5.

[7] STEFAN L，BJORN G，DIRK H. Scaling law s in the spatial structure of urban road networks[J]. Physica A，2006，363（1）：89-95.

[8] MEDINA MATTA I，BYERS J. On the origin of power laws in Internet topologies[J]. ACM SIGCOMM Comput Commun Rev，2000，30（2）：18-28.

[9] 竇炳琳，李澍淞，张世永.基于结构的社会网络分析[J].计算机学报，2012，35（4）：741-753.

[10] 朱志良，邱媛源，李丹程，等.一种Web服务复杂网络的构建方法[J].小型微型计算机系统，2012，33（2）：199-205.

[11] 彭俊，李智，孙雨.一种改进的无标度网络演化模型[J].航天制造技术，2008（1）：40-50.

[12] CHEN F，CHEN Z Q，WANG X F，et al. The average path length of scale free networks[J]. Communications in Nonlinear Science and Numerical Simulation，2008，13（7）：1405-1410.

[13] 刘文颖，蔡万通，张宁，等.基于加权网络拓扑熵的电网自组织临界状态演化[J].中国电机工程学报，2015，35（22）：5740-5748.

[14] 高鹏，胡剑波，魏高乐.变权重的城市轨道交通复杂网络鲁棒性分析[J].计算机仿真，2013，30（9）：153-156.

[15] 田田，吴俊，谭跃进.基于自然连通度的复杂网络抗毁性仿真优化研究[J].复杂系统与复杂性科学，2013，10（2）：88-94.

[16] 朱晓霞，刘萌萌，赵雪.复杂网络中的信息传播机制研究[J].情报科学，2017，35（5）：42-45.

[17] 赵之滢，于海，朱志良，等.基于网络社团结构的节点传播影响力分析[J].计算机学报，2014，37（4）：753-766.

（责任编辑：杜能钢）