聚类系数大小及分布可调的BBV网络演化模型

孙雅倩，张达敏，曾　成，徐玉珠

(贵州大学 大数据与信息工程学院,贵州 贵阳 550025)

摘　要：在传统BBV模型的基础上，提出了一种改进的BBV网络演化模型。基本思想是改变网络增长过程中新节点加入时，新旧节点的连接方式及优先选择概率。该模型不仅可以调节无标度加权网络度和强度的分布，还可以通过改变“三角形”连接概率公式中系数的大小，增大网络的聚类系数并调节网络聚类系数的分布。即根据实际需要，大范围调节网络度分布，精确调节聚类系数大小及分布，其生成机制更符合实际网络的演化过程。

关键词：BBV演化模型;度分布;聚类系数

doi:10.3969/j.issn.1002-0802.2015.06.013

聚类系数大小及分布可调的BBV网络演化模型

孙雅倩，张达敏，曾成，徐玉珠

(贵州大学 大数据与信息工程学院,贵州 贵阳 550025)

摘要：在传统BBV模型的基础上，提出了一种改进的BBV网络演化模型。基本思想是改变网络增长过程中新节点加入时，新旧节点的连接方式及优先选择概率。该模型不仅可以调节无标度加权网络度和强度的分布，还可以通过改变“三角形”连接概率公式中系数的大小，增大网络的聚类系数并调节网络聚类系数的分布。即根据实际需要，大范围调节网络度分布，精确调节聚类系数大小及分布，其生成机制更符合实际网络的演化过程。

关键词：BBV演化模型;度分布;聚类系数

doi:10.3969/j.issn.1002-0802.2015.06.013

收稿日期：2015-01-21；修回日期：2015-04-28Received date:2015-01-21；Revised date：2015-04-28

基金项目：贵州省省委组织部项目(TZJF-2011-37)；贵州省合作计划项目([2012]7002号)；贵州大学研究生创新基金项目(研理工2015078)Foundation Item:Cooperative Project of Guizhou Province(TZJF-2011-37); Cooperative Project of Guizhou Privince([2012]7002);Graduate Student Innovation Foundation of Guizhou University

中图分类号：TP393

文献标志码：码：A

文章编号：号：1002-0802(2015)06-0692-07

Abstract：Based on the traditional BBV model, an improved BBV model is proposed. The main idea is to change the connecting way of between new nodes and old nodes and the probability of priority selection when a new node joins the network in the growth process. This model could adjust the distribution of degree and strength of the weighted scale-free network while increase clustering coefficient of the network and tune the distribution of clustering coefficient by changing the coefficient in “triangle”connection probability formula. To adjust the distribution of degree in a big way and accurately tune the clustering coefficient and its distribution in accordance with actual needs, this generation mechanism is more accordant with the actual network evolution.

作者简介：

An Evolution Model of BBV Network with Tunable Clustering

Coefficient and Distribution

SUN Ya-qian,ZHANG Da-min,ZENG Cheng,XU Yu-zhu

(School of Big Data and Information Engineering of Guizhou University,Guiyang Guizhou 550025,China)

Key words：BBV evolution model; distribution of degree; clustering coefficient

0引言

随着时代发展，复杂网络研究正渗透到我们生活中的各个领域。对于实际生活中的网络来说，每个节点和边的重要性并不相同，为了描述边的异质性，Yook等人提出了一个初步的加权网络理论模型[1]，给网络的边赋上了权值。该模型是在无权网络的基础上首次对加权的网络演化模型理论进行了研究。后来，Barrat,Barthelemy和Vespignani提出了著名的BBV模型[2]，该模型综合考虑点强度与边权值加强机制，BBV模型的动态演化利用权驱动方式得以实现[3-4]，该模型的提出掀起了加权网络的研究热潮。

随着无标度加权网络受到越来越多学者们的重视，一些改进的加权无标度网络模型相继被提出[5-10]。其中,很多学者围绕着调节网络度分布和聚类系数大小做深入研究，在度分布的调节上主要是在权重优先选择概率公式中引入调节系数，在聚类系数的调节上以加入三角形连接方式为主[5,9,10]。本文借鉴在BBV网络中加入三角形连接方式和在权重优先选择概率公式中引入调节系数的思想，通过在新节点加入时引入一个由当前节点聚类系数和当前网络平均聚类系数组成的概率公式来决定是否进行三角形连接，加入一个调节系数，改变系数大小可以调节网络进行三角形连接的概率，并对网络中每个节点的聚类系数大小进行控制，使聚类系数的分配相对灵活。

