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.     

一种复杂网络路由策略的普适优化算法

现有的复杂网络路由策略很多,改进算法也不断涌现,但是目前还没有一个统一的标准来衡量算法是否达到网络最佳传输效果.针对这一问题,本文提出一种适用于现有路由策略的普适优化算法.首先通过理论分析指出制约网络传输能力的关键因素是最大介数中心度,因而"最大介数中心度是否已经最低"成为评判路由策略是否最优的标准.在此基础上,采用"惩罚选择法"避开网络中介数中心度值比较大的节点,使网络介数中心度值分布更均匀,均衡网络中各个节点的传输负载.仿真结果显示,该优化算法针对现有路由策略均能降低最大介数中心度值,大幅度提高网络的传输能力.     

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

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

Improved routing strategy based on gravitational field theory

Routing and path selection are crucial for many communication and logistic applications. We study the interaction between nodes and packets and establish a simple model for describing the attraction of the node to the packet in transmission process by using the gravitational field theory, considering the real and potential congestion of the nodes. On the basis of this model, we propose a gravitational field routing strategy that considers the attractions of all of the nodes on the travel path to the packet. In order to illustrate the efficiency of proposed routing algorithm, we introduce the order parameter to measure the throughput of the network by the critical value of phase transition from a free flow phase to a congested phase,and study the distribution of betweenness centrality and traffic jam. Simulations show that, compared with the shortest path routing strategy, the gravitational field routing strategy considerably enhances the throughput of the network and balances the traffic load, and nearly all of the nodes are used efficiently.     

Efficient packet routing strategy in complex networks

We investigate a new efficient packet routing strategy which mitigates traffic congestion on complex networks. In order to avoid congestion, we minimize the maximum betweenness, which is a measure for concentration of routing paths passing through a node in the network. Danila et al. propose a packet routing strategy in which, instead of shortest paths, they used efficient paths, which are the paths with the minimum total summations of weights assigned to nodes in the respective paths. They use a heuristic algorithm in which the weights are updated step by step by using the information of betweenness of each node in every step and the respective total summations of weights for paths through the nodes with large degrees become comparatively large. Thus passage through such nodes, where congestion almost occurs, is likely to be avoided in their algorithm. The convergence time by their algorithm is, however, quite long. In this paper, we propose a new efficient heuristic algorithm which balances traffic on networks by achieving minimization of the maximum betweenness in the much smaller number of iteration steps for convergence than that by the algorithm of Danila et al.     

Optimized network structure and routing metric in wireless multihop ad hoc communication

Inspired by the Statistical Physics of complex networks, wireless multihop ad hoc communication networks are considered in abstracted form. Since such engineered networks are able to modify their structure via topology control, we search for optimized network structures, which maximize the end-to-end throughput performance. A modified version of betweenness centrality is introduced and shown to be very relevant for the respective modeling. The calculated optimized network structures lead to a significant increase of the end-to-end throughput. The discussion of the resulting structural properties reveals that it will be almost impossible to construct these optimized topologies in a technologically efficient distributive manner. However, the modified betweenness centrality also allows to propose a new routing metric for the end-to-end communication traffic. This approach leads to an even larger increase of throughput capacity and is easily implementable in a technologically relevant manner.     

Incremental routing strategy on scale-free networks

The most important function of a network is for transporting traffic. Due to the low traffic capacity of network systems under the global shortest path routing, plenty of heuristic routing strategies are emerging. In this paper, we propose a heuristic routing strategy called the incremental routing algorithm to improve the traffic capacity of complex networks. We divide the routing process into N$N$(the network size) steps and, at each step, we heuristically calculate all the routes for one source node considering both the dynamic efficient betweenness centrality and node degree information. We do extensive simulations on scale-free networks to confirm the effectiveness of the proposed incremental routing strategy. The simulation results show that the traffic capacity has been enhanced by a substantial factor at the expense of a slight lengthening in the average path.     

Role of connectivity in congestion and decongestion in a communication network

