Relaxation properties of small-world networks

The Mixing Time of the Newman-Watts Small-World Model

‘Small worlds’ are large systems in which any given node has only a few connections to other points, but possessing the property that all pairs of points are connected by a short path, typically logarithmic in the number of nodes. The use of random walks for sampling a uniform element from a large state space is by now a classical technique; to prove that such a technique works for a given network, a bound on the mixing time is required. However, little detailed information is known about the behaviour of random walks on small-world networks, though many predictions can be found in the physics literature. The principal contribution of this paper is to show that for a famous small-world random graph model known as the Newman-Watts small-world model, the mixing time is of order log2 n. This confirms a prediction of Richard Durrett [5, page 22], who proved a lower bound of order log2 n and an upper bound of order log3 n.

The Mixing Time of the Newman-Watts Small-World Model

‘Small worlds’ are large systems in which any given node has only a few connections to other points, but possessing the property that all pairs of points are connected by a short path, typically logarithmic in the number of nodes. The use of random walks for sampling a uniform element from a large state space is by now a classical technique; to prove that such a technique works for a given network, a bound on the mixing time is required. However, little detailed information is known about the behaviour of random walks on small-world networks, though many predictions can be found in the physics literature. The principal contribution of this paper is to show that for a famous small-world random graph model known as the Newman-Watts small-world model, the mixing time is of order log2n. This confirms a prediction of Richard Durrett [5, page 22], who proved a lower bound of order log2n and an upper bound of order log3n.

Laplacian spectra of a class of small-world networks and their applications

One of the most crucial domains of interdisciplinary research is the relationship between the dynamics and structural characteristics. In this paper, we introduce a family of small-world networks, parameterized through a variable d controlling the scale of graph completeness or of network clustering. We study the Laplacian eigenvalues of these networks, which are determined through analytic recursive equations. This allows us to analyze the spectra in depth and to determine the corresponding spectral dimension. Based on these results, we consider the networks in the framework of generalized Gaussian structures, whose physical behavior is exemplified on the relaxation dynamics and on the fluorescence depolarization under quasiresonant energy transfer. Although the networks have the same number of nodes (beads) and edges (springs) as the dual Sierpinski gaskets, they display rather different dynamic behavior.

Full-counting statistics of random transition-rate matrices

We study the full-counting statistics of current of large open systems through the application of random-matrix theory to transition-rate matrices. We develop a method for calculating the ensemble-averaged current-cumulant generating functions based on an expansion in terms of the inverse system size. We investigate how different symmetry properties and different counting schemes affect the results.

Topological effects on dynamics in complex pulse-coupled networks of integrate-and-fire type

For a class of integrate-and-fire, pulse-coupled networks with complex topology, we study the dependence of the pulse rate on the underlying architectural connectivity statistics. We derive the distribution of the pulse rate from this dependence and determine when the underlying scale-free architectural connectivity gives rise to a scale-free pulse-rate distribution. We identify the scaling of the pairwise coupling between the dynamical units in this network class that keeps their pulse rates bounded in the infinite-network limit. In the process, we determine the connectivity statistics for a specific scale-free network grown by preferential attachment.

Dynamic model of time-dependent complex networks

The characterization of the "most connected" nodes in static or slowly evolving complex networks has helped in understanding and predicting the behavior of social, biological, and technological networked systems, including their robustness against failures, vulnerability to deliberate attacks, and diffusion properties. However, recent empirical research of large dynamic networks (characterized by irregular connections that evolve rapidly) has demonstrated that there is little continuity in degree centrality of nodes over time, even when their degree distributions follow a power law. This unexpected dynamic centrality suggests that the connections in these systems are not driven by preferential attachment or other known mechanisms. We present an approach to explain real-world dynamic networks and qualitatively reproduce these dynamic centrality phenomena. This approach is based on a dynamic preferential attachment mechanism, which exhibits a sharp transition from a base pure random walk scheme.

Hierarchical mean-field model describing relaxation in a small-world network

This Brief Report presents the hierarchical reaction-diffusion partial differential equations (PDE) system, which reproduces a mean-square displacement and a density relaxation process corresponding to the anomalous diffusion on a small-world network. These results are confirmed by the comparison with the known direct numerical simulations.

Unusual percolation in simple small-world networks

We present an exact solution of percolation in a generalized class of Watts-Strogatz graphs defined on a one-dimensional underlying lattice. We find a nonclassical critical point in the limit of the number of long-range bonds in the system going to zero, with a discontinuity in the percolation probability and a divergence in the mean finite-cluster size. We show that the critical behavior falls into one of three regimes depending on the proportion of occupied long-range to unoccupied nearest-neighbor bonds, with each regime being characterized by different critical exponents. The three regimes can be united by a single scaling function around the critical point. These results can be used to identify the number of long-range links necessary to secure connectivity in a communication or transportation chain. As an example, we can resolve the communication problem in a game of "telephone."