实际生活中的网络种类繁多，不同网络具有不同的统计特性。例如：电力网、国际航空网的度分布在双对数坐标下较幂率分布更为均匀[11]，在线社会网，经济网，科学合作网等具有较大的聚类系数[12]，而传统BBV模型的度及强度严格服从幂率分布，且聚类系数较小。由此可见，我们改进的BBV网络模型需具备更高的灵活性。本文共引入3个调节系数，通过对这3个系数的合理调节，可以模拟构造多种类型的实际网络，具有高度灵活性。

1网络演化模型

模型演化基础：结合王丹等人提出的将三角形连接机制引入到BBV模型的方法以及潘灶烽、汪小帆提出的GBBV模型的生成方法，在网络模型进行“三角形”演化的过程中，将当前网络的平均聚类系数和当前节点的聚类系数综合考虑进来，即根据当前网络和当前节点的聚类系数大小来确定加入的新节点是进行三角形连接还是做权重优先选择连接。

本文提出的网络模型演化机理如下：

步骤1：设定初始网络：初始网络是一个由m0个节点组成，节点之间随机连接一些边的网络。网络中每条边的权值均设为w0，因此每个节点的强度为:

(1)

步骤2：增长：每次引入一个新节点，与已经存在的m个节点相连，直至达到所设定的网络节点数，即网络规模N。

步骤3：择优原则：网络增长过程中，每引入一个新节点n后，以概率:

(2)

选择一个旧节点i与新加入的节点n连接。si为当前节点i的强度，a是调节系数。a越小，每个旧节点被选中的概率就越接近，网络的度分布也就越均匀。当a=1时，就退变成传统BBV网络中的强度优先选择概率。

步骤4：执行步骤3后，再以概率:

(3)

三角形连接机制：如果按照步骤3选择的下一步是三角形连接，则从旧节点i的邻居节点中以概率 :

(4)

选择一节点与新节点n相连。这里的选择概率原则和步骤3的优先原则同出一辙，但此处的系数g对整个网络度分布的影响力度比a小，主要作用是辅助f调节聚类系数。需要注意的是，若节点i没有邻居节点，则按照步骤3的原则增加下一条边。

网络赋权原则依旧按照BBV网络的权重赋予原则进行，具体演化过程如下：

网络中加入的新边赋权值大小为w0,加入的新边(n,i)会引起被连接的旧节点i与其邻居节点j∈Γ(i)之间的边权值发生变化。变化规则规定为：

wij→wj+Δwij

(5)

(6)

由于引入新边(n,i)会给节点i增加流量负担，跟节点i连接的其他边，会根据自己的权值wij的大小来帮助节点i分担流量。此时，节点i的强度调整为：

si→si+δ+wo

(7)

2仿真结果分析

在仿真实验中，初始网络大小m0=10，并取m=6,w0=2，网络规模N=5 000。我们主要对网络的强度分布，度分布，聚类系数的大小及分布进行讨论。需要注意的是，在加权无标度网络中，节点度分布及强度分布是两个重要的统计特征。节点的强度反应了该节点的重要程度，传输能力等。度和强度的分布均能反映网络模型的特性。聚类系数反映的是网络节点的聚集性[12]，可以衡量网络的集团化程度和连通性等等。

2.1传统BBV网络特性分析

用传统BBV网络的生成方式生成网络模型，网络节点的度分布，强度分布，度与强度的关系以及度-聚类系数关系如图1所示。

(a)节点强度的分布图

(b)度分布图

(c)度-强度变化关系

(d)度-聚类系数相关图

生成的网络聚类系数为：0.064 253，从实验数据我们可以看出，度与强度之间呈线性关系,传统的BBV网络聚类系数非常小，节点的强度以及度分布均是严格的幂率分布，且幂指数固定不变，这不仅不能完全反映真实网络的特性，并且构造的网络模型种类单一，灵活性较差。

