Transport between multiple users in complex networks

We study the transport properties of model networks such as scale-free and Erd?s-Rényi networks as well as a real network. We consider few possibilities for the trnasport problem. We start by studying the conductance G between two arbitrarily chosen nodes where each link has the same unit resistance. Our theoretical analysis for scale-free networks predicts a broad range of values of G, with a power-law tail distribution $\Phi_{\rm SF}(G)\sim G^{-g_G}$ , where g_G=2λ-1, and λ is the decay exponent for the scale-free network degree distribution. The power-law tail in Φ_SF(G) leads to large values of G, thereby significantly improving the transport in scale-free networks, compared to Erd?s-Rényi networks where the tail of the conductivity distribution decays exponentially. We develop a simple physical picture of the transport to account for the results. The other model for transport is the max-flow model, where conductance is defined as the number of link-independent paths between the two nodes, and find that a similar picture holds. The effects of distance on the value of conductance are considered for both models, and some differences emerge. We then extend our study to the case of multiple sources ans sinks, where the transport is defined between two groups of nodes. We find a fundamental difference between the two forms of flow when considering the quality of the transport with respect to the number of sources, and find an optimal number of sources, or users, for the max-flow case. A qualitative (and partially quantitative) explanation is also given.     

Detrended Fluctuation Analysis on Correlations of Complex Networks Under Attack and Repair Strategy

We analyze the correlation properties of the Erdos-Rényi random graph (RG) and the Barabási-Albert scale-free network (SF) under the attack and repair strategy with detrended fluctuation analysis (DFA). The maximum degree k representing the local property of the system, shows similar scaling behaviors for random graphs and scale-free networks. The fluctuations are quite random at short time scales but display strong anticorrelation at longer time scales under the same system size N and different repair probability pre. The average degree , revealing the statistical property of the system, exhibits completely different scaling behaviors for random graphs and scale-free networks. Random graphs display long-range power-law correlations. Scale-free networks are uncorrelated at short time scales; while anticorrelated at longer time scales and the anticorrelation becoming stronger with the increase of pre.     

Optimal paths in disordered complex networks

We study the optimal distance in networks, l(opt), defined as the length of the path minimizing the total weight, in the presence of disorder. Disorder is introduced by assigning random weights to the links or nodes. For strong disorder, where the maximal weight along the path dominates the sum, we find that l(opt) approximately N(1/3) in both Erdos-Rényi (ER) and Watts-Strogatz (WS) networks. For scale-free (SF) networks, with degree distribution P(k) approximately k(-lambda), we find that l(opt) scales as N((lambda-3)/(lambda-1)) for 3 or =4. Thus, for these networks, the small-world nature is destroyed. For 2相似文献   

Clique percolation in random networks

The notion of k-clique percolation in random graphs is introduced, where k is the size of the complete subgraphs whose large scale organizations are analytically and numerically investigated. For the Erdos-Rényi graph of N vertices we obtain that the percolation transition of k-cliques takes place when the probability of two vertices being connected by an edge reaches the threshold p(c) (k) = [(k - 1)N](-1/(k - 1)). At the transition point the scaling of the giant component with N is highly nontrivial and depends on k. We discuss why clique percolation is a novel and efficient approach to the identification of overlapping communities in large real networks.     

Impact of degree heterogeneity on the behavior of trapping in Koch networks

Previous work shows that the mean first-passage time (MFPT) for random walks to a given hub node (node with maximum degree) in uncorrelated random scale-free networks is closely related to the exponent γ of power-law degree distribution P(k) ～ k(-γ), which describes the extent of heterogeneity of scale-free network structure. However, extensive empirical research indicates that real networked systems also display ubiquitous degree correlations. In this paper, we address the trapping issue on the Koch networks, which is a special random walk with one trap fixed at a hub node. The Koch networks are power-law with the characteristic exponent γ in the range between 2 and 3, they are either assortative or disassortative. We calculate exactly the MFPT that is the average of first-passage time from all other nodes to the trap. The obtained explicit solution shows that in large networks the MFPT varies lineally with node number N, which is obviously independent of γ and is sharp contrast to the scaling behavior of MFPT observed for uncorrelated random scale-free networks, where γ influences qualitatively the MFPT of trapping problem.     

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.     

Scale-free network growth by ranking

Network growth is currently explained through mechanisms that rely on node prestige measures, such as degree or fitness. In many real networks, those who create and connect nodes do not know the prestige values of existing nodes but only their ranking by prestige. We propose a criterion of network growth that explicitly relies on the ranking of the nodes according to any prestige measure, be it topological or not. The resulting network has a scale-free degree distribution when the probability to link a target node is any power-law function of its rank, even when one has only partial information of node ranks. Our criterion may explain the frequency and robustness of scale-free degree distributions in real networks, as illustrated by the special case of the Web graph.     

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.     

