Error and attack tolerance of synchronization in Hindmarsh–Rose neural networks with community structure

Synchronization is one of the most important features observed in large-scale complex networks of interacting dynamical systems. As is well known, there is a close relation between the network topology and the network synchronizability. Using the coupled Hindmarsh–Rose neurons with community structure as a model network, in this paper we explore how failures of the nodes due to random errors or intentional attacks affect the synchronizability of community networks. The intentional attacks are realized by removing a fraction of the nodes with high values in some centrality measure such as the centralities of degree, eigenvector, betweenness and closeness. According to the master stability function method, we employ the algebraic connectivity of the considered community network as an indicator to examine the network synchronizability. Numerical evidences show that the node failure strategy based on the betweenness centrality has the most influence on the synchronizability of community networks. With this node failure strategy for a given network with a fixed number of communities, we find that the larger the degree of communities, the worse the network synchronizability; however, for a given network with a fixed degree of communities, we observe that the more the number of communities, the better the network synchronizability.     

Centrality measure of complex networks using biased random walks

We propose a novel centrality measure based on the dynamical properties of a biased random walk to provide a general framework for the centrality of vertex and edge in scale-free networks (SFNs). The suggested centrality unifies various centralities such as betweenness centrality (BC), load centrality (LC) and random walk centrality (RWC) when the degree, k, is relatively large. The relation between our centrality and other centralities in SFNs is clearly shown by both analytic and numerical methods. Regarding to the edge centrality, there have been few established studies in complex networks. Thus, we also provide a systematic analysis for the edge BC (LC) in SFNs and show that the distribution of edge BC satisfies a power-law. Furthermore we also show that the suggested centrality measures on real networks work very well as on the SFNs.     

Computing Influential Nodes Using the Nearest Neighborhood Trust Value and PageRank in Complex Networks

Computing influential nodes gets a lot of attention from many researchers for information spreading in complex networks. It has vast applications, such as viral marketing, social leader creation, rumor control, and opinion monitoring. The information-spreading ability of influential nodes is greater compared with other nodes in the network. Several researchers proposed centrality measures to compute the influential nodes in a complex network, such as degree, betweenness, closeness, semi-local centralities, and PageRank. These centrality methods are defined based on the local and/or global information of nodes in the network. However, due to their high time complexity, centrality measures based on the global information of nodes have become unsuitable for large-scale networks. Very few centrality measures exist that are based on the attributes between nodes and the structure of the network. We propose the nearest neighborhood trust PageRank (NTPR) based on the structural attributes of neighbors and nearest neighbors of nodes. We define the measure based on the degree ratio, the similarity between nodes, the trust values of neighbors, and the nearest neighbors. We computed the influential nodes in various real-world networks using the proposed centrality method. We found the maximum influence by using influential nodes with SIR and independent cascade methods. We also compare the maximum influence of our centrality measure with the existing basic centrality measures.     

The importance of centralities in dark network value chains

This paper introduces three novel centrality measures based on the nodes’ role in the operation of a joint task, i.e., their position in a criminal network value chain. For this, we consider networks where nodes have attributes describing their “capabilities” or “colors”, i.e., the possible roles they may play in a value chain. A value chain here is understood as a series of tasks to be performed in a specific order, each requiring a specific capability. The first centrality notion measures how many value chain instances a given node participates in. The other two assess the costs of replacing a node in the value chain in case the given node is no longer available to perform the task. The first of them considers the direct distance (shortest path length) between the node in question and its nearest replacement, while the second evaluates the actual replacement process, assuming that preceding and following nodes in the network should each be able to find and contact the replacement. In this report, we demonstrate the properties of the new centrality measures using a few toy examples and compare them to classic centralities, such as betweenness, closeness and degree centrality. We also apply the new measures to randomly colored empirical networks. We find that the newly introduced centralities differ sufficiently from the classic measures, pointing towards different aspects of the network. Our results also pinpoint the difference between having a replacement node in the network and being able to find one. This is the reason why “introduction distance” often has a noticeable correlation with betweenness. Our studies show that projecting value chains over networks may significantly alter the nodes’ perceived importance. These insights might have important implications for the way law enforcement or intelligence agencies look at the effectiveness of dark network disruption strategies over time.     

Rethinking failure and attack tolerance assessment in complex networks