2.2改进模型中各个系数对网络特性的影响

在新节点与旧节点连接时的强度优先选择概率公式中引入系数a,当a取不同值时对应的节点强度分布,度分布,度与强度的关系如图2所示。

(a)节点强度的分布图

(b)度分布图

(c)度-强度变化关系

运行程序得出，a=0.2，a=1，a=3时网络的聚类系数分别为0.002 613 8，0.079 82，0.999 17。图2中的(c)图表明，系数a的引入并未改变节点度与强度之间的关系，而大多数真实网络度与强度正符合这种线性关系[1]。分析图2(b)发现，a=0.2时，网络节点的度接近指数分布，原因是网络中每个旧节点被新节点连接的概率接近相等，这意味着网络中的度分布比较平均，这点从图2(c)可以看出。而a的值越大，强度大的旧节点被连接的概率就越大，大部分节点的度将变小，少数节点的度会很大。但a的值无论大小，网络的强度分布都服从幂率分布，改变的只是分布指数。而对于度分布来说，当a的值越来越小时，其度分布会逐渐趋于扩展指数分布，该实验结果符合前人研究所得的结论。需要注意的是，a=0.5是度分布从扩展指数分布过度到幂率分布的分界值[11]。

上述实验发现，引入参数a后，仅仅对调节节点的度及强度分布有意义，却无法准确调节网络的聚类系数，一些研究人员通过三角形连接的方式来增大网络的聚类系数，并得到较为满意的结论。但传统的三角形连接方式，虽然可以调节聚类系数大小，却没有考虑到当前节点和当前网络的聚类系数大小关系，从而无法精确调节聚类系数的分布。本文提出的网络模型生成方法中，当网络中加入新节点时，先根据强度优先概率选出一个旧节点与之连接，之后根据当前旧节点的聚类系数和整个网络的聚类系数大小情况以一定概率进行三角形连接，此概率公式中引入了一个系数f. 在进行三角形连接时，当前节点将从自己的邻居节点中以概率k=s(j)g/sum(s(j)g)选择一个自己的邻居节点与新节点相连。此处，先讨论改变系数f对网络度分布、强度分布、聚类系数大小的影响，实验结果如图3所示。

(a)节点强度的分布图

(b)度分布图

图3是在系数a=1，g=1时，探究系数f对网络基本特性的影响。运行程序后得到，当f=0.2,f=1,f=3时对应的聚类系数大小分别为0.290 44,0.456 65,0.564 4。聚类系数比同等规模下的传统无标度网络高出数倍。从图3可以看出，系数f无论怎么变化网络节点的度及强度分布依旧服从幂率分布，也就是说系数f的大小对度和强度的分布影响不大。

系数g的作用是，当a的值不变时，可以微调度分布，且对聚类系数大小也有影响，a,g,f这3个系数合作可以大范围精确的调节网络的度分布，聚类系数大小和和聚类系数大小分布。

(a)节点强度的分布图

(b)度分布图

运行程序后得到，g=0.1,g=1和g=3时对应的聚类系数大小分别是，0.203 83,0.467 71,0.221 57。从实验结果可以看出，g的取值无论大小，网络的度分布及强度分布均服从幂率分布，当a和f的值为1时，g的值增大或减小都会使得聚类系数减小，而且波动范围较大。当a和f的值固定时，调节g的值可以改变聚类系数，因此，如果想得到聚类系数大小和度分布可以任意调整的网络模型，只要协调好a,f,g这3个系数的大小即可。

以上实验结果是验证各系数对整个网络强度分布，度分布及聚类系数大小的调节。接下来讨论引入系数f对聚类系数分布的影响。图5是在系数a=0.5,g=0的前提下实验得出的结果。

图5　引入系数f对网络聚类系数分布的影响

图5中显示的实验结果表明，在系数a和g的值固定不变的情况下，系数f取不同值会得到不同的网络聚类系数分布。当系数f取值较小时，三角形连接概率会很小。因此，网络中各个节点的聚类系数都较小，大多分布在0.01左右，且a=0.5时网络度分布较均匀，聚类系数分布也就相对均匀。调节f的值，此处取f=1,可以增大网络的聚类系数，还可以使聚类系数和度的相关图整体趋势近似于幂率分布。可见，调节系数f可以有效控制网络聚类系数的大小和聚类系数的分布。

