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.     

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.     

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.     

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.     

Loop statistics in complex networks

We study a scaling property of the number M_h(N) of loops of size h in complex networks with respect to a network size N. For networks with a bounded second moment of degree, we find two distinct scaling behaviors: M_h(N) ~ (constant) and M_h(N) ~ lnN as N increases. Uncorrelated random networks specified only with a degree distribution and Markovian networks specified only with a nearest neighbor degree-degree correlation display the former scaling behavior, while growing network models display the latter. The difference is attributed to structural correlation that cannot be captured by a short-range degree-degree correlation.     

Distinct Clusterings and Characteristic Path Lengths in Dynamic Small-World Networks with Identical Limit Degree Distribution

Many real-world networks belong to a particular class of structures, known as small-world networks, that display short distance between pair of nodes. In this paper, we introduce a simple family of growing small-world networks where both addition and deletion of edges are possible. By tuning the deletion probability q _t , the model undergoes a transition from large worlds to small worlds. By making use of analytical or numerical means we determine the degree distribution, clustering coefficient and average path length of our networks. Surprisingly, we find that two similar evolving mechanisms, which provide identical degree distribution under a reciprocal scaling as t goes to infinity, can lead to quite different clustering behaviors and characteristic path lengths. It is also worth noting that Farey graphs constitute the extreme case q _t ??0 of our random construction.     

Complex networks renormalization: flows and fixed points

Recently, it has been claimed that some complex networks are self-similar under a convenient renormalization procedure. We present a general method to study renormalization flows in graphs. We find that the behavior of some variables under renormalization, such as the maximum number of connections of a node, obeys simple scaling laws, characterized by critical exponents. This is true for any class of graphs, from random to scale-free networks, from lattices to hierarchical graphs. Therefore, renormalization flows for graphs are similar as in the renormalization of spin systems. An analysis of classic renormalization for percolation and the Ising model on the lattice confirms this analogy. Critical exponents and scaling functions can be used to classify graphs in universality classes, and to uncover similarities between graphs that are inaccessible to a standard analysis.     

Cross over of recurrence networks to random graphs and random geometric graphs

Recurrence networks are complex networks constructed from the time series of chaotic dynamical systems where the connection between two nodes is limited by the recurrence threshold. This condition makes the topology of every recurrence network unique with the degree distribution determined by the probability density variations of the representative attractor from which it is constructed. Here we numerically investigate the properties of recurrence networks from standard low-dimensional chaotic attractors using some basic network measures and show how the recurrence networks are different from random and scale-free networks. In particular, we show that all recurrence networks can cross over to random geometric graphs by adding sufficient amount of noise to the time series and into the classical random graphs by increasing the range of interaction to the system size. We also highlight the effectiveness of a combined plot of characteristic path length and clustering coefficient in capturing the small changes in the network characteristics.     

Self-similar scaling of density in complex real-world networks

Despite their diverse origin, networks of large real-world systems reveal a number of common properties including small-world phenomena, scale-free degree distributions and modularity. Recently, network self-similarity as a natural outcome of the evolution of real-world systems has also attracted much attention within the physics literature. Here we investigate the scaling of density in complex networks under two classical box-covering renormalizations–network coarse-graining–and also different community-based renormalizations. The analysis on over 50 real-world networks reveals a power-law scaling of network density and size under adequate renormalization technique, yet irrespective of network type and origin. The results thus advance a recent discovery of a universal scaling of density among different real-world networks [P.J. Laurienti, K.E. Joyce, Q.K. Telesford, J.H. Burdette, S. Hayasaka, Universal fractal scaling of self-organized networks, Physica A 390 (20) (2011) 3608–3613] and imply an existence of a scale-free density also within–among different self-similar scales of–complex real-world networks. The latter further improves the comprehension of self-similar structure in large real-world networks with several possible applications.     

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.     

Agreement dynamics of finite-memory language games on networks

We propose a Finite-Memory Naming Game (FMNG) model with respect to the bounded rationality of agents or finite resources for information storage in communication systems. We study its dynamics on several kinds of complex networks, including random networks, small-world networks and scale-free networks. We focus on the dynamics of the FMNG affected by the memory restriction as well as the topological properties of the networks. Interestingly, we found that the most important quantity, the convergence time of reaching the consensus, shows some non-monotonic behaviors by varying the average degrees of the networks with the existence of the fastest convergence at some specific average degrees. We also investigate other main quantities, such as the success rate in negotiation, the total number of words in the system and the correlations between agents of full memory and the total number of words, which clearly explain the nontrivial behaviors of the convergence. We provide some analytical results which help better understand the dynamics of the FMNG. We finally report a robust scaling property of the convergence time, which is regardless of the network structure and the memory restriction.     

Role of fractal dimension in random walks on scale-free networks

