A Robustness Model of Complex Networks with Tunable Attack Information Parameter

We introduce a novel model for robustness of complex with a tunable attack information parameter. The random failure and intentional attack known are the two extreme cases of our model. Based on the model, we study the robustness of complex networks under random information and preferential information, respectively. Using the generating function method, we derive the exact value of the critical removal fraction of nodes for the disintegration of networks and the size of the giant component. We show that hiding just a small fraction of nodes randomly can prevent a scale-free network from collapsing and detecting just a small fraction of nodes preferentially can destroy a scale-free network.     

The emergence of scale-free networks with a seceding mechanism

In order to explore further the underlying mechanism of scale-free networks, we study stochastic secession as a mechanism for the creation of complex networks. In this evolution the network growth incorporates the addition of new nodes, the addition of new links between existing nodes, the deleting and rewiring of some existing links, and the stochastic secession of nodes. To random growing networks with preferential attachment, the model yields scale-free behavior for the degree distribution. Furthermore, we obtain an analytical expression of the power-law degree distribution with scaling exponent γ ranging from 1.1 to 9. The analytical expressions are in good agreement with the numerical simulation results.     

On structural properties of scale-free networks with finite size

Since many large real networks tend to present scale-free degree distribution, this paper investigates the structural properties of scale-free networks with finite size. Beginning with a comprehensive analysis of the degree distribution consisting of the concentration trend, dispersion and inequality, this paper then focuses on the discussion of heterogeneity and hub nodes of scale-free networks. The findings will help to improve our understanding of the structure and function of real networks.     

Extremum statistics in scale-free network models

We investigate the statistics of the most connected node in scale-free networks. For a scale-free network model with homogeneous nodes, we show by means of extensive simulations that the exponential truncation, due to the finite size of the network, of the degree distribution governs the scaling of the extreme values and that the distribution of maxima follows the Gumbel statistics. For a scale-free network model with heterogeneous nodes, we show that scaling no longer holds and that the truncation of the degree distribution no longer controls the maxima distribution.     

Truncation of power law behavior in "scale-free" network models due to information filtering

We formulate a general model for the growth of scale-free networks under filtering information conditions-that is, when the nodes can process information about only a subset of the existing nodes in the network. We find that the distribution of the number of incoming links to a node follows a universal scaling form, i.e., that it decays as a power law with an exponential truncation controlled not only by the system size but also by a feature not previously considered, the subset of the network "accessible" to the node. We test our model with empirical data for the World Wide Web and find agreement.     

有倾向性重连产生的反匹配网络

在具有网络结构的系统中度关联属性对于动力学行为具有重要的影响, 所以产生适当度关联网络的方法对于大量网络系统的研究具有重要的作用. 尽管产生正匹配网络的方法已经得到很好的验证, 但是产生反匹配网络的方法还没有被系统的讨论过. 重新连接网络中的边是产生度关联网络的一个常用方法. 这里我们研究使用重连方法产生反匹配无标度网络的有效性. 我们的研究表明, 有倾向的重连可以增强网络的反匹配属性. 但是有倾向重连不能使皮尔森度相关系数下降到-1, 而是存在一个依赖于网络参数的最小值. 我们研究了网络的主要参数对于网络度相关系数的影响, 包括网络尺寸, 网络的连接密度和网络节点的度差异程度. 研究表明在网络尺寸大的情况下和节点度差异性强的情况下, 重连的效果较差. 我们研究了真实Internet网络, 发现模型产生的网络经过重连不能达到真实网络的度关联系数.     

A packet routing strategy using neural networks on scale-free networks

We propose a dynamic packet routing strategy by using neural networks on scale-free networks. In this strategy, in order to determine the nodes to which the packets should be transmitted, we use path lengths to the destinations of the packets, and adjust the connection weights of the neural networks attached to the nodes from local information and the path lengths. The performances of this strategy on scale-free networks which have the same degree distribution and different degree correlations are compared to one another. Our numerical simulations confirm that this routing strategy is more effective than the shortest path based strategy on scale-free networks with any degree correlations and that the performance of our strategy on assortative scale-free networks is better than that on disassortative and uncorrelated scale-free networks.     

Complex networks: Dynamics and security

This paper presents a perspective in the study of complex networks by focusing on how dynamics may affect network security under attacks. In particular, we review two related problems: attack-induced cascading breakdown and range-based attacks on links. A cascade in a network means the failure of a substantial fraction of the entire network in a cascading manner, which can be induced by the failure of or attacks on only a few nodes. These have been reported for the internet and for the power grid (e.g., the August 10, 1996 failure of the western United States power grid). We study a mechanism for cascades in complex networks by constructing a model incorporating the flows of information and physical quantities in the network. Using this model we can also show that the cascading phenomenon can be understood as a phase transition in terms of the key parameter characterizing the node capacity. For a parameter value below the phase-transition point, cascading failures can cause the network to disintegrate almost entirely. We will show how to obtain a theoretical estimate for the phase-transition point. The second problem is motivated by the fact that most existing works on the security of complex networks consider attacks on nodes rather than on links. We address attacks on links. Our investigation leads to the finding that many scale-free networks are more sensitive to attacks on short-range than on long-range links. Considering that the small-world phenomenon in complex networks has been identified as being due to the presence of long-range links, i.e., links connecting nodes that would otherwise be separated by a long node-to-node distance, our result, besides its importance concerning network efficiency and security, has the striking implication that the small-world property of scale-free networks is mainly due to short-range links.     