2.3改进模型实用性研究及系数选择原则

图6是给系数a,f,g赋上不同值时得到的相应特性图，不同特性可以描述不同类型的网络，从而说明此模型生成方法的灵活性和实用性。

(a)节点强度的分布图

(b)度分布图

(c)度-聚类系数相关图

这三组数据从上到下所对应的聚类系数大小分别是：0.714 6、0.138 34、0.421 87。从图中可以看出，这几组数据得到的度分布以及强度分布均符合幂率分布特性，不同之处主要在于网络聚类系数大小及聚类系数与度的关系分布。分析发现，a=0.5,f=5,g=3和a=1,f=3,g=1这两组系数所生成网络的度和聚类系数相关图具有平头特征，而多种真实网络都具有这一特征[13-14]。前者可以描述校园人际关系网等网络。该类网络特点是：强度分布和度分布服从幂率分布特征，幂指数较大，整个网络的平均聚类系数很大且聚类系数和度的相关性会具有“平头”特征[9]，大多数节点的聚类系数聚集在某一范围内，这是因为同学之间大多互相认识，尤其是人际关系圈子较小的同学，其认识的人互相认识的可能性更大。后者适合描述类似于Internet网络中自治层等类型的真实网络[9]。a=0.5,f=1,g=0时所对应的聚类系数与度的相关图近似服从幂率分布，此时的模型适合描述集群现象比较突出的网络。

真实网络都拥有自身的结构特点，而传统BBV网络仅限于描述度、强度和聚类系数均服从幂率分布的网络，却无法描述图2和图6中显示的度分布均匀和聚类系数分布具有“平头”特征的网络。可见，改进的演化模型可通过调节这三个系数的大小，适应更多网络类型。

结合2.2节的仿真结果，规定系数选择原则如下：

当a=1，f=0时，该模型就变为传统BBV模型，此时用于描述度分布，聚类系数分布均服从幂率特性且聚类系数较小的网络。当a<0.5,f>1,g>0时，该模型适于描述度分布较均匀，聚类系数较大且分布具有“平头”特征的网络，使a>0.5，f和g的取值范围不变，则网络的聚类系数特性依旧不变，网络度分布服从幂率特性，若要想聚类系数分布也服从幂率特性特性可使g=0。

3结语

本文仅把网络的度分布，强度分布及聚类系数几个复杂网络的基本特性作为出发点，但实际中的网络更为复杂，且需要考虑多方面因素，生成模型方法还需要进一步完善。此外，本文或许存在不妥之处，还望各位专家和学者们批评指正。

参考文献：

[1]Yook S H，Jeong H，Barabási A L. Weighted Evolving Networks[J]. Physical Review Letters，2001，86(25):5835-5838.

[2]Barabási A L，Barthelemy M，Vespignani A. Weighted Evolving Networks:Coupling Topology and Weight Dynamics[J]. Physical Review Letters，2004，92(22):228701.

[3]杨珉，张家玥，张达敏. 复杂网络拓扑结构的网络模型研究综述[J].通信技术，2014,47(12):1354-1359.

YANG Min, ZHANG Jia-yue, ZHANG Da-min. Review of Complex Networks Topology Structure and Network Models Research[J]. Communications Technology, 2014,47(12):1354-1359.

[4]王翠君,王红. 复杂网络的研究进展综述[J].计算机与信息技术,2007(31):417-418.

WANG Cui-jun, WANG Hong. Research Progress Outline of the Complex Network .[J]. Science & Technology Information, 2007(31):417-418.

[5]潘灶烽，汪小帆.一种可大范围调节聚类系数的加权无标度网络模型[J].物理学报,2006,55(08):4058-4064.

PAN Zao-feng, WANG Xiao-fan. A Weighted Scale-free Network Model with Large-Scale Tunable Clustering.[J]. ACTA Phys Sin,2006,55 (08): 4058-4064.

