基于betweenness centrality提高复杂网络容量的方法

《基于betweenness centrality提高复杂网络容量的方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2006全国复杂网络学术会议（CCCN’06）论文集基于BetweennessCentrality提高复杂网络容量的方法范晶1,2秦卓琼1,2张国强1,2张国清1（1.中国科学院计算技术研究所北京100080）（2.中国科学院研究生院北京100080）摘要：BetweennessCentrality能够刻画节点在网络中的重要程度，能够反映节点在网络中可能承载的网络流量。本文引入BetweennessCentrality对网络拓扑进行优化和拥塞预测，通过理论分析和仿真实验，提出在具有scale-free特征的复杂网络中，依据Betweenness值以及Betwee

2、nness的标准差增加一些捷径路径的方法，有效平衡中枢节点的负载，缓解拥塞状况，提高网络容量。关键词：BetweennessCentrality，网络拓扑，网络容量，拥塞，无标度网络AMETHODFORIMPROVINGCOMPLEXNETWORKCAPACITYBASEDONBETWEENNESSCENTRALITYFanJing1,2QinZhuoqiong1,2ZhangGuoqiang1,2ZhangGuoqing1(1.InstituteofComputingTechnology,ChineseAcademyofScienceBeijing100080

3、)(2.GraduateUniversityofChineseAcademyofScienceBeijing100080)ABSTRACT:TheBetweennessCentralityindexisadirectmeasureofmessagetraffic.HighBetweennessCentralityscoresindicatethatavertexliesonconsiderablefractionsofshortestpathsconnectingothersanditplaysanimportantroleinthenetwork.Theind

4、exisintroducedheretooptimizenetworktopologyandidentifynodeswhicharemostlikelytocausecongestion.Weproposesomemethodsaftertheoreticalanalysisandexperimentstoaddsomeshortcutsinscale-freenetworksaccordingtoBetweennessandthevariationofBetweenness.Thiscanbalanceloadamongthecorenodes,reliev

5、econgestionefficientlyandincreasethecapacityofthenetworksubstantially.Keywords:BetweennessCentrality,networktopology,networkcapacity,congestion,scale-freenetwork2006全国复杂网络学术会议（CCCN’06）论文集1引言随着互联网的普及和发展，各种新兴的Internet业务不断涌现，上网的计算机数和网站数迅猛增长，在网络使用高峰时段，大多数网络都会出现拥塞，服务质量下降。网络拥塞受很多因素影响，例如节点的

6、容量、链路的带宽、网络路由协议还有网络拓扑。为了获得令人满意的服务质量，缓解拥塞状况，大多数网络运营决策人员会选择扩容或者更换网络设备，而很少尝试对已有的网络拓扑作些小小的改变来提高网络性能[1]。而事实上系统的动态特征（网络流量）和网络的静态结构（网络拓扑）关系非常密切[2]，网络拓扑结构是影响网络负载分布的主要因素之一。BetweennessCentrality（简称Betweenness）的概念源于分析社会网络中个体的重要性[3]。简单地讲，一个节点的Betweenness表示所有的节点对之间通过该节点的最短路径条数。Betweenness很好地描述了一个

7、网络中节点可能需要承载的流量。一个节点的Betweenness越大，流经它的数据分组越多，意味着它更容易拥塞，成为网络的瓶颈。在早期的网络拓扑模型的研究中，网络拓扑模型通常采用完全随机图模型，认为网络中的节点度大致相同，呈正态分布。近期的研究表明Internet的网络节点度呈幂律分布，具有这种特征的网络就被称之为无标度（scale-free）网络。大多数节点度较小，而一小部分节点则节点度很大，通常称之为中枢节点。中枢节点的Betweenness就往往很大，一旦中枢节点崩溃，整个网络就面临瘫痪的危险，所以平衡整个网络的流量来提高系统容量对符合scale-free特

8、征的网络尤为必要。文[1