改进HK网络演化模型的研究

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

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



改进HK网络演化模型的研究

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

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

摘要以HK网络模型为基础,提出了两个度分布与聚类系数均可调的改进HK网络模型。改进模型联合考虑“优先连接”、“三角结构”、“内部演化”等演化机制。在新节点加入时,分别考虑加入单个节点和社团的情况,将 TF 机理移到旧节点之间进行网络演化。仿真结果表明,两个改进模型不仅继承了HK模型的高聚类无标度特性,同时克服了HK模型演化过程中单一加入单个节点的方式及新旧节点之间TF机理的限制。

关键词HK模型;度分布;聚类系数

Research on and Modeling of the Improved HK Network Model

XU Yuzhu,ZHANG Damin,ZENG Cheng,SUN Yaqian

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

AbstractTwo improved HK network models based on the HK network model with adjustable degree distribution and clustering coefficient are proposed.The improved models jointly consider the evolution mechanisms of preferential attachment,triangle structure,and internal evolution.The mechanism of TF moved to old nodes in the evolution of network when a new node (a single node or a community) joins in the network.Simulation results show that the two improved models not only inherit the high clustering and scale free properties but also overcome the single way of node joint and the TF mechanism limit between new and old nodes.

KeywordsHK model;degree distribution;clustering coefficient

在复杂网络的研究历史上,匈牙利数学家Erdös和Rényi建立的随机图论奠定了复杂网络理论研究的基础[1]。随后,Watts和Strogatz提出的“WS小世界网络”揭示了复杂网络的小世界特征[2],聚类系数高、平均路径长度短。Barabási和Albert结合实际网络的特性,建立了兼具增长机制和优先连接特性的“BA无标度网络”[3-4],其节点的度服从幂律分布。然而实际网络几乎同时具备高聚类无标度特性。最早的高聚类系数无标度网络模型是 Holme-Kim(HK)模型,也是最具代表性的此类模型之一。HK模型以BA模型为基础,增加了一种TF(Triad Formation)的方法,以此改变原模型中加入的新节点均按照全局择优PA(Preferential Attachment)原则来选择旧节点进行加边的方式。这种改进不仅使得网络增长方式更灵活,也提高了聚类系数[5]。

但在HK模型的演化过程中,每个时间步加入的新节点n均产生相同的新边数m与网络中的已存在节点相连,且网络中新边的产生只存在于新、旧节点之间。实际上,边的演化机理更可能存在于旧节点之间,所以本文将TF机制移到了旧节点之间进行演化,使网络新边增长的同时存在于与新旧节点和旧节点之间。此外,网络增长除了单一的加入单个节点外,有时需要加入社团结构。本文考虑了加入单个节点和社团结构的情况,使之更符合实际网络模型。通过参数的调节,取消了产生新边数量固定的限制,成功解决了HK模型的不足[9,12]。

1三角机制内部演化网络模型

1.1三角机制内部演化网络模型的构建

HK网络模型以BA模型为基础,在BA网络具有无标度特征的基础上增加了网络聚类系数。HK网络模型演化机理如下:(1)每个时间步长,在网络中增加一个节点和m条边;(2)以PA步骤增加其中的一条边;(3)以概率p进行TF步骤或者以概率(1-p)进行PA步骤,增加其余的m-1条边[12]。

在HK模型的演化过程中,网络边的增长只存在于新加入节点与旧节点之间,然而,对比于实际网络,网络边的增长不仅存在于新旧节点之间,同时也存在于旧节点之间。例如现实网络中的交际网络,结交新朋友时,与朋友本身的交际面有关,交际面广的个体更容易结交到新朋友,即网络中度大的节点被连接的可能性更大;同时,没有新朋友加入的情况,个体也更容易与自己朋友的朋友成为朋友,即网络的内部演化。基于上述思想,提出的改进HK网络模型1就克服了HK网络模型的这个缺点,改进模型1演化机理如下:(1)初始网络。初始网络中有m0个完全连接的节点;(2)网络增长。按照概率p,网络中增加一个新节点和m条边,p∈[0,1]。

根据择优概率,选择网络中1个旧节点与之相连,使新加入节点与网络中的旧节点之间具有1条边。连接节点的选择按照如下的择优概率进行,即网络中一个旧节点i被选择的概率∏(ki)为

(1)

其中,ki为节点的度,该式表示新节点的加入更倾向于选择网络中度较大的节点。α为可调因子,其中α∈(0,1)。

其余m-1条边,以概率1-∏(Ci)做三角形连接,∏Ci做择优概率连接。其中