Fractal dimension is central to understanding dynamical processes occurring on networks; however, the relation between fractal dimension and random walks on fractal scale-free networks has been rarely addressed, despite the fact that such networks are ubiquitous in real-life world. In this paper, we study the trapping problem on two families of networks. The first is deterministic, often called (x,y)-flowers; the other is random, which is a combination of (1,3)-flower and (2,4)-flower and thus called hybrid networks. The two network families display rich behavior as observed in various real systems, as well as some unique topological properties not shared by other networks. We derive analytically the average trapping time for random walks on both the (x,y)-flowers and the hybrid networks with an immobile trap positioned at an initial node, i.e., a hub node with the highest degree in the networks. Based on these analytical formulae, we show how the average trapping time scales with the network size. Comparing the obtained results, we further uncover that fractal dimension plays a decisive role in the behavior of average trapping time on fractal scale-free networks, i.e., the average trapping time decreases with an increasing fractal dimension.     

Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices

In this paper, firstly, we study analytically the topological features of a family of hierarchical lattices (HLs) from the view point of complex networks. We derive some basic properties of HLs controlled by a parameter q: scale-free degree distribution with exponent γ=2+ln 2/(ln q), null clustering coefficient, power-law behavior of grid coefficient, exponential growth of average path length (non-small-world), fractal scaling with dimension d_B=ln (2q)/(ln 2), and disassortativity. Our results show that scale-free networks are not always small-world, and support the conjecture that self-similar scale-free networks are not assortative. Secondly, we define a deterministic family of graphs called small-world hierarchical lattices (SWHLs). Our construction preserves the structure of hierarchical lattices, including its degree distribution, fractal architecture, clustering coefficient, while the small-world phenomenon arises. Finally, the dynamical processes of intentional attacks and collective synchronization are studied and the comparisons between HLs and Barabási-Albert (BA) networks as well as SWHLs are shown. We find that the self-similar property of HLs and SWHLs significantly increases the robustness of such networks against targeted damage on hubs, as compared to the very vulnerable non fractal BA networks, and that HLs have poorer synchronizability than their counterparts SWHLs and BA networks. We show that degree distribution of scale-free networks does not suffice to characterize their synchronizability, and that networks with smaller average path length are not always easier to synchronize.     

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.     

Some physical applications of random hierarchical matrices

The investigation of spectral properties of random block-hierarchical matrices as applied to dynamic and structural characteristics of complex hierarchical systems with disorder is proposed for the first time. Peculiarities of dynamics on random ultrametric energy landscapes are discussed and the statistical properties of scale-free and polyscale (depending on the topological characteristics under investigation) random hierarchical networks (graphs) obtained by multiple mapping are considered.     

Enhancement of scale-free network attack tolerance

Despite the large size of most communication and transportation systems,there are short paths between nodes in these networks which guarantee the efficient information,data and passenger delivery;furthermore these networks have a surprising tolerance under random errors thanks to their inherent scale-free topology.However,their scale-free topology also makes them fragile under intentional attacks,leaving us a challenge on how to improve the network robustness against intentional attacks without losing their strong tolerance under random errors and high message and passenger delivering capacity.Here we propose two methods (SL method and SH method) to enhance scale-free network’s tolerance under attack in different conditions.     

Error and attack tolerance of evolving networks with local preferential attachment

Networks generated by local-world evolving network model display a transition from exponential network to power-law network with respect to connectivity distribution. We investigate statistical properties of the evolving networks and the responses of these networks under random errors and intentional attacks. It has been found that local world size M has great effect on the network's heterogeneity, thus leading to transitional behaviors in network's robustness against errors and attacks. Numerical results show that networks constructed with local preferential attachment mechanism can maintain the robustness of scale-free networks under random errors and concurrently improve reliance against targeted attacks on highly connected nodes.     

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.     

Resilience of public transport networks against attacks

The behavior of complex networks under failure or attack depends strongly on the specific scenario. Of special interest are scale-free networks, which are usually seen as robust under random failure but appear to be especially vulnerable to targeted attacks. In recent studies of public transport networks of fourteen major cities of the world it was shown that these systems when represented by appropriate graphs may exhibit scale-free behavior [Physica A 380, 585 (2007); Eur. Phys. J. B 68, 261 (2009)]. Our present analysis focuses on the effects that defunct or removed nodes have on the properties of public transport networks. Simulating different directed attack strategies, we derive vulnerability criteria that result in minimal strategies with high impact on these systems.     

Reducing congestion on complex networks by dynamic relaxation processes

We study the effects of relaxational dynamics on the congestion pressure in general transport networks. We show that the congestion pressure is reduced in scale-free networks if a relaxation mechanism is utilized, while this is in general not the case for non-scale-free graphs such as random graphs. We also present evidence supporting the idea that the emergence of scale-free networks arise from optimization mechanisms to balance the load of the networks nodes.