Quantum transport on small-world networks: a continuous-time quantum walk approach

We consider the quantum mechanical transport of (coherent) excitons on small-world networks (SWNs). The SWNs are built from a one-dimensional ring of N nodes by randomly introducing B additional bonds between them. The exciton dynamics is modeled by continuous-time quantum walks, and we evaluate numerically the ensemble-averaged transition probability to reach any node of the network from the initially excited one. For sufficiently large B we find that the quantum mechanical transport through the SWNs is, first, very fast, given that the limiting value of the transition probability is reached very quickly, and second, that the transport does not lead to equipartition, given that on average the exciton is most likely to be found at the initial node.

Scaling property of flux fluctuations from random walks

We study dynamical scaling of flux fluctuation sigma(t) from the one-random-walker model on regular lattices and complex networks and compare it to the surface width W(t) of a corresponding growth model. On the regular lattices, we analytically show that sigma(t) undergoes a crossover from the nontrivial scaling regime to the trivial one by increasing time t, and we verify the results by numerical simulations. In contrast to the results on the regular lattices, sigma(t) does not show any crossover behavior on complex networks and satisfies the scaling relation sigma(t) approximately t(1/2) for any t. On the other hand, we show that W(t) of the corresponding model on complex networks has two different scaling regimes, W approximately t(1/2) for t<<N and W(t) approximately t for t>>N .

Dynamics of information access on the web

While current studies on complex networks focus on systems that change relatively slowly in time, the structure of the most visited regions of the web is altered at the time scale from hours to days. Here we investigate the dynamics of visitation of a major news portal, representing the prototype for such a rapidly evolving network. The nodes of the network can be classified into stable nodes, which form the time-independent skeleton of the portal, and news documents. The visitations of the two node classes are markedly different, the skeleton acquiring visits at a constant rate, while a news document's visitation peaks after a few hours. We find that the visitation pattern of a news document decays as a power law, in contrast with the exponential prediction provided by simple models of site visitation. This is rooted in the inhomogeneous nature of the browsing pattern characterizing individual users: the time interval between consecutive visits by the same user to the site follows a power-law distribution, in contrast to the exponential expected for Poisson processes. We show that the exponent characterizing the individual user's browsing patterns determines the power-law decay in a document's visitation. Finally, our results document the fleeting quality of news and events: while fifteen minutes of fame is still an exaggeration in the online media, we find that access to most news items significantly decays after 36 hours of posting.

Synchronization landscapes in small-world-connected computer networks

Motivated by a synchronization problem in distributed computing we studied a simple growth model on regular and small-world networks, embedded in one and two dimensions. We find that the synchronization landscape (corresponding to the progress of the individual processors) exhibits Kardar-Parisi-Zhang-like kinetic roughening on regular networks with short-range communication links. Although the processors, on average, progress at a nonzero rate, their spread (the width of the synchronization landscape) diverges with the number of nodes (desynchronized state) hindering efficient data management. When random communication links are added on top of the one and two-dimensional regular networks (resulting in a small-world network), large fluctuations in the synchronization landscape are suppressed and the width approaches a finite value in the large system-size limit (synchronized state). In the resulting synchronization scheme, the processors make close-to-uniform progress with a nonzero rate without global intervention. We obtain our results by "simulating the simulations," based on the exact algorithmic rules, supported by coarse-grained arguments.

Efficiency of quantum and classical transport on graphs

We propose a measure to quantify the efficiency of classical and quantum mechanical transport processes on graphs. The measure only depends on the density of states (DOS), which contains all the necessary information about the graph. For some given (continuous) DOS, the measure shows a power law behavior, where the exponent for the quantum transport is twice the exponent of its classical counterpart. For small-world networks, however, the measure shows rather a stretched exponential law but still the quantum transport outperforms the classical one. Some finite tree graphs have a few highly degenerate eigenvalues, such that, on the other hand, on them the classical transport may be more efficient than the quantum one.

Elastic properties of small-world spring networks

We construct small-world spring networks based on a one-dimensional chain and study its static and quasistatic behavior with respect to external forces. Regular bonds and shortcuts are assigned linear springs of constant k and k', respectively. In our models, shortcuts can only stand extensions less than deltac beyond which they are removed from the network. First we consider the simple cases of a hierarchical small-world network and a complete network. In the main part of this paper we study random small-world networks (RSWN) in which each pair of nodes is connected by a shortcut with probability p. We obtain a scaling relation for the effective stiffness of RSWN when k=k'. In this case the extension distribution of shortcuts is scale free with the exponent -2. There is a strong positive correlation between the extension of shortcuts and their betweenness. We find that the chemical end-to-end distance (CEED) could change either abruptly or continuously with respect to the external force. In the former case, the critical force is determined by the average number of shortcuts emanating from a node. In the latter case, the distribution of changes in CEED obeys power laws of the exponent -alpha with alpha < or = 3/2.