Studies have revealed that real complex networks are inherently vulnerable to the loss of high centrality nodes. These nodes are crucial to maintaining the network connectivity and are identified by classical measures, such as degree and betweenness centralities. Despite its significance, an assessment based solely on this vulnerability premise is misleading for the interpretation of the real state of the network concerning connectivity. As a matter of fact, some networks may be in a state of imminent fragmentation before such a condition is fully characterized by an analysis targeted solely on the centrally positioned nodes. This work aims at showing that, in fact, it is basically the global network configuration that is responsible for network fragmentation, as it may allow many other lower centrality nodes to seriously damage the network connectivity.     

Detecting community structure in networks

There has been considerable recent interest in algorithms for finding communities in networks--groups of vertices within which connections are dense, but between which connections are sparser. Here we review the progress that has been made towards this end. We begin by describing some traditional methods of community detection, such as spectral bisection, the Kernighan-Lin algorithm and hierarchical clustering based on similarity measures. None of these methods, however, is ideal for the types of real-world network data with which current research is concerned, such as Internet and web data and biological and social networks. We describe a number of more recent algorithms that appear to work well with these data, including algorithms based on edge betweenness scores, on counts of short loops in networks and on voltage differences in resistor networks.Received: 10 November 2003, Published online: 14 May 2004PACS: 89.75.Hc Networks and genealogical trees - 87.23.Ge Dynamics of social systems - 89.20.Hh World Wide Web, Internet - 05.10.-a Computational methods in statistical physics and nonlinear dynamics     

A class of improved algorithms for detecting communities in complex networks

Detecting communities in complex networks is of considerable importance for understanding both the structure and function of the networks. Here, we propose a class of improved algorithms for community detection, by combining the betweenness algorithm of Girvan and Newman with the edge weight defined by the edge-clustering coefficient. The improved algorithms are tested on some artificial and real-world networks, and the results show that they can detect communities of networks more effectively in both unweighted and weighted cases. In addition, the technique for improving the betweenness algorithm in this paper, thanks to its compatibility, can directly be applied to various detection algorithms.     

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

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

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

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

Complexity in human transportation networks: a comparative analysis of worldwide air transportation and global cargo-ship movements

We present a comparative network-theoretic analysis of the two largest global transportation networks: the worldwide air-transportation network (WAN) and the global cargo-ship network (GCSN). We show that both networks exhibit surprising statistical similarities despite significant differences in topology and connectivity. Both networks exhibit a discontinuity in node and link betweenness distributions which implies that these networks naturally segregate into two different classes of nodes and links. We introduce a technique based on effective distances, shortest paths and shortest path trees for strongly weighted symmetric networks and show that in a shortest path tree representation the most significant features of both networks can be readily seen. We show that effective shortest path distance, unlike conventional geographic distance measures, strongly correlates with node centrality measures. Using the new technique we show that network resilience can be investigated more precisely than with contemporary techniques that are based on percolation theory. We extract a functional relationship between node characteristics and resilience to network disruption. Finally we discuss the results, their implications and conclude that dynamic processes that evolve on both networks are expected to share universal dynamic characteristics.     

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.     

Lobby index as a network centrality measure

We study the lobby index (l$l$-index for short) as a local node centrality measure for complex networks. The l$l$-index is compared with degree (a local measure), betweenness and Eigenvector centralities (two global measures) in the case of a biological network (Yeast interaction protein–protein network) and a linguistic network (Moby Thesaurus   II). In both networks, the l$l$-index has a poor correlation with betweenness but correlates with degree and Eigenvector centralities. Although being local, the l$l$-index carries more information about its neighbors than degree centrality. Also, it requires much less time to compute when compared with Eigenvector centrality. Results show that the l$l$-index produces better results than degree and Eigenvector centrality for ranking purposes.     

节点中心性对复杂网络传播模式的影响分析

在众多的重要节点评估方法研究中,具有较高中心性的节点一直是关注的焦点,许多传播行为的研究也主要围绕高中心性节点展开,因此在一定程度上忽略了低中心性节点对传播行为的影响.本文从传播异构性角度,通过初始感染最大中心性节点和最小中心性节点揭示网络结构异构性对信息传播的影响.实验结果表明,传播过程中存在"链型"和"扇型"两种传播模式,在初始感染比例不断提升的情况下,两种传播模式的相互转换引发传播速率的变化,进一步促使非线性传播规模交叉现象的产生.这一现象说明,在宏观的信息传播过程中,最小中心性节点的影响力不容忽视,尤其在初始感染比例升高时,最小中心性节点比最大中心性节点更具传播优势.     