We study network traffic dynamics in a two dimensional communication network with regular nodes and hubs. If the network experiences heavy message traffic, congestion occurs due to finite capacity of the nodes. We discuss strategies to manipulate hub capacity and hub connections to relieve congestion and define a coefficient of betweenness centrality (CBC), a direct measure of network traffic, which is useful for identifying hubs which are most likely to cause congestion. The addition of assortative connections to hubs of high CBC relieves congestion very efficiently. An erratum to this article is available at .     

Change of network load due to node removal

The interplay between topology changes and the redistribution of traffic plays a significant role in many real-world networks. In this paper we study how the load of the remaining network changes when nodes are removed. This removal operation can model attacks and errors in networks, or the planned control of network topology. We consider a scenario similar to the data communication networks, and measure the load of a node by its betweenness centrality. By analysis and simulations, we show that when a single node is removed, the change of the remaining network’s load is positively correlated with the degree of the removed node. In multiple-node removal, by comparing several node removal schemes, we show in detail how significantly different the change of the remaining network’s load will be between starting the removal from small degree/betweenness nodes and from large degree/betweenness nodes. Moreover, when starting the removal from small degree/betweenness nodes, we not only observe that the remaining network’s load decreases, which is consistent with previous studies, but also find that the load of hubs keeps decreasing. These results help us to make a deeper understanding about the dynamics after topology changes, and are useful in planned control of network topology.     

Searchability of Central Nodes in Networks

Social networks are discrete systems with a large amount of heterogeneity among nodes (individuals). Measures of centrality aim at a quantification of nodes’ importance for structure and function. Here we ask to which extent the most central nodes can be found by purely local search. We find that many networks have close-to-optimal searchability under eigenvector centrality, outperforming searches for degree and betweenness. Searchability of the strongest spreaders in epidemic dynamics tends to be substantially larger for supercritical than for subcritical spreading.     

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.     

推荐重要节点部署防御策略的优化模型

当前网络安全防御策略集中部署于高连接度节点主要有2个方面的不足: 一是高连接度节点在很多场合中并不是网络通信的骨干节点; 二是该类节点对信息的转发和传播并非总是最有效的.针对以上传统部署策略的不足, 改进了恶意病毒程序传播的离散扩散模型并采用中间路径跳数来衡量网络节点的重要程度, 提出了基于介数中心控制力和接近中心控制力模型的重要节点优先推荐部署技术.实验结果显示具有高介数中心控制力和低接近中心控制力的节点相对于传统的高连接度节点无论在无标度网络还是小世界网络均能够对恶意病毒程序的疫情扩散和早期传播速度起到更加有效的抑制作用, 同时验证了网络分簇聚类行为产生的簇团特性也将对恶意程序的传播起到一定的负面影响.     

Transport optimization on complex networks

We present a comparative study of the application of a recently introduced heuristic algorithm to the optimization of transport on three major types of complex networks. The algorithm balances network traffic iteratively by minimizing the maximum node betweenness with as little path lengthening as possible. We show that by using this optimal routing, a network can sustain significantly higher traffic without jamming than in the case of shortest path routing. A formula is proved and tested with numerical simulation that allows quick computation of the average number of hops along the path and of the average travel times once the betweennesses of the nodes are computed. Using this formula, we show that routing optimization preserves the small-world character exhibited by networks under shortest path routing, and that it significantly reduces the average travel time on congested networks with only a negligible increase in the average travel time at low loads. Finally, we study the correlation between the weights of the links in the case of optimal routing and the betweennesses of the nodes connected by them.     

Identifying important nodes in weighted functional brain networks: a comparison of different centrality approaches

We compare different centrality metrics which aim at an identification of important nodes in complex networks. We investigate weighted functional brain networks derived from multichannel electroencephalograms recorded from 23 healthy subject under resting-state eyes-open or eyes-closed conditions. Although we observe the metrics strength, closeness, and betweenness centrality to be related to each other, they capture different spatial and temporal aspects of important nodes in these networks associated with behavioral changes. Identifying and characterizing of these nodes thus benefits from the application of several centrality metrics.     

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

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

基于复杂网络理论的多元混合空管技术保障系统网络特征分析

