Diffusion processes on power-law small-world networks

Damage spreading in spatial and small-world random Boolean networks

The study of the response of complex dynamical social, biological, or technological networks to external perturbations has numerous applications. Random Boolean networks (RBNs) are commonly used as a simple generic model for certain dynamics of complex systems. Traditionally, RBNs are interconnected randomly and without considering any spatial extension and arrangement of the links and nodes. However, most real-world networks are spatially extended and arranged with regular, power-law, small-world, or other nonrandom connections. Here we explore the RBN network topology between extreme local connections, random small-world, and pure random networks, and study the damage spreading with small perturbations. We find that spatially local connections change the scaling of the Hamming distance at very low connectivities (K ≪ 1) and that the critical connectivity of stability K(s) changes compared to random networks. At higher K, this scaling remains unchanged. We also show that the Hamming distance of spatially local networks scales with a power law as the system size N increases, but with a different exponent for local and small-world networks. The scaling arguments for small-world networks are obtained with respect to the system sizes and strength of spatially local connections. We further investigate the wiring cost of the networks. From an engineering perspective, our new findings provide the key design trade-offs between damage spreading (robustness), the network's wiring cost, and the network's communication characteristics.

Random walks and search in time-varying networks

The random walk process underlies the description of a large number of real-world phenomena. Here we provide the study of random walk processes in time-varying networks in the regime of time-scale mixing, i.e., when the network connectivity pattern and the random walk process dynamics are unfolding on the same time scale. We consider a model for time-varying networks created from the activity potential of the nodes and derive solutions of the asymptotic behavior of random walks and the mean first passage time in undirected and directed networks. Our findings show striking differences with respect to the well-known results obtained in quenched and annealed networks, emphasizing the effects of dynamical connectivity patterns in the definition of proper strategies for search, retrieval, and diffusion processes in time-varying networks.

Effective number of accessed nodes in complex networks

The measurement called accessibility has been proposed as a means to quantify the efficiency of the communication between nodes in complex networks. This article reports results regarding the properties of accessibility, including its relationship with the average minimal time to visit all nodes reachable after h steps along a random walk starting from a source, as well as the number of nodes that are visited after a finite period of time. We characterize the relationship between accessibility and the average number of walks required in order to visit all reachable nodes (the exploration time), conjecture that the maximum accessibility implies the minimal exploration time, and confirm the relationship between the accessibility values and the number of nodes visited after a basic time unit. The latter relationship is investigated with respect to three types of dynamics: traditional random walks, self-avoiding random walks, and preferential random walks.

Close or connected: distance and connectivity effects on transport in networks

We develop an analytical approach that provides the dependence of the mean first-passage time (MFPT) for random walks on complex networks both on the target connectivity and on the source-target distance. Our approach puts forward two strongly different behaviors depending on the type-compact or non compact-of the random walk. In the case of non compact exploration, we show that the MFPT scales linearly with the inverse connectivity of the target and is largely independent of the starting point. On the contrary, in the compact case, the MFPT is controlled by the source-target distance, and we find that unexpectedly the target connectivity becomes irrelevant for remote targets.

Vicious Lévy flights

We study the statistics of encounters of Lévy flights by introducing the concept of vicious Lévy flights--distinct groups of walkers performing independent Lévy flights with the process terminating upon the first encounter between walkers of different groups. We show that the probability that the process survives up to time t decays as t-α at late times. We compute α up to the second order in ε expansion, where ε=σ-d, σ is the Lévy exponent, and d is the spatial dimension. For d=σ, we find the exponent of the logarithmic decay exactly. Theoretical values of the exponents are confirmed by numerical simulations. Our results indicate that walkers with smaller values of σ survive longer and are therefore more effective at avoiding each other.

Diffusion model based spectral clustering for protein-protein interaction networks

Background

A goal of systems biology is to analyze large-scale molecular networks including gene expressions and protein-protein interactions, revealing the relationships between network structures and their biological functions. Dividing a protein-protein interaction (PPI) network into naturally grouped parts is an essential way to investigate the relationship between topology of networks and their functions. However, clear modular decomposition is often hard due to the heterogeneous or scale-free properties of PPI networks.