Tricritical point in heterogeneous k-core percolation

k-core percolation is an extension of the concept of classical percolation and is particularly relevant to understanding the resilience of complex networks under random damage. A new analytical formalism has been recently proposed to deal with heterogeneous k-cores, where each vertex is assigned a local threshold k(i). In this Letter we identify a binary mixture of heterogeneous k-cores which exhibits a tricritical point. We investigate the new scaling scenario and calculate the relevant critical exponents, by analytical and computational methods, for Erd?s-Rényi networks and 2D square lattices.     

Continuous Weight Attack on Complex Network

We introduce a continuous weight attack strategy and numerically investigate the effect of continuous weight attack strategy on the Barabasi-Albert （BA） scale-free network and the Erdos-Rdnyi （ER） random network. We use a weight coefficient ω to define the attack intensity. The weight coefficient ω increases continuously from 1 to infinity, where 1 represents no attack and infinity represents complete destructive attack. Our results show that the continuous weight attack on two selected nodes with small ω （ω≈ 3） could achieve the same damage of complete elimination of a single selected node on both BA and ER networks. It is found that the continuous weight attack on a single selected edge with small ω （ω≈ 2） can reach the same effect of complete elimination of a single edge on BA network, but on ER network the damage of the continuous weight attack on a single edge is c/ose to but always smaller than that of complete elimination of edge even if ω is very large.     

Complete condensation in a zero range process on scale-free networks

We study a zero range process on scale-free networks in order to investigate how network structure influences particle dynamics. The zero range process is defined with the rate p(n) = n(delta) at which particles hop out of nodes with n particles. We show analytically that a complete condensation occurs when delta < or = delta(c) triple bond 1/(gamma-1) where gamma is the degree distribution exponent of the underlying networks. In the complete condensation, those nodes whose degree is higher than a threshold are occupied by macroscopic numbers of particles, while the other nodes are occupied by negligible numbers of particles. We also show numerically that the relaxation time follows a power-law scaling tau approximately L(z) with the network size L and a dynamic exponent z in the condensed phase.     

Robustness of a network of networks

Network research has been focused on studying the properties of a single isolated network, which rarely exists. We develop a general analytical framework for studying percolation of n interdependent networks. We illustrate our analytical solutions for three examples: (i) For any tree of n fully dependent Erd?s-Rényi (ER) networks, each of average degree k, we find that the giant component is P∞ =p[1-exp(-kP∞)](n) where 1-p is the initial fraction of removed nodes. This general result coincides for n = 1 with the known second-order phase transition for a single network. For any n>1 cascading failures occur and the percolation becomes an abrupt first-order transition. (ii) For a starlike network of n partially interdependent ER networks, P∞ depends also on the topology-in contrast to case (i). (iii) For a looplike network formed by n partially dependent ER networks, P∞ is independent of n.     

Experimental evidence for the interplay between individual wealth and transaction network

We conduct a market experiment with human agents in order to explore the structure of transaction networks and to study the dynamics of wealth accumulation. The experiment is carried out on our platform for 97 days with 2,095 effective participants and 16,936 times of transactions. From these data, the hybrid distribution (log-normal bulk and power-law tail) in the wealth is observed and we demonstrate that the transaction networks in our market are always scale-free and disassortative even for those with the size of the order of few hundred. We further discover that the individual wealth is correlated with its degree by a power-law function which allows us to relate the exponent of the transaction network degree distribution to the Pareto index in wealth distribution.     

Return probability for random walks on scale-free complex trees

The time course of random processes usually differs depending on the topology of complex networks which are a substrate for the process. However, as this Letter demonstrates, the first-return as well as the survival probabilities for random walks on the scale-free (SF) trees decay in time according to the same invariant power-law behavior. This means that both quantities are independent of the node power-law degree distributions which are distinguished by different scaling exponents. It is also shown here that the crucial property of the networks, affecting the dynamics of random walks, is their tree-like topology and not SF architecture. All analytical results quantifying these predictions have been verified through extensive computer simulations.     

Degree and wealth distribution in a network induced by wealth

