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.     

Thresholds for epidemic spreading in networks

We study the threshold of epidemic models in quenched networks with degree distribution given by a power-law. For the susceptible-infected-susceptible model the activity threshold λ(c) vanishes in the large size limit on any network whose maximum degree k(max) diverges with the system size, at odds with heterogeneous mean-field (HMF) theory. The vanishing of the threshold has nothing to do with the scale-free nature of the network but stems instead from the largest hub in the system being active for any spreading rate λ>1/√k(max) and playing the role of a self-sustained source that spreads the infection to the rest of the system. The susceptible-infected-removed model displays instead agreement with HMF theory and a finite threshold for scale-rich networks. We conjecture that on quenched scale-rich networks the threshold of generic epidemic models is vanishing or finite depending on the presence or absence of a steady state.     

Non-mean-field behavior of the contact process on scale-free networks

We present an analysis of the classical contact process on scale-free networks. A mean-field study, both for finite and infinite network sizes, yields an absorbing-state phase transition at a finite critical value of the control parameter, characterized by a set of exponents depending on the network structure. Since finite size effects are large and the infinite network limit cannot be reached in practice, a numerical study of the transition requires the application of finite size scaling theory. Contrary to other critical phenomena studied previously, the contact process in scale-free networks exhibits a nontrivial critical behavior that cannot be quantitatively accounted for by mean-field theory.     

The nature of explosive percolation phase transition

In this Letter, we show that the explosive percolation is a novel continuous phase transition. The order-parameter-distribution histogram at the percolation threshold is studied in Erd?s-Rényi networks, scale-free networks, and square lattice. In finite system, two well-defined Gaussian-like peaks coexist, and the valley between the two peaks is suppressed with the system size increasing. This finite-size effect always appears in typical first-order phase transition. However, both of the two peaks shift to zero point in a power law manner, which indicates the explosive percolation is continuous in the thermodynamic limit. The nature of explosive percolation in all the three structures belongs to this novel continuous phase transition. Various scaling exponents concerning the order-parameter-distribution are obtained.     

Optimization and scale-freeness for complex networks

Complex networks are mapped to a model of boxes and balls where the balls are distinguishable. It is shown that the scale-free size distribution of boxes maximizes the information associated with the boxes provided configurations including boxes containing a finite fraction of the total amount of balls are excluded. It is conjectured that for a connected network with only links between different nodes, the nodes with a finite fraction of links are effectively suppressed. It is hence suggested that for such networks the scale-free node-size distribution maximizes the information encoded on the nodes. The noise associated with the size distributions is also obtained from a maximum entropy principle. Finally, explicit predictions from our least bias approach are found to be borne out by metabolic networks.     

From topology to dynamics in biochemical networks

Abstract formulations of the regulation of gene expression as random Boolean switching networks have been studied extensively over the past three decades. These models have been developed to make statistical predictions of the types of dynamics observed in biological networks based on network topology and interaction bias, p. For values of mean connectivity chosen to correspond to real biological networks, these models predict disordered dynamics. However, chaotic dynamics seems to be absent from the functioning of a normal cell. While these models use a fixed number of inputs for each element in the network, recent experimental evidence suggests that several biological networks have distributions in connectivity. We therefore study randomly constructed Boolean networks with distributions in the number of inputs, K, to each element. We study three distributions: delta function, Poisson, and power law (scale free). We analytically show that the critical value of the interaction bias parameter, p, above which steady state behavior is observed, is independent of the distribution in the limit of the number of elements N--> infinity. We also study these networks numerically. Using three different measures (types of attractors, fraction of elements that are active, and length of period), we show that finite, scale-free networks are more ordered than either the Poisson or delta function networks below the critical point. Thus the topology of scale-free biochemical networks, characterized by a wide distribution in the number of inputs per element, may provide a source of order in living cells. (c) 2001 American Institute of Physics.     

Deterministic scale-free small-world networks of arbitrary order

In many real-life networks, both the scale-free distribution of degree and small-world behavior are important features. There are many random or deterministic models of networks to simulate these features separately. However, there are few models that combine the scale-free effect and small-world behavior, especially in terms of deterministic versions. What is more, all the existing deterministic algorithms running in the iterative mode generate networks with only several discrete numbers of nodes. This contradicts the purpose of creating a deterministic network model on which we can simulate some dynamical processes as widely as possible. According to these facts, this paper proposes a deterministic network generation algorithm, which can not only generate deterministic networks following a scale-free distribution of degree and small-world behavior, but also produce networks with arbitrary number of nodes. Our scheme is based on a complete binary tree, and each newly generated leaf node is further linked to its full brother and one of its direct ancestors. Analytical computation and simulation results show that the average degree of such a proposed network is less than 5, the average clustering coefficient is high (larger than 0.5, even for a network of size 2 million) and the average shortest path length increases much more slowly than logarithmic growth for the majority of small-world network models.     