Methodology/Principal Findings

To address this problem, we propose a diffusion model-based spectral clustering algorithm, which analytically solves the cluster structure of PPI networks as a problem of random walks in the diffusion process in them. To cope with the heterogeneity of the networks, the power factor is introduced to adjust the diffusion matrix by weighting the transition (adjacency) matrix according to a node degree matrix. This algorithm is named adjustable diffusion matrix-based spectral clustering (ADMSC). To demonstrate the feasibility of ADMSC, we apply it to decomposition of a yeast PPI network, identifying biologically significant clusters with approximately equal size. Compared with other established algorithms, ADMSC facilitates clear and fast decomposition of PPI networks.

Conclusions/Significance

ADMSC is proposed by introducing the power factor that adjusts the diffusion matrix to the heterogeneity of the PPI networks. ADMSC effectively partitions PPI networks into biologically significant clusters with almost equal sizes, while being very fast, robust and appealing simple.

Interplay between structural randomness, composite disorder, and electrical response: resonances and transient delays in complex impedance networks

We study the interplay between structural and conductivity (composite) disorder and the collective electrical response in random network models. Translating the problem of time-dependent electrical response (resonance and transient relaxation) in binary random composite networks to the framework of generalized eigenvalues, we study and analyze the scaling behavior of the density of resonances in these structures. We found that by controlling the density of shortcuts (topological randomness) and/or the composite ratio of the binary links (conductivity disorder), one can effectively shape resonance landscapes or suppress or enhance long transient delays in the corresponding random impedance networks.

Valence bond and von Neumann entanglement entropy in Heisenberg ladders

We present a direct comparison of the recently proposed valence bond entanglement entropy and the von Neumann entanglement entropy on spin-1/2 Heisenberg systems using quantum Monte Carlo and density-matrix renormalization group simulations. For one-dimensional chains we show that the valence bond entropy can be either less or greater than the von Neumann entropy; hence, it cannot provide a bound on the latter. On ladder geometries, simulations with up to seven legs are sufficient to indicate that the von Neumann entropy in two dimensions obeys an area law, even though the valence bond entanglement entropy has a multiplicative logarithmic correction.

Stripe domain coarsening in geographical small-world networks on a Euclidean lattice

We study phase ordering dynamics of spatially periodic striped patterns on the small-world network that is derived from a two-dimensional regular lattice with distance-dependent random connections. It is demonstrated numerically that addition of spatial disorder in the form of shortcuts makes the growth of domains much slower or even frozen at late times.

Naming games in two-dimensional and small-world-connected random geometric networks

We investigate a prototypical agent-based model, the naming game, on two-dimensional random geometric networks. The naming game [Baronchelli, J. Stat. Mech.: Theory Exp. (2006) P06014] is a minimal model, employing local communications that captures the emergence of shared communication schemes (languages) in a population of autonomous semiotic agents. Implementing the naming games with local broadcasts on random geometric graphs, serves as a model for agreement dynamics in large-scale, autonomously operating wireless sensor networks. Further, it captures essential features of the scaling properties of the agreement process for spatially embedded autonomous agents. Among the relevant observables capturing the temporal properties of the agreement process, we investigate the cluster-size distribution and the distribution of the agreement times, both exhibiting dynamic scaling. We also present results for the case when a small density of long-range communication links are added on top of the random geometric graph, resulting in a "small-world"-like network and yielding a significantly reduced time to reach global agreement. We construct a finite-size scaling analysis for the agreement times in this case.

Discrete surface growth process as a synchronization mechanism for scale-free complex networks