Evolving model of weighted networks inspired by scientific collaboration networks

Inspired by scientific collaboration networks (SCN), especially our empirical analysis of econophysicists network, an evolutionary model for weighted networks is proposed. Besides a new vertex added in at every time step, old vertices can also attempt to build up new links, or to reconnect the existing links. The number of connections repeated between two nodes is converted into the weight of the link. This provides a natural way for the evolution of link weight. The path-dependent preferential attachment mechanism with local information is also introduced. It increases the clustering coefficient of the network significantly. The model shows the scale-free phenomena in degree and vertex weight distribution. It also gives well qualitatively consistent behavior with the empirical results.     

Sandpile Dynamics Driven by Degree on Scale-Free Networks

We introduce a sandpile model driven by degree on scale-free networks, where the perturbation is triggered at nodes with the same degree. We numerically investigate the avalanche behaviour of sandpile driven by different degrees on scale-free networks. It is observed that the avalanche area has the same behaviour with avalanche size. When the sandpile is driven at nodes with the minimal degree, the avalanches of our model behave similarly to those of the original Bak-Tang-Wiesenfeld （BTW） model on scale-free networks. As the degree of driven nodes increases from the minimal value to the maximal value, the avalanche distribution gradually changes from a clean power law, then a mixture of Poissonian and power laws, finally to a Poisson-like distribution. The average avalanche area is found to increase with the degree of driven nodes so that perturbation triggered on higher-degree nodes will result in broader spreading of avalanche propagation.     

Anomalous transport in scale-free networks

To study transport properties of scale-free and Erdos-Rényi networks, we analyze the conductance G between two arbitrarily chosen nodes of random scale-free networks with degree distribution P(k)-k(-lambda) in which all links have unit resistance. We predict a broad range of values of G, with a power-law tail distribution phi(SF)(G)-G(-g(G)), where g(G)=2lambda-1, and confirm our predictions by simulations. The power-law tail in phi(SF)(G) leads to large values of G, signaling better transport in scale-free networks compared to Erdos-Rényi networks where the tail of the conductivity distribution decays exponentially. Based on a simple physical "transport backbone" picture we show that the conductances of scale-free and Erdos-Rényi networks are well approximated by ck(A)k(B)/(k(A)+k(B)) for any pair of nodes A and B with degrees k(A) and k(B), where c emerges as the main parameter characterizing network transport.     

Self-organization of balanced nodes in random networks with transportation bandwidths

We apply statistical physics to study the task of resource allocation in random networks with limited bandwidths along the transportation links. The mean-field approach is applicable when the connectivity is sufficiently high. It allows us to derive the resource shortage of a node as a well-defined function of its capacity. For networks with uniformly high connectivity, an efficient profile of the allocated resources is obtained, which exhibits features similar to the Maxwell construction. These results have good agreements with simulations, where nodes self-organize to balance their shortages, forming extensive clusters of nodes interconnected by unsaturated links. The deviations from the mean-field analyses show that nodes are likely to be rich in the locality of gifted neighbors. In scale-free networks, hubs make sacrifice for enhanced balancing of nodes with low connectivity.     

Theory of rumour spreading in complex social networks

We introduce a general stochastic model for the spread of rumours, and derive mean-field equations that describe the dynamics of the model on complex social networks (in particular, those mediated by the Internet). We use analytical and numerical solutions of these equations to examine the threshold behaviour and dynamics of the model on several models of such networks: random graphs, uncorrelated scale-free networks and scale-free networks with assortative degree correlations. We show that in both homogeneous networks and random graphs the model exhibits a critical threshold in the rumour spreading rate below which a rumour cannot propagate in the system. In the case of scale-free networks, on the other hand, this threshold becomes vanishingly small in the limit of infinite system size. We find that the initial rate at which a rumour spreads is much higher in scale-free networks than in random graphs, and that the rate at which the spreading proceeds on scale-free networks is further increased when assortative degree correlations are introduced. The impact of degree correlations on the final fraction of nodes that ever hears a rumour, however, depends on the interplay between network topology and the rumour spreading rate. Our results show that scale-free social networks are prone to the spreading of rumours, just as they are to the spreading of infections. They are relevant to the spreading dynamics of chain emails, viral advertising and large-scale information dissemination algorithms on the Internet.     

Scaling of mean first-passage time as efficiency measure of nodes sending information on scale-free Koch networks

