一类基于随机行走机理的优化路由改进策略

在对随机行走过程的研究中发现:单个粒子通过某条特定路径的时间正比于该路径上所有节点度的连乘积.据此,文章提出基于随机行走机理的优化路由改进策略.该策略以节点度连乘积最小化为原则,通过调节可变参数,建立节点处理能力均匀分布的情况下最佳路由策略.通过分析比较不同路由策略条件下平均路由介数中心度,网络的临界负载量,平均路径长度以及平均搜索信息量等性能指标,研究结果表明,此改进路由策略在保证网络平均路径长度较少增加的前提下,使网络的传输能力获得最大幅度的提升. 关键词： 复杂网络 路由策略 负载传输     

无标度复杂网络负载传输优化策略

提出了一种能够显著提高无标度复杂网络负载传输性能的优化路由策略.实现了负载在核心节点与边缘节点间的合理分配.分析表明该策略使得网络的负载处理能力正比于网络规模的平方,而与单个节点的度值无关.实验结果显示优化路由策略在保持了最短路由策略小世界效应的同时,成倍地提升了网络的负载传输能力,且随着网络平均节点度的增加其优势越趋显著.此外,与有效路由策略的比较进一步验证了优化路由策略的优异性能. 关键词： 优化路由策略 复杂网络 负载传输 网络阻塞     

基于引力场理论的复杂网络路由选择策略研究

利用引力场理论对网络传输过程中节点激发的引力场进行了描述,建立了节点的引力场方程,引入α和γ两个参数,用于调节数据传输对节点畅通程度、节点传输能力和路径长度的依赖程度．基于节点的引力场,提出了一种高效的路由选择算法,该算法下数据包将沿着所受路径引力最大的方向进行传递．为检验算法的有效性,引入有序状态参数卵,利用其由自由流到拥塞态的指标流量相变值度量网络的吞吐量,并通过节点的介中心值B分析网络的传输性能和拥塞分布．针对算法在不同α,γ取值条件下的路由情况进行了仿真．仿真结果显示,与传统最短路由算法相比,本文算法将网络传输能力提高了数倍,有效地均衡了节点的介中心值分布,传输路径平均长度（Lavg）随负载量R的增加表现出先增后减的变化趋势,而参数α与γ值的变化对网络传输能力几乎没有影响,说明本文路由算法的性能不依赖于α与γ,对于可行域内任意的α与γ算法都能保证网络传输能力近似相等．     

基于社团结构的负载传输优化策略研究

研究表明网络社团结构特征对负载传输有影响,明显社团结构特征会降低网络的承载能力.由于最短路由策略在选择路由时有一定的随机性,本文提出了一种基于社团结构的负载传输策略,减少最短路由经过的社团数量,从而降低社团边缘节点的介数.实验结果显示,该策略在保证最短路由小世界特性的同时,提升了网络的承载能力,社团划分得越准确传输优化策略效果越显著. 关键词： 优化路由策略 社团结构 复杂网络 负载传输     

基于最短路径长度的空间网络路由

以通信网、电力网、交通网为代表的很多复杂网络以传输负载为基本功能.在这些网络中,网络的吞吐量是衡量网络传输性能的重要指标,如何提升网络的吞吐量是研究热点之一.不少研究人员提出了不同的路由算法,通过调节传输路径来提高网络吞吐量.但之前的研究很少考虑网络中节点的空间位置.本文针对空间网络提出了一种高效的路由策略,通过节点位置得到路径长度;采用该算法,负载从源节点沿着最短长度的路径传输到目标节点.为了检验算法的有效性,采用网络从自由流状态转变成拥塞状态的相变点Rc来衡量网络的吞吐量.在匀质和异质空间网络上的仿真表明,与传统的最少跳数路由策略相比,本文提出的基于最短路径长度的路由算法能有效提高空间网络的吞吐量.     

复杂网络的一种加权路由策略研究