Fermi-Dirac statistics and traffic in complex networks

We propose an idealized model for traffic in a network, in which many particles move randomly from node to node, following the network's links, and it is assumed that at most one particle can occupy any given node. This is intended to mimic the finite forwarding capacity of nodes in communication networks, thereby allowing the possibility of congestion and jamming phenomena. We show that the particles behave like free fermions, with appropriately defined energy-level structure and temperature. The statistical properties of this system are thus given by the corresponding Fermi-Dirac distribution. We use this to obtain analytical expressions for dynamical quantities of interest, such as the mean occupation of each node and the transport efficiency, for different network topologies and particle densities. We show that the subnetwork of free nodes always fragments into small isolated clusters for a sufficiently large number of particles, implying a communication breakdown at some density for all network topologies. These results are compared to direct simulations.

Exploring complex networks by walking on them

We carry out a comparative study of the problem of a walker searching several typical complex networks. The search efficiency is evaluated for various strategies. Having no knowledge of the global properties of the underlying networks and the optimal path between any two given nodes, it is found that the best search strategy is the self-avoiding random walk. The preferentially self-avoiding random walk does not help in improving the search efficiency further. In return, topological information of the underlying networks may be drawn by comparing the results of the different search strategies.

Scaling of directed dynamical small-world networks with random responses