Random walks on complex networks, especially scale-free networks, have attracted considerable interest in the past few years. A lot of previous work showed that the average receiving time (ART), i.e., the average of mean first-passage time (MFPT) for random walks to a given hub node (node with maximum degree) averaged over all starting points in scale-free small-world networks exhibits a sublinear or linear dependence on network order N (number of nodes), which indicates that hub nodes are very efficient in receiving information if one looks upon the random walker as an information messenger. Thus far, the efficiency of a hub node sending information on scale-free small-world networks has not been addressed yet. In this paper, we study random walks on the class of Koch networks with scale-free behavior and small-world effect. We derive some basic properties for random walks on the Koch network family, based on which we calculate analytically the average sending time (AST) defined as the average of MFPTs from a hub node to all other nodes, excluding the hub itself. The obtained closed-form expression displays that in large networks the AST grows with network order as N ln N, which is larger than the linear scaling of ART to the hub from other nodes. On the other hand, we also address the case with the information sender distributed uniformly among the Koch networks, and derive analytically the global mean first-passage time, namely, the average of MFPTs between all couples of nodes, the leading scaling of which is identical to that of AST. From the obtained results, we present that although hub nodes are more efficient for receiving information than other nodes, they display a qualitatively similar speed for sending information as non-hub nodes. Moreover, we show that that AST from a starting point (sender) to all possible targets is not sensitively affected by the sender’s location. The present findings are helpful for better understanding random walks performed on scale-free small-world networks.     

Resilience of the internet to random breakdowns

A common property of many large networks, including the Internet, is that the connectivity of the various nodes follows a scale-free power-law distribution, P(k) = ck(-alpha). We study the stability of such networks with respect to crashes, such as random removal of sites. Our approach, based on percolation theory, leads to a general condition for the critical fraction of nodes, p(c), that needs to be removed before the network disintegrates. We show analytically and numerically that for alpha0.99.     

Mitigation strategies on scale-free networks against cascading failures

According to the dynamic characteristics of the cascading propagation, we introduce a mitigation mechanism and propose four mitigation methods on four types of nodes. By the normalized average avalanche size and a new measure, we demonstrate the efficiencies of the mitigation strategies on enhancing the robustness of scale-free networks against cascading failures and give the order of the effectiveness of the mitigation strategies. Surprisingly, we find that only adopting once mitigation mechanism on a small part of the overload nodes can dramatically improve the robustness of scale-free networks. In addition, we also show by numerical simulations that the optimal mitigation method strongly depends on the total capacities of all nodes in a network and the distribution of the load in the cascading model. Therefore, according to the protection strength for scale-free networks, by the distribution of the load and the protection price of networks, we can reasonably select how many nodes and which mitigation method to efficiently protect scale-free networks at the lower price. These findings may be very useful for avoiding various cascading-failure-induced disasters in the real world and for leading to insights into the mitigation of cascading failures.     

基于超图的超网络相继故障分析

分析了快递超网络和电子元件超网络的相继故障扩散方式, 结合超图理论提出了2-section 图分析法和线图分析法, 并仿真分析了无标度超网络耦合映像格子的相继故障进程. 结果表明: 无标度超网络对外部攻击表现出了既鲁棒又脆弱的特性. 针对相继故障的不同扩散方式, 无标度超网络的相继故障行为表现出不同的特点. 超网络的相继故障行为和超网络的超度以及超边度分布有密切的联系, 也和超网络中超边的个数有关. 通过和同规模的Barabasi-Albert (BA)无标度网络对比, 在同一种攻击方式下同规模的无标度超网络都比BA 无标度网络表现出了更强的鲁棒性. 另外, 基于超边扩散的相继故障进程比基于节点扩散的相继故障进程更加缓慢.     

Routes to thermodynamic limit on scale-free networks

We show that there are two classes of finite size effects for dynamic models taking place on a scale-free topology. Some models in finite networks show a behavior that depends only on the system size N. Others present an additional distinct dependence on the upper cutoff kc of the degree distribution. Since the infinite network limit can be obtained by allowing kc to diverge with the system size in an arbitrary way, this result implies that there are different routes to the thermodynamic limit in scale-free networks. The contact process (in its mean-field version) belongs to this second class and thus our results clarify the recent discrepancy between theory and simulations with different scaling of kc reported in the literature.     

n-ary fragmentation model with nearest point flaw and maximal net force fracture

Through the distinction between “real” and “virtual” links between the nodes of a graph, we develop a set of simple rules leading to scale-free networks with a tunable degree distribution exponent. Albeit sharing some similarities with preferential attachment, our procedure is both faster than a naïve implementation of the Barabási and Albert model and exhibits different clustering properties. The model is thoroughly studied numerically and suggests that reducing the set of partners a node can connect to is important in seizing the diversity of scale-free structures.     

Dynamics of congestion transition triggered by multiple walkers on complex networks

The congestion transition triggered by multiple walkers walking along the shortest path on complex networks is numerically investigated. These networks are composed of nodes that have a finite capacity in analogy to the buffer memory of a computer. It is found that a transition from free-flow phase to congestion phase occurs at a critical walker density f_c, which varies for complex networks with different topological structures. The dynamic pictures of congestion for networks with different topological structures show that congestion on scale-free networks is a percolation process of congestion clusters, while the dynamics of congestion transition on non-scale-free networks is mainly a process of nucleation.