[6]ZHOU Jian,LI Shi-wei,CHENG Ke-qin.BBV Weighted Network Evolving Model Reseach based on Local World[J]. Computer Engineering and Applications,2011,47(14),95-98.

[7]李稳国,邓曙光,崔治等.可调路径长度和簇系数的加权无标度网络模型研究[J].湖南城市学院学报: 自然科学版,2011,20(02):60-62.

LI Wen-guo, DENG Shu-guang, CUI Zhi,et al . Growing Weighted Scale-Free Network with Tunable Length and Clustering Coefficient[J]. Journal ofHunan City University，2011,20(02):60-62.

[8]逯鹏,张姗姗,高庆一.基于共同邻居的点权有限BBV模型研究[J].计算机科学，2014,41(04):49-52.

LU Peng, ZHANG Shan-shan, GAO Qing-yi.Research on BBV Mode with Limited Node Strength based on Common Neighbors[J].Computer Science,2014,41(04):49-52.

[9]王丹,金小峥.可调聚类系数加权无标度网络建模及其拥塞问题研究[J].物理学报，2012，61(22)：228901.

WANG Dan, JING Xiao-zheng .On Weightd Scale-Free Network Model with Tunable Clustering and Congestion[J]. Acta Phys Sin，2012，61(22)：228901.

[10]刘慧，李增扬，陆君安.局域演化的加权网络模型[J].复杂系统与复杂性科学，2006,3(01)：36-43.

LIU Hui, LI Zeng-Yang, LU Jun-an.Weighted Scale-Free Network Model with Evolving Local-World[J].Complex Systems and Complexity Science,2006,3(01):36-43.

[11]彭俊，李智，孙雨.一种改进的无标度网络演化模型[J]. 计算机应用，2008,02(01)：40-50.

PENG Jun，LI Zhi ,Sun Yu. An Improved Scale-free Network Evolution Model [J].Jounarl of Computer Applications, 2008,02(01)：40-50.

[12]胡海波, 王科, 徐玲等. 基于复杂网络理论的在线社会网络分析[J]. 复杂系统与复杂性科学, 2008, 05(02): 1-14.

HU Hai-bo , WANG Ke,XU Ling，et al.Analysis of Online Social Networks based on Complex Network Theory[J].Complex Systems and Complexity Science,2008,05(02):1-14.

[13]AlbertRéka，Jeong Hawoong，Barabási Albert-László. Internet: Diameter of the World-Wide Web[J].Natuure,1999,401(6749):130-131.

[14]Ravasz Erzsébet, Barabási Albert-László.Hierarchical Organization in Complex Networks [J]. Physical Review E, 2003,67(02):026112.

孙雅倩(1990—)，女，硕士研究生，主要研究方向为复杂网络；

张达敏(1967—)，男，教授，主要研究方向为计算机应用技术、网络拥塞控制、病毒传播机制;

曾成(1989—)，男，硕士研究生，主要研究方向为复杂网络；

徐玉珠(1992—)，女，硕士研究生，主要研究方向为复杂网络。

术语百科Technical Terms

计算智能

计算智能(CI，Computational Intelligence)是受到大自然智慧和人类智慧的启发而设计出的一类算法的统称。典型的计算智能算法有神经计算中的人工神经网络算法，模糊计算中的模糊逻辑，进化计算中的遗传算法、蚁群优化算法、粒子群优化算法、萤火虫群优化算法，以及单点搜索优化中的模拟退火算法等。作为人工智能的一个重要领域，计算智能因其智能性、并行性和健壮性，具备了很好的自适应能力和很强的全局搜索能力。在科学研究和工程实践中，对于遇到的一些NP(Non-deterministic Polynomial)难问题，计算智能算法可以在求解时间和求解精度上取得平衡。这些算法或模仿生物界的进化过程，或模仿生物的生理构造和身体机能，或模仿动物的群体行为，或模仿人类的思维、语言和记忆过程的特性，或模仿自然界的物理现象，通过模拟大自然和人类的智慧实现对问题的优化求解，在可接受的时间内求解出可以接受的解。 目前，计算智能已经在算法理论和算法性能方面取得了很多突破性的进展，并且已经在通信网络、优化计算、模式识别、图像处理、自动控制、经济管理、生物医学等许多领域取得了成功的应用。