Percolation in self-similar networks

We provide a simple proof that graphs in a general class of self-similar networks have zero percolation threshold. The considered self-similar networks include random scale-free graphs with given expected node degrees and zero clustering, scale-free graphs with finite clustering and metric structure, growing scale-free networks, and many real networks. The proof and the derivation of the giant component size do not require the assumption that networks are treelike. Our results rely only on the observation that self-similar networks possess a hierarchy of nested subgraphs whose average degree grows with their depth in the hierarchy. We conjecture that this property is pivotal for percolation in networks.     

Percolation and epidemic thresholds in clustered networks

We develop a theoretical approach to percolation in random clustered networks. We find that, although clustering in scale-free networks can strongly affect some percolation properties, such as the size and the resilience of the giant connected component, it cannot restore a finite percolation threshold. In turn, this implies the absence of an epidemic threshold in this class of networks, thus extending this result to a wide variety of real scale-free networks which shows a high level of transitivity. Our findings are in good agreement with numerical simulations.     

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.     

增长及非增长无标度网络的成因解析

分析两类无标度网络的形成原因,提出一个无标度网络演化模型并进行一系列数值实验.基于分析和实验得到推论:只要保持足够低的网络密度,通过基于度的偏好连接就可形成长期稳定的无标度网络.规模增长和点边增删既是客观存在,又起到了控制网络密度的作用,足够低的网络密度和基于度的偏好连接是所有无标度网络共同的必要条件.推论可同时解释增长和非增长无标度网络的形成原因.研究结果有助于理解各种真实无标度网络和建立相应的模型.     

Fractality and degree correlations in scale-free networks

Fractal scale-free networks are empirically known to exhibit disassortative degree mixing. It is, however, not obvious whether a negative degree correlation between nearest neighbor nodes makes a scale-free network fractal. Here we examine the possibility that disassortativity in complex networks is the origin of fractality. To this end, maximally disassortative (MD) networks are prepared by rewiring edges while keeping the degree sequence of an initial uncorrelated scale-free network. We show that there are many MD networks with different topologies if the degree sequence is the same with that of the (u,v)-flower but most of them are not fractal. These results demonstrate that disassortativity does not cause the fractal property of networks. In addition, we suggest that fractality of scale-free networks requires a long-range repulsive correlation, in the sense of the shortest path distance, in similar degrees.     

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.     

Number of loops of size h in growing scale-free networks

The hierarchical structure of scale-free networks has been investigated focusing on the scaling of the number N(h)(t) of loops of size h as a function of the system size. In particular, we have found the analytic expression for the scaling of N(h)(t) in the Barabási-Albert (BA) scale-free network. We have performed numerical simulations on the scaling law for N(h)(t) in the BA network and in other growing scale-free networks, such as the bosonic network and the aging nodes network. We show that in the bosonic network and in the aging node network the phase transitions in the topology of the network are accompained by a change in the scaling of the number of loops with the system size.     

Olami-Feder-Christensen model on different networks

We investigate numerically the Self Organized Criticality (SOC) properties of the dissipative Olami-Feder-Christensen model on small-world and scale-free networks. We find that the small-world OFC model exhibits self-organized criticality. Indeed, in this case we observe power law behavior of earthquakes size distribution with finite size scaling for the cut-off region. In the scale-free OFC model, instead, the strength of disorder hinders synchronization and does not allow to reach a critical state.     

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.     

Active transport and cluster formation on 2D networks

We introduce a model for active transport on inhomogeneous networks embedded in a diffusive environment which is motivated by vesicular transport on actin filaments. In the presence of a hard-core interaction, particle clusters are observed that exhibit an algebraically decaying distribution in a large parameter regime, indicating the existence of clusters on all scales. The scale-free behavior can be understood by a mechanism promoting preferential attachment of particles to large clusters. The results are compared with a diffusion-limited aggregation model and active transport on a regular network. For both models we observe aggregation of particles to clusters which are characterized by a finite size scale if the relevant time scales and particle densities are considered.     

Synchronizability of dynamical scale-free networks subject to random errors

In this paper the robustness of network synchronizability against random deletion of nodes, i.e. errors, in dynamical scale-free networks was studied. To this end, two measures of network synchronizability, namely, the eigenratio of the Laplacian and the order parameter quantifying the degree of phase synchrony were adopted, and the synchronizability robustness on preferential attachment scale-free graphs was investigated. The findings revealed that as the network size decreases, the robustness of its synchronizability against random removal of nodes declines, i.e. the more the number of randomly removed nodes from the network, the worse its synchronizability. We also showed that this dependence of the synchronizability on the network size is different with that in the growing scale-free networks. The profile of a number of network properties such as clustering coefficient, efficiency, assortativity, and eccentricity, as a function of the network size was investigated in these two cases, growing scale-free networks and those with randomly removed nodes. The results showed that these processes are also different in terms of these metrics.     

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

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