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

2006全国复杂网络学术会议（CCCN06）论文集基于Betweenness Centrality提高复杂网络容量的方法范晶1, 2 秦卓琼1,2 张国强1,2 张国清1（1. 中国科学院计算技术研究所 北京 100080）（2. 中国科学院研究生院 北京 100080）摘 要：Betweenness Centrality能够刻画节点在网络中的重要程度，能够反映节点在网络中可能承载的网络流量。本文引入Betweenness Centrality对网络拓扑进行优化和拥塞预测，通过理论分析和仿真实验，提出在具有scale-free特征的复杂网络中，依据Betweenness值以及Betweenness的标准差增加一些捷径路径的方法，有效平衡中枢节点的负载，缓解拥塞状况，提高网络容量。关键词：Betweenness Centrality，网络拓扑，网络容量，拥塞，无标度网络A METHOD FOR IMPROVING COMPLEX NETWORK CAPACITY BASED ON BETWEENNESS CENTRALITYFan Jing1, 2 Qin Zhuoqiong1, 2 Zhang Guoqiang1, 2 Zhang Guoqing1 (1. Institute of Computing Technology, Chinese Academy of Science Beijing 100080) (2. Graduate University of Chinese Academy of Science Beijing 100080)ABSTRACT: The Betweenness Centrality index is a direct measure of message traffic. High Betweenness Centrality scores indicate that a vertex lies on considerable fractions of shortest paths connecting others and it plays an important role in the network. The index is introduced here to optimize network topology and identify nodes which are most likely to cause congestion. We propose some methods after theoretical analysis and experiments to add some shortcuts in scale-free networks according to Betweenness and the variation of Betweenness. This can balance load among the core nodes, relieve congestion efficiently and increase the capacity of the network substantially. Key words: Betweenness Centrality, network topology, network capacity, congestion, scale-free network1 引言随着互联网的普及和发展，各种新兴的Internet业务不断涌现，上网的计算机数和网站数迅猛增长，在网络使用高峰时段，大多数网络都会出现拥塞，服务质量下降。网络拥塞受很多因素影响，例如节点的容量、链路的带宽、网络路由协议还有网络拓扑。为了获得令人满意的服务质量，缓解拥塞状况，大多数网络运营决策人员会选择扩容或者更换网络设备，而很少尝试对已有的网络拓扑作些小小的改变来提高网络性能1。而事实上系统的动态特征（网络流量）和网络的静态结构（网络拓扑）关系非常密切2，网络拓扑结构是影响网络负载分布的主要因素之一。Betweenness Centrality（简称Betweenness）的概念源于分析社会网络中个体的重要性3。简单地讲，一个节点的Betweenness表示所有的节点对之间通过该节点的最短路径条数。Betweenness很好地描述了一个网络中节点可能需要承载的流量。一个节点的Betweenness越大，流经它的数据分组越多，意味着它更容易拥塞，成为网络的瓶颈。在早期的网络拓扑模型的研究中，网络拓扑模型通常采用完全随机图模型，认为网络中的节点度大致相同，呈正态分布。近期的研究表明Internet的网络节点度呈幂律分布，具有这种特征的网络就被称之为无标度（scale-free）网络。大多数节点度较小，而一小部分节点则节点度很大，通常称之为中枢节点。中枢节点的Betweenness就往往很大，一旦中枢节点崩溃，整个网络就面临瘫痪的危险，所以平衡整个网络的流量来提高系统容量对符合scale-free特征的网络尤为必要。文1中指出在度分布具有Bi-Modal特征、拓扑结构较为规则的网络中，单单增加这类Betweenness较大的节点的容量只能很小程度地减小拥塞，要想有效地避免拥塞，必须大幅度增大节点容量，而这必然花费相当高的成本。然而在Betweenness较大的前5个节点间增加连接，同时适当增加节点的容量，则会大幅度提高网络容量，如果在Betweenness较大的前5个节点和随机选择的其它的节点间增加连接，则容量提高得更多。但是对于scale-free网络来说，给Betweenness较大的前5个节点增加连接对于原本负载就很重的中枢节点，简直就是雪上加霜。缓解中枢节点的压力比单纯提高网络容量更为重要。本文以基于Barabsi -Albert(BA)算法构造的scale-free网络为模型，研究在最短路由算法下此类网络的容量问题。通过理论分析和实验仿真，提出依据Betweenness的值和标准差，增加尽可能少的捷径路径，改善中枢节点的拥塞状况，提高网络容量的方法，对网络运营决策人员进行容量分析和规划有实际指导意义。 2基于Betweenness Centrality的网络容量分析当网络负载很低的时候，转发节点的缓冲队列较空，这时，数据分组的平均端到端时延近似的和分组经过的平均节点数成比例4。当加大负载，转发节点的队列开始增加，平均时延也相应增加。当负载更进一步加重，达到一个临界值c，某些节点的缓冲队列将增长很快，数据分组平均时延陡增，网络性能恶化。这时，认为网络发生了拥塞，网络的吞吐量由升转降，而c就定义为网络的容量。通信网络可以用图G=（V，E）来表示，其中V代表节点（顶点）集，E代表链路（边）集。主机、路由器和交换机在图中用节点（顶点）来表示，它们之间的物理连接则用链路（边）来表示。本文只考虑连通无向图。如果记图中任意两点s,d之间的最短路径条数为，而这些最短路径中经过节点w的条数为，那么节点s,d之间经过w的最短路径条数占s,d间总的最短路径条数的比例为， 在此基础上，节点w的Betweenness Centrality定义为：一个节点的越大，它就显得越重要，因为大量的数据分组将流经它，它的负载将很重。因此，这种类型的节点在设计时需要更大的数据处理速率，连接的链路也需要更大的带宽容量5。Scale-free网络的中枢节点通常是数据传输中使用率很高的节点，因此会很大。文4从理论上指出，如果 是将标准化，那么网络容量可以近似地表示为 ， （1）其中S是包括主机在内的所有节点数，是主机密度，S表示主机数，主机节点随机地分布在网络中，集合R(s,d)是从路由表中得到的节点子集。从公式（1）可以看出，在主机数一定的情况下，网络的容量和节点的Betweenness值之间关系密切。因此，我们研究的目的就是希望通过仿真实验，进一步找出网络的静态属性Betweenness值和网络容量之间更直观、更明确的关系。3仿真实验 文中仿真方法类似于文6中所描述的方法。网络中有N个节点，这里N=1，2，3。连续的时间过程被等分为离散的、等时间间隔的仿真时钟的推进。在每一个仿真步长内t,t+1)，N个节点之中的每一个节点最多生成M个数据分组,每个节点生成数据分组是相互独立的。具体方法是每个节点在时刻t生成M个随机数，每个随机数都服从0，1均匀分布。在仿真时钟开始推进之前，设置一个阈值P（其值在0，1之间）。如果一个节点在时刻t生成的M个随机数中有m个小于或等于该阈值P，则在此时刻该节点生成m个数据分组。在整个仿真过程中单个节点和系统数据分组生成速率V，Vtotal 表示为：V=M*P Vtotal=N*M*P通过控制参数M和P，可以调节系统数据分组生成速率Vtotal。在仿真试验中，固定参数M，通过调节P的大小来改变Vtotal。当P在0，1间变化时，Vtotal在0，N*M*P范围内变化。在每个仿真时刻t，到达中间路由节点的数据分组进入缓冲队列的尾部，等待转发。Fig. 1 A scale-free network图 1一个scale-free网络对于如图1所示的具有scale-free特征的网络，节点数N=55，图中圆圈里的数字代表节点号，表1按照Betweenness值的降序列出了图中每个节点的Betweenness值，我们按照这种排列方式把节点分为Betweenness值位于前10%的节点、Betweenness值位于前10%到前20%之间的节点，Betweenness值位于前20%到前30%的节点以及Betweenness值排在后70%的节点。图中深色的节点是Betweenness值位于前10%的节点，即Betweenness值属于TOP6的中枢节点。采用上述仿真方法，在NS2仿真平台上进行实验，其中M=1000，的初值设为0.05，并以0.001递增，直至系统开始发生拥塞。这时的Vtotal就是网络容量c，c =N*M*P，通过做多组实验求出c的平均值作为网络容量的无偏估计量。表2列出了增加某些捷径路径以后，网络容量的变化情况以及与Betweenness的关系。表中第一列的新增链路表示在原图的基础上增加一条链路，每次增加链路后重做上述仿真实验，例如0-54表示节点号为0和节点号为54的两节点间增加一条连接，考查此时容量平均值和Betweenness的关系。图2则依据表2的数据给出了网络容量和Betweenness的标准差的关系图。 Table 1 The Betweenness of each node in the Fig.1表1 图1中每个节点的Betweenness值列表新增链路网络容量平均值Betweenness标准差Betweenness和最短路径长度最短路径上Top6节点数15-496152.11 31216292730-115918.03 322.1516738430-155917.01 317.57166225314-325600.29 319.37167344215-505234.24 317.29162147338-465160.01 322.71163085426-385008.79 340.65164664444-534894.35 333.971694012449-444723.18 333.89168649432-414563.41 328.74166305320-384452.93 358.991622833原图4331.93 362.2717432-20-544320.34 357.5162946220-524318.12 356.916040520-444092.04 338.216928840-543904.00 355.1516706830-523142.95 354.2616580737-15872.54 364.3717164217-38870.70 372.361680832Table 2 The relation between the network capacity and nodes Betweenness表2 网络容量与节点的Betweenness关系表 Fig. 2 The relation between the Variation of Betweenness and network capacity图2 Betweenness的标准差和网络容量关系图从以上的图表可以看出：(1) 网络节点的Betweenness的标准差与网络容量关系紧密。从图2 我们可以明显看出，网络节点的Betweenness的标准差越小，网络容量越大。网络节点的Betweenness的标准差小，说明网络负载较为均衡，瓶颈节点出现的概率小，因此发生网络拥塞的概率变小，从而网络容量变大。(2) 网络节点的Betweenness的和与网络容量没有明显关系。(3) 选择新增连接的两点之间的最短路径长度与网络容量没有明显的关系，但是在其他因素相同的情况下，最短路径长度越长，对容量改进效果越明显。(4) 容量增加显著的网络拓扑有着一个共性：选择连接的两点之间的最短路径上，有着较多的Betweenness值位于TOP 6 的节点，即Betweenness值位于前10%的节点。当两个节点之间的最短路径经过较多个Betweenness值位于前10%的节点时，可以考虑在它们之间增加链路，以缓解网络拥塞。然而，并不是在最短路径上有着更多的Betweenness值位于前10%的节点的节点对之间增加链路，就能更多地提高网络容量。(5) 在Betweenness值位于前10%到前20%之间的节点之间增加连接往往能最大幅度提高网络容量。表1中新增连接后容量最大的前五种情况中就有四种是在这样的节点间增加的连接。因为具有这种特征的节点在网络中属于次中枢节点，重要性也较高，网络中不少的流量要经过它们，但同时它们的负载又不是很重，所以增加连接后即能为整个网络分流，又不至于本身的负载过重，有利于网络容量的提高。在以基于Barabsi -Albert(BA)算法构造的其它较大规模的scale-free网络中，进行上述同样的实验，也能得到类似的结论。4提高复杂网络容量的方法根据文7中的算法，可以计算出网络中各个节点的Betweenness值，找到中枢节点。然后依据以上的实验结果，在节点间增加一些链路，以提高网络容量。基本方法如下：(1) 在网络规模不大（节点数很小）的情况下，可以穷尽所有节点对之间增加链路的情况，每次在不存在连接的两点间新增一条连接，找到使得Betweenness的标准差最小的连接方式，它能最大程度提高网络容量；(2) 在网络规模较大的情况下，无法穷尽所有节点对之间增加链路的情况，或者只需要得到一个较优方案，没必要穷尽所有节点对之间增加链路的情况时，可以选择在网络中不存在连接的且对提高网络容量影响大的两个节点之间增加一条边。当网络中所有节点的Betweenness值按照由大到小的顺序排成一个序列时，所述对提高网络容量影响大的节点为：Betweenness值位于所述序列中排在前10至前20范围内的节点。在满足上述条件的节点中，选择两点间最短路径经过较多的Betweenness值排在前10的节点的节点对，在这样的节点对之间加一条边，除了这两个节点的Betweenness值会大幅增加外，其他大多数中枢节点的负载会大幅下降，尤其对Betweenness值排在前10的节点的改善很明显，总体容量也能较大提高；(3) 对按(1)或(2)中的方法增加链路后的网络，重新计算各个节点的Betweenness值以及整个网络Betweenness的标准差，可以从理论上分析每个节点负载的变化和网络容量的变化；(4) 根据上述优选方案，进行实验仿真或者实际测试，并结合实际情况，比如两点之间的实际距离、增加链路的费用以及网络拓扑部署的策略等因素，最终确定合理的优化方案。5结论随着复杂网络研究的兴起，Betweenness Centrality被广泛用在大规模网络拓扑的分析中。由于它能够刻画不同节点或边在网络中的重要程度，能够很好地描述一个网络中节点或链路可能需要承载的流量，因此本文引入Betweenness Centrality来进行网络容量分析。对于像Internet这样具有scale-free特征的网络，节点的重要程度差别很大，少数中枢节点成为制约网络容量的瓶颈。本文首先进行了理论分析，而后通过仿真实验得出了Betweenness和网络容量的关系，提出通过增加捷径路径来平衡中枢节点的负载，提高网络容量的有效而易于操作的方法。下一步工作将深入考查Betweenness和网络容量之间定量的关系，并考虑复杂网络更多的特征，进一步研究网络拓扑的静态属性和网络容量的关系。参考文献1. Neelima Gupte, Brajendra K. Singh. Role of connectivity in congestion and decongestion in networks. the Proceedings of the 3rd International Conference NEXT-SigmaPhi. 2005.92. Petter Holme. Congestion and centrality in traffic flow on complex networks. Advances in Complex Systems 6, 163-176 (2003).3. L.C. Freeman. A set of measures of Centrality based on Betweenness. Sociometry, 40:35-41, 1977.4. D.K. Arrowsmith, R.J. Mondragn, M. Woolf. Data traffic, topology and congestion. 20045. Zhengping FAN, Guanrong CHEN, King Tim KO. Evolving networks: from topology to dynamics. Journal of Control Theory and Applications 2 (2004) 60646. 蔡研，赵千川. 网络拓扑与容量的关系初探. 计算机工程与应用，2003.15：178183(Cai Yan, Zhao Qianchuan. Discussion about network capacity relevant to topology information of network. Computer Engineering and Applicaion (in Chinese), 2003.15:178183)7. 张国强，张国清. 基于回溯机制的互联网AS拓扑的Betweenness算法,计算机研究与发展，Vol.43.2006.(Zhang Guoqiang, Zhang Guoqing. “An Algorithm for Internet AS Graph Betweenness Centrality Based on Backtrack”, Journal of Computer Research and Development (in Chinese), Vol.43.2006.)