We consider the discrete surface growth process with relaxation to the minimum [F. Family, J. Phys. A 19, L441 (1986)] as a possible synchronization mechanism on scale-free networks, characterized by a degree distribution P(k) approximately k;{-lambda} , where k is the degree of a node and lambda its broadness, and compare it with the usually applied Edward-Wilkinson process (EW) [S. F. Edwards and D. R. Wilkinson, Proc. R. Soc. London, Ser. A 381, 17 (1982)]. In spite of both processes belonging to the same universality class for Euclidean lattices, in this work we demonstrate that for scale-free networks with exponents lambda<3 the scaling behavior of the roughness in the saturation cannot be explained by the EW process. Moreover, we show that for these ubiquitous cases the Edward-Wilkinson process enhances spontaneously the synchronization when the system size is increased. This nonphysical result is mainly due to finite size effects due to the underlying network. Contrarily, the discrete surface growth process does not present this flaw and is applicable for every lambda .

Nature-inspired interconnects for self-assembled large-scale network-on-chip designs

Future nanoscale electronics built up from an Avogadro number of components need efficient, highly scalable, and robust means of communication in order to be competitive with traditional silicon approaches. In recent years, the networks-on-chip (NoC) paradigm emerged as a promising solution to interconnect challenges in silicon-based electronics. Current NoC architectures are either highly regular or fully customized, both of which represent implausible assumptions for emerging bottom-up self-assembled molecular electronics that are generally assumed to have a high degree of irregularity and imperfection. Here, we pragmatically and experimentally investigate important design tradeoffs and properties of an irregular, abstract, yet physically plausible three-dimensional (3D) small-world interconnect fabric that is inspired by modern network-on-chip paradigms. We vary the framework's key parameters, such as the connectivity, number of switch nodes, and distribution of long- versus short-range connections, and measure the network's relevant communication characteristics. We further explore the robustness against link failures and the ability and efficiency to solve a simple toy problem, the synchronization task. The results confirm that (1) computation in irregular assemblies is a promising and disruptive computing paradigm for self-assembled nanoscale electronics and (2) that 3D small-world interconnect fabrics with a power-law decaying distribution of shortcut lengths are physically plausible and have major advantages over local two-dimensional and 3D regular topologies.

Synchronization in weighted uncorrelated complex networks in a noisy environment: optimization and connections with transport efficiency

Motivated by synchronization problems in noisy environments, we study the Edwards-Wilkinson process on weighted uncorrelated scale-free networks. We consider a specific form of the weights, where the strength (and the associated cost) of a link is proportional to (kikj)beta with ki and kj being the degrees of the nodes connected by the link. Subject to the constraint that the total edge cost is fixed, we find that in the mean-field approximation on uncorrelated scale-free graphs, synchronization is optimal at beta*= -1 . Numerical results, based on exact numerical diagonalization of the corresponding network Laplacian, confirm the mean-field results, with small corrections to the optimal value of beta*. Employing our recent connections between the Edwards-Wilkinson process and resistor networks, and some well-known connections between random walks and resistor networks, we also pursue a naturally related problem of optimizing performance in queue-limited communication networks utilizing local weighted routing schemes.

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.

Statistics of cycles in large networks

The occurrence of self-avoiding closed paths (cycles) in networks is studied under varying rules of wiring. As a main result, we find that the dependence between network size and typical cycle length is algebraic, (h) proportional to Nalpha, with distinct values of for different wiring rules. The Barabasi-Albert model has alpha=1. Different preferential and nonpreferential attachment rules and the growing Internet graph yield alpha<1. Computation of the statistics of cycles at arbitrary length is made possible by the introduction of an efficient sampling algorithm.

Physical realizability of small-world networks

Supplementing a lattice with long-range connections effectively models small-world networks characterized by a high local and global interconnectedness observed in systems ranging from society to the brain. If the links have a wiring cost associated with their length l, the corresponding distribution q(l) plays a crucial role. Uniform length distributions have received the most attention despite indications that q(l) approximately l(-alpha) exists-e.g., for integrated circuits, the Internet, and cortical networks. While length distributions of this type were previously examined in the context of navigability, we here discuss for such systems the emergence and physical realizability of small-world topology. Our simple argument allows us to understand under which condition and at what expense a small world results.