为提高空管技术保障系统应对突发事件的能力,本文以空管技术保障系统导航、通信、监视设备覆盖的航路结构为基础,构建系统对应的空间网络模型.提出从灵活性、鲁棒性、高效性三个方面度量空管技术保障系统网络特性,对北京、上海、广州、昆明、沈阳、兰州飞行情报区的空管技术保障系统网络的平均度、度分布、度-度相关性、聚集系数、平均路径长度、直径等进行分析.分析结果显示,各飞行情报区空管技术保障系统的平均聚集系数在0.25—0.39之间,网络聚集程度偏低;网络平均路径长度为3.4,表现出小世界网络特征;度值3时服从幂律分布,度-度分布不表现出正相关或负相关.对网络进行基于度优先的和随机的抗毁性测度,空管技术保障系统网络抗毁性较差,网络的可靠性由少数核心节点决定,应对核心节点进行目标免疫,提高网络的抗毁性.这些规律为空管技术保障系统能力提升、新建扩建提供理论依据,对降低突发事件对空管系统保障能力的影响,保障空中交通持续安全具有现实意义.     

基于节点负荷失效的网络可控性研究

Liu和Barabasi将现代控制理论应用到线性系统的网络可控性问题上, 提出了最小驱动节点集的计算方法, 解决了复杂网络控制的可计算问题. 针对现实网络中存在的节点因负荷过载而失效的问题, 本文提出了基于节点负荷失效的网络可控性模型. 通过对网络采用介数和Weibull失效模型, 在随机和目标失效机制下进行仿真, 研究结果表明: 维持无标度网络可控性的难度要明显大于随机网络; 在目标节点失效机制下, 即使对网络输入极少的失效信号, 也能极大地破坏网络的可控性; 使高介数节点失效要比使度高节点失效更能破坏网络的可控性, 说明高介数节点在维持网络可控性上发挥着重要作用; 对不同的负荷失效模型, 要合理采取措施, 防止网络发生阶跃性全不可控现象. 关键词： 网络可控性 结构可控性 节点失效     

Extracting hidden fluctuation patterns of Hang Seng stock index from network topologies

We present a model of complex network generated from Hang Seng index (HSI) of Hong Kong stock market, which encodes stock market relevant both interconnections and interactions between fluctuation patterns of HSI in the network topologies. In the network, the nodes (edges) represent all kinds of patterns of HSI fluctuation (their interconnections). Based on network topological statistic, we present efficient algorithms, measuring betweenness centrality (BC) and inverse participation ratio (IPR) of network adjacency matrix, for detecting topological important nodes. We have at least obtained three uniform nodes of topological importance, and find the three nodes, i.e. 18.7% nodes undertake 71.9% betweenness centrality and closely correlate other nodes. From these topological important nodes, we can extract hidden significant fluctuation patterns of HSI. We also find these patterns are independent the time intervals scales. The results contain important physical implication, i.e. the significant patterns play much more important roles in both information control and transport of stock market, and should be useful for us to more understand fluctuations regularity of stock market index. Moreover, we could conclude that Hong Kong stock market, rather than a random system, is statistically stable, by comparison to random networks.     

一种新的网络传播中最有影响力的节点发现方法

在复杂网络的传播模型研究中, 如何发现最具影响力的传播节点在理论和现实应用中都有重大的意义. 目前的研究一般使用节点的度数、紧密度、介数和K-shell等中心化指标来评价影响力, 这种方法虽然简单, 但是由于它们仅利用了节点自身的内部属性, 因而在评价影响力时精确度并不高, 普遍性适用性较弱.为了解决这个问题, 本文提出了KSC (K-shell and community centrality)指标模型. 此模型不但考虑了节点的内部属性, 而且还综合考虑了节点的外部属性, 例如节点所属的社区等. 然后利用SIR (susceptible-infected-recovered)模型对传播过程进行仿真, 实验证明所提出的方法可以更好地发现最具有影响力的节点, 且可适用于各种复杂网络. 本文为这项具有挑战性研究提供了新的思想和方法. 关键词： 复杂网络 最具影响力的节点 社区划分 中性化测量