(2)

其中,C为节点的聚类系数,该式表明新入节点更倾向于与网络中聚类系数小的节点进行三角连接,从而增加整个网络的聚类系数。

(3)网络内部演化。按照概率1-p选择网络中已存在节点做内部演化。随机选择网络中一个节点i,以择优概率选择节点i的邻居节点j,其中连接概率按照∏(kj)选择,再以概率1-∏Ci选择节点j的邻居节点k与节点i做连接。其中

(3)

N(i)为选中旧节点i的邻居节点集合。

在改进模型1中,当概率p=0时,网络中没有新节点的加入,没有节点规模的增长,网络边的增加仅发生在旧节点之间,旧节点之间进行内部演化加边。当时,每个时间步长,网络中既可能有新节点的加入,同时增加网络的节点与边,也有网络的内部演化加边,且随着p值的增加,演化过程中节点增长机制所占的比重越来越大。当概率p=1时,网络中旧节点之间不进行内部演化加边,每个时间步长有一个新节点加入网络。概率p=1时的这种情况在实际网络中不太会出现。

1.2仿真结果及分析

HK网络模型是最具代表性的高聚类系数无标度小世界模型,HK网络模型节点度分布服从幂律分布,幂律指数稳定在。改进HK网络模型1继承了HK网络模型节点度分布服从幂律分布这一特征,且由于参数p的不同,幂律指数可在2～3之间变化。

设定参数m=4和α=1,通过模拟实验分别研究网络规模N=3 000和N=5 000时,概率p对网络节点度分布的影响。

图1和图2给出了网络节点为3 000和5 000,p分别为0.2与0.4时,改进模型1度分布的比较。由图可知,网络节点度分布服从幂律分布,参数p可调整幂率指数在2~3之间变化,更符合实际网络的特性。

图1　p=0.2,改进模型1的度分布

图2　p=0.4,改进模型1的度分布

以前众多网络模型在增长过程中只考虑优先连接机制,造成网络模型聚类系数较小。如传统的BA网络,聚类系数趋近于0,这并不符合现实网络的结构特点,许多实际大规模网络满足无标度特性的同时聚类系数也较高。

设定固定参数m=4,α=1,p=0.4,通过模拟实验研究网络规模N对聚类系数的影响,实验结果如图所示。

图3　N=300或500,改进模型1的聚类系数分布

图4　N=3 000或5 000,改进模型1的聚类系数分布

网络中度较大的节点聚类系数较小,度小的节点反而聚类系数较大,表明度小的节点之间相互连接更为紧密。如图所示,网络规模在1 000以内时,聚类系数集中在0.5附近,网络规模扩大到3 000或5 000时,聚类系数下降到0.1附近。网络规模增加,聚类系数下降,呈负相关。当网络规模<1 000,聚类系数下降速度最快,随着网络节点数增加,下降速度变平缓。最终,聚类系数趋于一个≪1的非零常数。数值分析结果表明,网络的聚类系数被大幅提高。

2新增社团结构网络优化模型

2.1新增社团结构网络优化模型的构建

HK网络模型的增长仅考虑了单一新节点的加入。类比于社会网络,某个成员加入网络后,往往意味着整个社团都成为网络的一个新成员。基于上述思想,提出的改进HK网络模型2使得加入网络的节点情况从单一节点变为加入一个社团结构,改进模型2演化机理如下:(1)初始网络。初始网络中有m0个完全连接的节点;(2)网络增长。按照概率p,网络中加入一个节点数为n的小型社团结构和m条边,其中p∈[0,1]。

随机选择新加入社团结构中一个节点v,并按照∏(ki)选择网络中1个旧节点与节点v相连,使新加入节点v与网络中的旧节点之间具有1条边。连接节点的选择按照如下的择优概率进行,即网络中一个旧节点i被选择的概率∏(ki)为

(4)

其中,ki为节点的度,该式表示新节点的加入更倾向于选择网络中度较大的节点;α为可调因子,其中α∈(0,1)。因为所加入的社团结构为全连接,所以当社团中一个节点被加入网络后,意味着其余的n-1个节点也同时被加入到网络中。其余m-1条边,以概率1-∏(Ci)做三角形连接,∏Ci做择优概率。其中概率

(5)

其中,C为节点的聚类系数,该式表明新入节点更倾向于与网络中聚类系数小的节点进行三角连接,从而增加整个网络的聚类系数。