复杂网络的传输能力是其功能正常运转的重要保障,提高网络的吞吐量有着重要意义.提出一种新的高效路由策略,以提高复杂网络的传输能力,称之为加权路由策略.即对网络的每一条边加权,权值与该边的两端节点的度相关,然后数据包按照这个加权网络的最短路径路由.这样的路径可以更均匀地经过各个节点,发挥它们的传输能力,极大地提高网络的吞吐量.可以避免数据包集中地通过个别度大的节点,在这些节点发生拥塞.仿真显示,该策略比传统的最短路径策略优越,对很多结构的网络,可以提高几十倍的吞吐量. 关键词： 复杂网络 路由策略 吞吐量 拥塞     

最小代价最大节点度数的稀疏光疏导方法

疏导可以增加多播业务请求成功传输概率并提高光纤链路带宽利用率,但波分复用光网络中所有节点具有疏导能力则会增加网络造价和复杂度.本文研究了稀疏疏导网络中疏导节点选择策略,提出基于最小代价最大节点度数的疏导节点选择策略;根据疏导节点和非疏导节点功能差别,改进了稀疏疏导网络中多播请求的疏导传输方法.结合最小代价最大度数疏导节点选择策略和多播业务稀疏疏导传输方法,提出一种根据网络业务阻塞率限定值指标实现多播请求所需最少数目疏导节点的稀疏路由方法.仿真结果表明:在网络给定波长数和光收发器端口数目情况下,所提策略能够节约所需疏导节点数目并优化疏导节点位置,降低网络节点构造造价.     

利用重要度评价矩阵确定复杂网络关键节点

为了对复杂网络节点重要度进行评估,针对节点删除法、节点收缩法和介数法的不足,通过定义节点效率和节点重要度评价矩阵, 提出了一种利用重要度评价矩阵来确定复杂网络关键节点的方法.该方法综合考虑了节点效率、节点度值和相邻节点的重要度贡献,用节点度值和效率值来表征其对相邻节点的重要度贡献,其优化算法的时间复杂度为O(Rn²). 实验分析表明该方法可行有效,对于大型复杂网络可以获得理想的计算能力.     

基于感知流量算法的复杂网络拥塞问题研究

研究了在具有感知流量的路由策略下,复杂网络的拓扑结构对网络中传输流量的影响.为了描述数据包传输过程的有效性,通过引入一个状态参数,利用由稳态到拥塞的指标流量相变值来刻画网络的吞吐量.基于每个节点的数据包处理能力与该节点的度或介数成比例提出两种模型并进行仿真.仿真结果表明,平均度相同的情况下,模型Ⅰ中,WS小世界网络比ER随机网络和BA无标度网络更容易产生拥塞;模型Ⅱ中,所有网络容量都得到较大的提高,尤其是WS小世界网络.但当网络的基本连接参数改变时,哪种模型更利于网络的流量传输,还要依据网络本身的结构特性 关键词： 复杂网络 无标度网络 感知流量 拥塞     

基于局部路由策略的复杂网络拥塞控制

提出一种复杂网络上的局部路由策略,算法采用节点收缩法评估节点的重要度,发送节点根据邻居节点的重要度及网络的状态自适应地调整向邻居节点转发数据包的概率.在网络处于自由流通状态时充分发挥关键节点的优势,保证数据包快速到达目的地;在网络处于即将拥塞时分散业务,根据节点重要度准确识别网络中的关键节点,通过有效分流予以保护.仿真结果表明:在网络处于自由流通状态时,该局部路由策略能充分发挥网络中关键节点的枢纽作用,保持较低的传输时延;在网络部分关键节点出现拥塞时,该局部路由策略能有效避开拥挤严重的节点,将数据包均匀地分布在各个节点上,有效抑制网络拥塞,提高网络的容量.     

Routing in scale-free networks based on expanding betweenness centrality