A dynamical model of small-world networks, with directed links which describe various correlations in social and natural phenomena, is presented. Random responses of sites to the input message are introduced to simulate real systems. The interplay of these ingredients results in the collective dynamical evolution of a spinlike variable S(t) of the whole network. The global average spreading length <L>(s) and average spreading time <T>(s) are found to scale as p(-alpha)ln(N with different exponents. Meanwhile, S(t) behaves in a duple scaling form for N>>N(*): S approximately f(p(-beta)q(gamma)t), where p and q are rewiring and external parameters, alpha, beta, and gamma are scaling exponents, and f(t) is a universal function. Possible applications of the model are discussed.

Random walks on complex networks

We investigate random walks on complex networks and derive an exact expression for the mean first-passage time (MFPT) between two nodes. We introduce for each node the random walk centrality C, which is the ratio between its coordination number and a characteristic relaxation time, and show that it determines essentially the MFPT. The centrality of a node determines the relative speed by which a node can receive and spread information over the network in a random process. Numerical simulations of an ensemble of random walkers moving on paradigmatic network models confirm this analytical prediction.

Constrained spin-dynamics description of random walks on hierarchical scale-free networks

We study a random walk problem on the hierarchical network which is a scale-free network grown deterministically. The random walk problem is mapped onto a dynamical Ising spin chain system in one dimension with a nonlocal spin update rule, which allows an analytic approach. We show analytically that the characteristic relaxation time scale grows algebraically with the total number of nodes N as T--N(z). From a scaling argument, we also show the power-law decay of the autocorrelation function C(sigma)(t)--t(-alpha), which is the probability to find the Ising spins in the initial state sigma after t time steps, with the state-dependent nonuniversal exponent alpha. It turns out that the power-law scaling behavior has its origin in a quasiultrametric structure of the configuration space.

Scaling properties of random walks on small-world networks

Using both numerical simulations and scaling arguments, we study the behavior of a random walker on a one-dimensional small-world network. For the properties we study, we find that the random walk obeys a characteristic scaling form. These properties include the average number of distinct sites visited by the random walker, the mean-square displacement of the walker, and the distribution of first-return times. The scaling form has three characteristic time regimes. At short times, the walker does not see the small-world shortcuts and effectively probes an ordinary Euclidean network in d dimensions. At intermediate times, the properties of the walker shows scaling behavior characteristic of an infinite small-world network. Finally, at long times, the finite size of the network becomes important, and many of the properties of the walker saturate. We propose general analytical forms for the scaling properties in all three regimes, and show that these analytical forms are consistent with our numerical simulations.

Self-avoiding walks and connective constants in small-world networks

Long-distance characteristics of small-world networks have been studied by means of self-avoiding walks (SAW's). We consider networks generated by rewiring links in one- and two-dimensional regular lattices. The number of SAW's u(n) was obtained from numerical simulations as a function of the number of steps n on the considered networks. The so-called connective constant, mu=lim(n-->infinity)u(n)/u(n-1), which characterizes the long-distance behavior of the walks, increases continuously with disorder strength (or rewiring probability p). For small p, one has a linear relation mu=mu(0)+ap, mu(0) and a being constants dependent on the underlying lattice. Close to p=1 one finds the behavior expected for random graphs. An analytical approach is given to account for the results derived from numerical simulations. Both methods yield results agreeing with each other for small p, and differ for p close to 1, because of the different connectivity distributions resulting in both cases.

Introducing small-world network effects to critical dynamics

We analytically investigate the kinetic Gaussian model and the one-dimensional kinetic Ising model of two typical small-world networks (SWN), the adding type and the rewiring type. The general approaches and some basic equations are systematically formulated. The rigorous investigation of the Glauber-type kinetic Gaussian model shows the mean-field-like global influence on the dynamic evolution of the individual spins. Accordingly a simplified method is presented and tested, which is believed to be a good choice for the mean-field transition widely (in fact, without exception so far) observed for SWN. It yields the evolving equation of the Kawasaki-type Gaussian model. In the one-dimensional Ising model, the p dependence of the critical point is analytically obtained and the nonexistence of such a threshold p(c), for a finite-temperature transition, is confirmed. The static critical exponents gamma and beta are in accordance with the results of the recent Monte Carlo simulations, and also with the mean-field critical behavior of the system. We also prove that the SWN effect does not change the dynamic critical exponent z=2 for this model. The observed influence of the long-range randomness on the critical point indicates two obviously different hidden mechanisms.

Characterizing the structure of small-world networks

We give exact relations for small-world networks (SWN's) which are independent of the "degree distribution," i.e., the distribution of nearest-neighbor connections. For the original SWN model, we illustrate how these exact relations can be used to obtain approximations for the corresponding basic probability distribution. In the limit of large system sizes and small disorder, we use numerical studies to obtain a functional fit for this distribution. Finally, we obtain the scaling properties for the mean-square displacement of a random walker, which are determined by the scaling behavior of the underlying SWN.

Correlation effects in a simple model of a small-world network

We analyze the effect of correlations in a simple model of a small-world network by obtaining exact analytical expressions for the distribution of shortest paths in the network. We enter correlations into a simple model with a distinguished site, by taking the random connections to this site from an Ising distribution. Our method shows how the transfer-matrix technique can be used in the new context of small-world networks.

Scaling of random spreading in small world networks

In this study we have carried out computer simulations of random walks on Watts-Strogatz-type small world networks and measured the mean number of visited sites and the return probabilities. These quantities were found to obey scaling behavior with intuitively reasoned exponents as long as the probability p of having a long range bond was sufficiently low.

Ising model on a small world network

A one-dimensional Ising model is studied, via Monte Carlo simulations, on a small world network, where each site has, apart from couplings to its two nearest neighbors, a certain probability to be linked to one of its farther neighbors. It is demonstrated that even a small fraction of such links enables the system to order at finite temperatures. The critical exponent beta is smaller than the two-dimensional value, and seems to be independent of the concentration of the extra links. The dependence of the magnetization and the critical temperature on the concentration of the small world links is also presented.

Spectra of "real-world" graphs: beyond the semicircle law

Many natural and social systems develop complex networks that are usually modeled as random graphs. The eigenvalue spectrum of these graphs provides information about their structural properties. While the semicircle law is known to describe the spectral densities of uncorrelated random graphs, much less is known about the spectra of real-world graphs, describing such complex systems as the Internet, metabolic pathways, networks of power stations, scientific collaborations, or movie actors, which are inherently correlated and usually very sparse. An important limitation in addressing the spectra of these systems is that the numerical determination of the spectra for systems with more than a few thousand nodes is prohibitively time and memory consuming. Making use of recent advances in algorithms for spectral characterization, here we develop methods to determine the eigenvalues of networks comparable in size to real systems, obtaining several surprising results on the spectra of adjacency matrices corresponding to models of real-world graphs. We find that when the number of links grows as the number of nodes, the spectral density of uncorrelated random matrices does not converge to the semicircle law. Furthermore, the spectra of real-world graphs have specific features, depending on the details of the corresponding models. In particular, scale-free graphs develop a trianglelike spectral density with a power-law tail, while small-world graphs have a complex spectral density consisting of several sharp peaks. These and further results indicate that the spectra of correlated graphs represent a practical tool for graph classification and can provide useful insight into the relevant structural properties of real networks.

Small-world networks: links with long-tailed distributions

Small-world networks (SWN), obtained by randomly adding to a regular structure additional links (AL), are of current interest. In this paper we explore (based on physical models) a new variant of SWN, in which the probability of realizing an AL depends on the chemical distance between the connected sites. We assume a power-law probability distribution and study random walkers on the network, focusing especially on their probability of being at the origin. We connect the results to Levy flights, which follow from a mean-field variant of our model.