A network induced by wealth is a social network model in which wealth induces individuals to participate as nodes, and every node in the network produces and accumulates wealth utilizing its links. More specifically, at every time step a new node is added to the network, and a link is created between one of the existing nodes and the new node. Innate wealth-producing ability is randomly assigned to every new node, and the node to be connected to the new node is chosen randomly, with odds proportional to the accumulated wealth of each existing node. Analyzing this network using the mean value and continuous flow approaches, we derive a relation between the conditional expectations of the degree and the accumulated wealth of each node. From this relation, we show that the degree distribution of the network induced by wealth is scale-free. We also show that the wealth distribution has a power-law tail and satisfies the 80/20 rule. We also show that, over the whole range, the cumulative wealth distribution exhibits the same topological characteristics as the wealth distributions of several networks based on the Bouchaud-Mèzard model, even though the mechanism for producing wealth is quite different in our model. Further, we show that the cumulative wealth distribution for the poor and middle class seems likely to follow by a log-normal distribution, while for the richest, the cumulative wealth distribution has a power-law behavior.     

Mobile user forecast and power-law acceleration invariance of scale-free networks

This paper studies and predicts the number growth of China's mobile users by using the power-law regression. We find that the number growth of the mobile users follows a power law. Motivated by the data on the evolution of the mobile users, we consider scenarios of self-organization of accelerating growth networks into scale-free structures and propose a directed network model, in which the nodes grow following a power-law acceleration. The expressions for the transient and the stationary average degree distributions are obtained by using the Poisson process. This result shows that the model generates appropriate power-law connectivity distributions. Therefore, we find a power-law acceleration invariance of the scale-free networks. The numerical simulations of the models agree with the analytical results well.     

基于复杂网络理论的北京公交网络拓扑性质分析

为分析公交复杂网络的拓扑性质, 本文以北京市为例, 选取截止到2010年7月的北京全市(14区、2县)的1165条公交线路和9618个公交站点为样本数据, 运用复杂网络理论构建起基于邻接站点的有向加权复杂网络模型. 该方法以公交站点作为节点, 相邻站点之间的公交线路作为边, 使得网络既具有复杂网络的拓扑性质同时节点(站点)又具有明确的地理坐标. 对网络中节点度、点强度、强度分布、平均最短路径、聚类系数等性质的分析显示, 公交复杂网络的度和点强度分布极为不均, 网络中前5%和前10%节点的累计强度分布分别达到22.43%和43.02%; 点强度与排列序数、累积强度分布都服从幂律分布, 具有无标度和小世界的网络特点, 少数关键节点在网络中发挥着重要的连接作用. 为分析复杂网络中的关键节点, 本文通过承载压力分析和基于"掠夺" 的区域中心节点提取两种方法, 得到了公交复杂网络中两类不同表现的关键节点. 这些规律也为优化城市公交网络及交通规划发展提供了新的参考建议.     

False Positive and False Negative Effects on Network Attacks

Robustness against attacks serves as evidence for complex network structures and failure mechanisms that lie behind them. Most often, due to detection capability limitation or good disguises, attacks on networks are subject to false positives and false negatives, meaning that functional nodes may be falsely regarded as compromised by the attacker and vice versa. In this work, we initiate a study of false positive/negative effects on network robustness against three fundamental types of attack strategies, namely, random attacks (RA), localized attacks (LA), and targeted attack (TA). By developing a general mathematical framework based upon the percolation model, we investigate analytically and by numerical simulations of attack robustness with false positive/negative rate (FPR/FNR) on three benchmark models including Erd?s-Rényi (ER) networks, random regular (RR) networks, and scale-free (SF) networks. We show that ER networks are equivalently robust against RA and LA only when FPR equals zero or the initial network is intact. We find several interesting crossovers in RR and SF networks when FPR is taken into consideration. By defining the cost of attack, we observe diminishing marginal attack efficiency for RA, LA, and TA. Our finding highlights the potential risk of underestimating or ignoring FPR in understanding attack robustness. The results may provide insights into ways of enhancing robustness of network architecture and improve the level of protection of critical infrastructures.     

Robustness analysis of network controllability

Structural controllability, which is an interesting property of complex networks, attracts many researchers from various fields. The maximum matching algorithm was recently applied to explore the minimum number of driver nodes, where control signals are injected, for controlling the whole network. Here we study the controllability of directed Erdös–Rényi and scale-free networks under attacks and cascading failures. Results show that degree-based attacks are more efficient than random attacks on network structural controllability. Cascade failures also do great harm to network controllability even if they are triggered by a local node failure.     

一种能耗均衡的无线传感器网络加权无标度拓扑研究

针对无线传感器网络节点能耗不均衡问题,通过对节点生命期建模,得出节点生命期受节点剩余能量和通信距离的影响,进而将两端节点生命期作为构建拓扑时边权重的影响因子,通过边权重控制节点权重,最终得出了一种能耗均衡的无线传感器网络加权无标度拓扑模型,并理论证明了该模型的点权、边权和节点度均服从幂律分布.实验结果表明,该模型具有无标度拓扑的强容错性,并有效的均衡了网络中的节点能耗,延长了网络的生命期.