In this paper, an improved routing strategy is proposed for enhancing the traffic capacity of scale-free networks. Instead of using the information of degree and betweenness centrality, the new algorithm is derived on the basis of the expanding betweenness centrality of nodes, which gives an estimate of the traffic handled by the vertex for a certain route set. Since the nodes with large betweenness centrality are more susceptible to traffic congestion, the traffic can be improved by redistributing traffic loads from nodes with large betweenness centrality to nodes with small betweenness centrality in the process of computing the collective routing table. Comparing with results of previous routing strategies, it is shown that the present improved routing performs more effectively.     

Optimization of transport protocols in complex networks

In this paper, an optimal routing strategy is proposed to enhance the traffic capacity of complex networks. In order to avoid nodes overloading, the new algorithm is derived on the basis of generalized betweenness centrality which gives an estimate of traffic handled by the node for a route set. Since the nodes with large betweenness centrality are more susceptible to traffic congestion, the traffic can be improved, as our strategy, by redistributing traffic load from nodes with large betweenness centrality to nodes with small betweenness centrality in the proceeding of computing collective routing table. Particularly, depending on a parameter that controls the optimization scale, the new routing can not only enlarge traffic capacity of networks more, but also enhance traffic efficiency with smaller average path length. Comparing results of previous routing strategies, it is shown that the present improved routing performs more effectively.     

Methods to find community based on edge centrality

Divisive algorithms are of great importance for community detection in complex networks. One algorithm proposed by Girvan and Newman (GN) based on an edge centrality named betweenness, is a typical representative of this field. Here we studied three edge centralities based on network topology, walks and paths respectively to quantify the relevance of each edge in a network, and proposed a divisive algorithm based on the rationale of GN algorithm for finding communities that removes edges iteratively according to the edge centrality values in a certain order. In addition, we gave a comparison analysis of these measures with the edge betweenness and information centrality. We found the principal difference among these measures in the partition procedure is that the edge centrality based on walks first removes the edge connected with a leaf vertex, but the others first delete the edge as a bridge between communities. It indicates that the edge centrality based on walks is harder to uncover communities than other edge centralities. We also tested these measures for community detection. The results showed that the edge information centrality outperforms other measures, the edge centrality based on walks obtains the worst results, and the edge betweenness gains better performance than the edge centrality based on network topology. We also discussed our method’s efficiency and found that the edge centrality based on walks has a high time complexity and is not suitable for large networks.     

Rewiring dynamical networks with prescribed degree distribution for enhancing synchronizability

In this paper, we present an algorithm for enhancing synchronizability of dynamical networks with prescribed degree distribution. The algorithm takes an unweighted and undirected network as input and outputs a network with the same node-degree distribution and enhanced synchronization properties. The rewirings are based on the properties of the Laplacian of the connection graph, i.e., the eigenvectors corresponding to the second smallest and the largest eigenvalues of the Laplacian. A term proportional to the eigenvectors is adopted to choose potential edges for rewiring, provided that the node-degree distribution is preserved. The algorithm can be implemented on networks of any sizes as long as their eigenvalues and eigenvectors can be calculated with standard algorithms. The effectiveness of the proposed algorithm in enhancing the network synchronizability is revealed by numerical simulation on a number of sample networks including scale-free, Watts-Strogatz, and Erdo?s-Re?nyi graphs. Furthermore, a number of network's structural parameters such as node betweenness centrality, edge betweenness centrality, average path length, clustering coefficient, and degree assortativity are tracked as a function of optimization steps.     

综合考虑局部和全局特性的电网关键节点识别

为有效识别网络中的关键节点,提出一种综合考虑网络局部和全局特性的节点重要性识别综合指标,依据此指标对加权标准测试系统IEEE39和IEEE118中的节点进行重要性排序,并将排序结果与基于介数法和点权法对节点重要性进行排序结果进行对比,基于结构的网络效能分析和基于动力学的失同步扩散时间、同步能力比较均表明,提出的基于综合指标的节点重要性排序更合理,优于基于介数和点权的节点重要性识别方法.     