当概率p=0时,网络中没有新社团的加入,没有新节点增长仅有旧节点间演化加边。当时,每个时间步长,网络中既可能有新社团的加入,同时增加网络的节点与边,也有网络的内部演化加边,即随着p的增加,网络中社团结构的增长机制所占比重越来越大。当概率p=1时,网络中旧节点之间不进行内部演化加边,每个时间步长有一个新社团加入网络,然而概率p=1的情况在现实网络中不太会出现。

2.2仿真结果及分析

改进HK网络模型2继承了HK网络模型节点分布服从幂律分布,且可调节参数p,从而条件幂律指数在2～3之间变化,打破了HK网络幂律指数γ≈3的限制。

设定参数m=4和α=1,通过模拟实验分别研究网络规模N=3 000和N=5 000时,概率p对网络节点度分布的影响。

图5和图6分别给出了网络节点为3 000和5 000,p分别为0.2与0.4时,改进模型2度分布的比较。由图可知,网络节点度分布服从幂律分布,参数p可调整幂率指数在2~3之间变化,更符合实际网络的特性。

图5　p=0.2,改进模型2的度分布

图6　p=0.4,改进模型2的度分布

设定固定参数m=4,α=1,p=0.4,通过模拟实验研究网络规模N对聚类系数的影响,实验结果如图所示。

图7　N=300和N=500,改进模型2的聚类系数分布

图8　N=3 000和N=5 000,改进模型2的聚类

如图所示,网络规模在1 000以内时,聚类系数集中在0.6附近,网络规模扩大到3 000或5 000时,聚类系数下降到0.2附近。网络规模增加,聚类系数下降,呈负相关。当网络规模<1 000时,聚类系数下降速度最快,随着网络节点数增加,下降速度变平缓。最终,聚类系数趋于一个≪1的非零常数。数值分析结果表明,网络的聚类系数被大幅提高。

3结束语

针对现实世界中诸多大规模的网络均同时具有小世界与无标度网络特性,即网络的度分布服从幂率分布,同时聚类系数有较高的特点。本文在HK网络模型的基础上,提出一类包含“优先连接”,“三角结构”,“内部演化”等演化机制的改进的高聚类系数无标度网络模型1和网络模型2。在模型演化规则中,以概率p增加单个节点或增加一个社团结构,以概率1-p不增加新节点或社团结构,仅选择网络内部节点做网络内部演化加边。该网络模型的拓扑结构和度分布、聚类系数均随时间的变化而不断演化,使网络模型更加贴近于现实网络。本文对度、聚类系数的统计特性进行数值模拟,研究不同节点个数的演化网络结构特性。仿真结果表明,这两种改进模型不仅继承了HK网络模型高聚类无标度的特点,且度分布与聚类系数分布是参数可调的,更符合现实网络特征。

参考文献

[1]Erdos P,Renyi A.On random graphs[J].Publ Math,1959,6(6):290-297.

[2]Watts D J,Strogatz S H.Collective dynamics of small-world networks[J].Nature,1998,393(3):440-442.

[3]Barabasi A L,Albert R,Jeong H.Mean-field theory for scale-free random networks[J].Physica A,1999,272(2):173-187.

[4]Barabási A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286(6):509-512.

[5]李稳国,王力虎,陈明芳.HK网络演化模型的研究和改进[J].计算机工程,2009,35(3):121-122.

[6]卓越.两层复杂网络上的动态权重路由策略研究[J].计算机应用研究,2011,28(9):3411-3413.

[7]王翠君,王红.复杂网络的研究进展综述[J].科技信息,2007(31):417-418.

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

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

[10]刘建香.复杂网络及其在国内研究进展的综述[J].系统科学学报,2009,17(4):31-37.

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

[12]王丹,井元伟,郝彬彬.扩展HK网络结构与同步能力的研究[J].物理学报,2012,61(22):154-161.

[13]王丹,郝彬彬.一类高聚类系数的加权无标度网络及其同步能力的分析[J].物理学报,2013,62(22):1-8.

中图分类号TP393

文献标识码A

文章编号1007-7820(2016)03-106-04

doi:10.16180/j.cnki.issn1007-7820.2016.03.027

作者简介:徐玉珠(1992—),女,硕士研究生。研究方向:数字通信与通信系统。张达敏(1967—),男,博士,教授,硕士生导师。研究方向:计算机应用技术等。

基金项目:贵州省省委组织部基金资助项目(TZJF-2011-37);贵州省合作计划基金资助项目(【2012】7002号);贵州大学研究生创新基金资助项目(研理工2015078)

收稿日期:2015- 09- 28