Betweenness centrality in finite components of complex networks

We use generating function formalism to obtain an exact formula of the betweenness centrality in finite components of random networks with arbitrary degree distributions. The formula is obtained as a function of the degree and the component size, and is confirmed by simulations for Poisson, exponential, and power-law degree distributions. We find that the betweenness centralities for the three distributions are asymptotically power laws with an exponent 1.5 and are invariant to the particular distribution parameters.     

Enhancing synchronizability by rewiring networks

<正>According to different forms of synchronized region,complex networks are divided into typeⅠ(unbounded synchronization region) and typeⅡ(bounded synchronization region) networks.This paper presents a rewiring algorithm to enhance the synchronizability of typeⅠand typeⅡnetworks.By utilizing the algorithm for an unweighted and undirected network,a better synchronizability of network with the same number of nodes and edges can be obtained. Numerical simulations on several different network models are used to support the proposed procedure.The relationship between different topological properties of the networks and the number of rewirings are shown.It finds that the final optimized network is independent of the initial network,and becomes homogeneous.In addition the optimized networks have similar structural properties in the sense of degree,and node and edge betweenness centralities.However,they do not have similar cluster coefficients for typeⅡnetworks.The research may be useful for designing more synchronizable networks and understanding the synchronization behaviour of networks.     

Detecting hierarchical and overlapping network communities using locally optimal modularity changes

Agglomerative clustering is a well established strategy for identifying communities in networks. Communities are successively merged into larger communities, coarsening a network of actors into a more manageable network of communities. The order in which merges should occur is not in general clear, necessitating heuristics for selecting pairs of communities to merge. We describe a hierarchical clustering algorithm based on a local optimality property. For each edge in the network, we associate the modularity change for merging the communities it links. For each community vertex, we call the preferred edge that edge for which the modularity change is maximal. When an edge is preferred by both vertices that it links, it appears to be the optimal choice from the local viewpoint. We use the locally optimal edges to define the algorithm: simultaneously merge all pairs of communities that are connected by locally optimal edges that would increase the modularity, redetermining the locally optimal edges after each step and continuing so long as the modularity can be further increased. We apply the algorithm to model and empirical networks, demonstrating that it can efficiently produce high-quality community solutions. We relate the performance and implementation details to the structure of the resulting community hierarchies. We additionally consider a complementary local clustering algorithm, describing how to identify overlapping communities based on the local optimality condition.     

微博双向“关注”网络节点中心性及传播 影响力的分析

根据新浪微博的实际数据, 建立了两个基于双向“关注”的用户关系网络, 通过分析网络拓扑统计特征, 发现二者均具有小世界、无标度特征. 通过对节点度、紧密度、介数和k-core 四个网络中心性指标进行实证分析, 发现节点度服从分段幂率分布; 介数相比其他中心性指标差异性最为显著; 两个网络均具有明显的层次性, 但不是所有度值大的节点核数也大; 全局范围内各中心性指标之间存在着较强的相关性, 但在度值较大的节点群这种相关性明显减弱. 此外, 借助基于传染病动力学的SIR信息传播模型来分析四种指标在刻画节点传播能力方面的差异性, 仿真结果表明, 选择具有不同中心性指标的初始传播节点, 对信息传播速度和范围均具有不同影响; 紧密度和k-core较其他指标可以更加准确地描述节点在信息传播中所处的网络核心位置, 这有助于识别信息传播拓扑网络中的关键节点.     

Empirical analysis of the ship-transport network of China

Structural properties of the ship-transport network of China (STNC) are studied in the light of recent investigations of complex networks. STNC is composed of a set of routes and ports located along the sea or river. Network properties including the degree distribution, degree correlations, clustering, shortest path length, centrality, and betweenness are studied in different definitions of network topology. It is found that geographical constraint plays an important role in the network topology of STNC. We also study the traffic flow of STNC based on the weighted network representation, and demonstrate the weight distribution can be described by power-law or exponential function depending on the assumed definition of network topology. Other features related to STNC are also investigated.     

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.     

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.