Detection of influential nodes with multi-scale information

The identification of influential nodes in complex networks is one of the most exciting topics in network science. The latest work successfully compares each node using local connectivity and weak tie theory from a new perspective. We study the structural properties of networks in depth and extend this successful node evaluation from single-scale to multi-scale. In particular, one novel position parameter based on node transmission efficiency is proposed, which mainly depends on the shortest distances from target nodes to high-degree nodes. In this regard, the novel multi-scale information importance (MSII) method is proposed to better identify the crucial nodes by combining the network's local connectivity and global position information. In simulation comparisons, five state-of-the-art algorithms, i.e. the neighbor nodes degree algorithm (NND), betweenness centrality, closeness centrality, Katz centrality and the k-shell decomposition method, are selected to compare with our MSII. The results demonstrate that our method obtains superior performance in terms of robustness and spreading propagation for both real-world and artificial networks.     

Notes on the Algorithm for Calculating Betweenness

We investigate a common used algorithm [Phys. Rev. E 64 （2001） 016132] to calculate the betweenness centrality for all vertices. The inaccurateness of that algorithm is pointed out and a corrected algorithm, also with O（MN） time complexity, is given. In addition, the comparison of calculating results for these two algorithm aiming at the protein interaction network of yeast is shown.     

Undetermination of the relation between network synchronizability and betweenness centrality

Betweenness centrality is taken as a sensible indicator of the synchronizability of complex networks. To test whether betweenness centrality is a proper measure of the synchronizability in specific realizations of random networks,this paper adds edges to the networks and then evaluates the changes of betweenness centrality and network synchronizability. It finds that the two quantities vary independently.     

网络集聚性对节点中心性指标的准确性影响

节点中心性指标是从特定角度对网络某一方面的结构特点进行刻画的度量指标, 因此网络拓扑结构的改变会对节点中心性指标的准确性产生重要影响. 本文利用Holme-Kim模型构建可变集聚系数的无标度网络, 然后采用Susceptible-Infective-Removal模型进行传播影响力的仿真实验, 接着分析了节点中心性指标在不同集聚系数的无标度网络中的准确性. 结果表明, 度中心性和介数中心性的准确性在低集聚系数的网络中表现更好, 特征向量中心性则在高集聚类网络中更准确, 而紧密度中心性的准确性受网络集聚系数的变化影响较小. 因此当网络的集聚系数较低时, 可选择度或者介数作为中心性指标进行网络节点影响力评价; 反之则选择紧密度指标或特征向量指标较好, 尤其当网络的集聚系数接近0.6时特征向量的准确性可以高达到0.85, 是度量小规模网络的较优选择. 另一方面, 传播过程的感染率越高, 度指标和介数指标越可靠, 紧密度和特征向量则相反. 最后Autonomous System实证网络的断边重连实验, 进一步验证了网络集聚性的改变会对节点中心性指标的准确性产生重要影响.     

Vertex centrality as a measure of information flow in Italian Corporate Board Networks

The aim of this article is to investigate the governance models of companies listed on the Italian Stock Exchange by using a network approach, which describes the interlinks between boards of directors. Following mainstream literature, I construct a weighted graph representing the listed companies (vertices) and their relationships (weighted edges), the Corporate Board Network; I then apply three different vertex centrality measures: degree, betweenness and flow betweenness. What emerges from the network construction and by applying the degree centrality is a structure with a large number of connections but not particularly dense, where the presence of a small number of highly connected nodes (hubs) is evident.Then I focus on betweenness and flow betweenness; indeed I expect that these centrality measures may give a representation of the intensity of the relationship between companies, capturing the volume of information flowing from one vertex to another. Finally, I investigate the possible scale-free structure of the network.