Localization of nonbacktracking centrality on dense subgraphs of sparse networks

The nonbacktracking matrix and the related nonbacktracking centrality (NBC) play a crucial role in models of percolation-type processes on networks, such as nonrecurrent epidemics. Here we study the localization of NBC in infinite sparse networks that contain an arbitrary finite subgraph. Assuming the local tree likeness of the enclosing network, and that branches emanating from the finite subgraph do not intersect at finite distances, we show that the largest eigenvalue of the nonbacktracking matrix of the composite network is equal to the highest of the two largest eigenvalues: that of the finite subgraph and of the enclosing network. In the localized state, when the largest eigenvalue of the subgraph is the highest of the two, we derive explicit expressions for the NBCs of nodes in the subgraph and other nodes in the network. In this state, nonbacktracking centrality is concentrated on the subgraph and its immediate neighborhood in the enclosing network. We obtain simple, exact formulas in the case where the enclosing network is uncorrelated. We find that the mean NBC decays exponentially around the finite subgraph, at a rate which is independent of the structure of the enclosing network, contrary to what was found for the localization of the principal eigenvector of the adjacency matrix. Numerical simulations confirm that our results provide good approximations even in moderately sized, loopy, real-world networks.

Sync and Swarm: Solvable Model of Nonidentical Swarmalators

We study a model of nonidentical swarmalators, generalizations of phase oscillators that both sync in time and swarm in space. The model produces four collective states: asynchrony, sync clusters, vortexlike phase waves, and a mixed state. These states occur in many real-world swarmalator systems such as biological microswimmers, chemical nanomotors, and groups of drones. A generalized Ott-Antonsen ansatz provides the first analytic description of these states and conditions for their existence. We show how this approach may be used in studies of active matter and related disciplines.

Approximating nonbacktracking centrality and localization phenomena in large networks

Message-passing theories have proved to be invaluable tools in studying percolation, nonrecurrent epidemics, and similar dynamical processes on real-world networks. At the heart of the message-passing method is the nonbacktracking matrix, whose largest eigenvalue, the corresponding eigenvector, and the closely related nonbacktracking centrality play a central role in determining how the given dynamical model behaves. Here we propose a degree-class-based method to approximate these quantities using a smaller matrix related to the joint degree-degree distribution of neighboring nodes. Our findings suggest that in most networks, degree-degree correlations beyond nearest neighbor are actually not strong, and our first-order description already results in accurate estimates, particularly when message-passing itself is a good approximation to the original model in question, that is, when the number of short cycles in the network is sufficiently low. We show that localization of the nonbacktracking centrality is also captured well by our scheme, particularly in large networks. Our method provides an alternative to working with the full nonbacktracking matrix in very large networks where this may not be possible due to memory limitations.

A data-driven model for COVID-19 pandemic - Evolution of the attack rate and prognosis for Brazil

We introduce a compartmental model SEIAHRV (Susceptible, Exposed, Infected, Asymptomatic, Hospitalized, Recovered, Vaccinated) with age structure for the spread of the SARAS-CoV virus. In order to model current different vaccines we use compartments for individuals vaccinated with one and two doses without vaccine failure and a compartment for vaccinated individual with vaccine failure. The model allows to consider any number of different vaccines with different efficacies and delays between doses. Contacts among age groups are modeled by a contact matrix and the contagion matrix is obtained from a probability of contagion p c per contact. The model uses known epidemiological parameters and the time dependent probability p c is obtained by fitting the model output to the series of deaths in each locality, and reflects non-pharmaceutical interventions. As a benchmark the output of the model is compared to two good quality serological surveys, and applied to study the evolution of the COVID-19 pandemic in the main Brazilian cities with a total population of more than one million. We also discuss with some detail the case of the city of Manaus which raised special attention due to a previous report of We also estimate the attack rate, the total proportion of cases (symptomatic and asymptomatic) with respect to the total population, for all Brazilian states since the beginning of the COVID-19 pandemic. We argue that the model present here is relevant to assessing present policies not only in Brazil but also in any place where good serological surveys are not available.

Impact of field heterogeneity on the dynamics of the forced Kuramoto model

We studied the impact of field heterogeneity on entrainment in a system of uniformly interacting phase oscillators. Field heterogeneity is shown to induce dynamical heterogeneity in the system. In effect, the heterogeneous field partitions the system into interacting groups of oscillators that feel the same local field strength and phase. Based on numerical and analytical analysis of the explicit dynamical equations derived from the periodically forced Kuramoto model, we found that the heterogeneous field can disrupt entrainment at different field frequencies when compared to the homogeneous field. This transition occurs when the phase- and frequency-locked synchronization between groups of oscillators is broken at a critical field frequency, causing each group to enter a new dynamical state (disrupted state). Strikingly, it is shown that disrupted dynamics can differ between groups.

Enhanced robustness of single-layer networks with redundant dependencies

Dependency links in single-layer networks offer a convenient way of modeling nonlocal percolation effects in networked systems where certain pairs of nodes are only able to function together. We study the percolation properties of the weak variant of this model: Nodes with dependency neighbors may continue to function if at least one of their dependency neighbors is active. We show that this relaxation of the dependency rule allows for more robust structures and a rich variety of critical phenomena, as percolation is not determined strictly by finite dependency clusters. We study Erdős-Rényi and random scale-free networks with an underlying Erdős-Rényi network of dependency links. We identify a special "cusp" point above which the system is always stable, irrespective of the density of dependency links. We find continuous and discontinuous hybrid percolation transitions, separated by a tricritical point for Erdős-Rényi networks. For scale-free networks with a finite degree cutoff we observe the appearance of a critical point and corresponding double transitions in a certain range of the degree distribution exponent. We show that at a special point in the parameter space, where the critical point emerges, the giant viable cluster has the unusual critical singularity S-S_{c}∝(p-p_{c})^{1/4}. We study the robustness of networks where connectivity degrees and dependency degrees are correlated and find that scale-free networks are able to retain their high resilience for strong enough positive correlation, i.e., when hubs are protected by greater redundancy.

Exotic critical behavior of weak multiplex percolation

We describe the critical behavior of weak multiplex percolation, a generalization of percolation to multiplex or interdependent networks. A node can determine its active or inactive status simply by referencing neighboring nodes. This is not the case for the more commonly studied generalization of percolation to multiplex networks, the mutually connected clusters, which requires an interconnecting path within each layer between any two vertices in the giant mutually connected component. We study the emergence of a giant connected component of active nodes under the weak percolation rule, finding several nontypical phenomena. In two layers, the giant component emerges with a continuous phase transition, but with quadratic growth above the critical threshold. In three or more layers, a discontinuous hybrid transition occurs, similar to that found in the giant mutually connected component. In networks with asymptotically powerlaw degree distributions, defined by the decay exponent γ, the discontinuity vanishes but at γ=1.5 in three layers, more generally at γ=1+1/(M-1) in M layers.

Filtering Statistics on Networks

Compression, filtering, and cryptography, as well as the sampling of complex systems, can be seen as processing information. A large initial configuration or input space is nontrivially mapped to a smaller set of output or final states. We explored the statistics of filtering of simple patterns on a number of deterministic and random graphs as a tractable example of such information processing in complex systems. In this problem, multiple inputs map to the same output, and the statistics of filtering is represented by the distribution of this degeneracy. For a few simple filter patterns on a ring, we obtained an exact solution of the problem and numerically described more difficult filter setups. For each of the filter patterns and networks, we found three key numbers that essentially describe the statistics of filtering and compared them for different networks. Our results for networks with diverse architectures are essentially determined by two factors: whether the graphs structure is deterministic or random and the vertex degree. We find that filtering in random graphs produces much richer statistics than in deterministic graphs, reflecting the greater complexity of such graphs. Increasing the graph's degree reduces this statistical richness, while being at its maximum at the smallest degree not equal to two. A filter pattern with a strong dependence on the neighbourhood of a node is much more sensitive to these effects.

Choosing among alternative histories of a tree

The structure of an evolving network contains information about its past. Extracting this information efficiently, however, is, in general, a difficult challenge. We formulate a fast and efficient method to estimate the most likely history of growing trees, based on exact results on root finding. We show that our linear-time algorithm produces the exact stepwise most probable history in a broad class of tree growth models. Our formulation is able to treat very large trees and therefore allows us to make reliable numerical observations regarding the possibility of root inference and history reconstruction in growing trees. We obtain the general formula 〈lnN〉≅NlnN-cN for the size dependence of the mean logarithmic number of possible histories of a given tree, a quantity that largely determines the reconstructability of tree histories. We also reveal an uncertainty principle: a relationship between the inferability of the root and that of the complete history, indicating that there is a tradeoff between the two tasks; the root and the complete history cannot both be inferred with high accuracy at the same time.

Finding the Optimal Nets for Self-Folding Kirigami

Three-dimensional shells can be synthesized from the spontaneous self-folding of two-dimensional templates of interconnected panels, called nets. However, some nets are more likely to self-fold into the desired shell under random movements. The optimal nets are the ones that maximize the number of vertex connections, i.e., vertices that have only two of its faces cut away from each other in the net. Previous methods for finding such nets are based on random search, and thus, they do not guarantee the optimal solution. Here, we propose a deterministic procedure. We map the connectivity of the shell into a shell graph, where the nodes and links of the graph represent the vertices and edges of the shell, respectively. Identifying the nets that maximize the number of vertex connections corresponds to finding the set of maximum leaf spanning trees of the shell graph. This method allows us not only to design the self-assembly of much larger shell structures but also to apply additional design criteria, as a complete catalog of the maximum leaf spanning trees is obtained.

Structural stability of interaction networks against negative external fields

We explore structural stability of weighted and unweighted networks of positively interacting agents against a negative external field. We study how the agents support the activity of each other to confront the negative field, which suppresses the activity of agents and can lead to collapse of the whole network. The competition between the interactions and the field shape the structure of stable states of the system. In unweighted networks (uniform interactions) the stable states have the structure of k-cores of the interaction network. The interplay between the topology and the distribution of weights (heterogeneous interactions) impacts strongly the structural stability against a negative field, especially in the case of fat-tailed distributions of weights. We show that apart from critical slowing down there is also a critical change in the system structure that precedes the network collapse. The change can serve as an early warning of the critical transition. To characterize changes of network structure we develop a method based on statistical analysis of the k-core organization and so-called "corona" clusters belonging to the k-cores.

Sensitivity of directed networks to the addition and pruning of edges and vertices

Directed networks have various topologically different extensive components, in contrast to a single giant component in undirected networks. We study the sensitivity (response) of the sizes of these extensive components in directed complex networks to the addition and pruning of edges and vertices. We introduce the susceptibility, which quantifies this sensitivity. We show that topologically different parts of a directed network have different sensitivity to the addition and pruning of edges and vertices and, therefore, they are characterized by different susceptibilities. These susceptibilities diverge at the critical point of the directed percolation transition, signaling the appearance (or disappearance) of the giant strongly connected component in the infinite size limit. We demonstrate this behavior in randomly damaged real and synthetic directed complex networks, such as the World Wide Web, Twitter, the Caenorhabditis elegans neural network, directed Erdős-Rényi graphs, and others. We reveal a nonmonotonic dependence of the sensitivity to random pruning of edges or vertices in the case of C. elegans and Twitter that manifests specific structural peculiarities of these networks. We propose the measurements of the susceptibilities during the addition or pruning of edges and vertices as a new method for studying structural peculiarities of directed networks.

Nonbacktracking expansion of finite graphs

Message passing equations yield a sharp percolation transition in finite graphs, as an artifact of the locally treelike approximation. For an arbitrary finite, connected, undirected graph we construct an infinite tree having the same local structural properties as this finite graph, when observed by a nonbacktracking walker. Formally excluding the boundary, this infinite tree is a generalization of the Bethe lattice. We indicate an infinite, locally treelike, random network whose local structure is exactly given by this infinite tree. Message passing equations for various cooperative models on this construction are the same as for the original finite graph, but here they provide the exact solutions of the corresponding cooperative problems. These solutions are good approximations to observables for the models on the original graph when it is sufficiently large and not strongly correlated. We show how to express these solutions in the critical region in terms of the principal eigenvector components of the nonbacktracking matrix. As representative examples we formulate the problems of the random and optimal destruction of a connected graph in terms of our construction, the nonbacktracking expansion. We analyze the limitations and the accuracy of the message passing algorithms for different classes of networks and compare the complexity of the message passing calculations to that of direct numerical simulations. Notably, in a range of important cases, simulations turn out to be more efficient computationally than the message passing.

Mapping the Structure of Directed Networks: Beyond the Bow-Tie Diagram

We reveal a hierarchical, multilayer organization of finite components-i.e., tendrils and tubes-around the giant connected components in directed networks and propose efficient algorithms allowing one to uncover the entire organization of key real-world directed networks, such as the World Wide Web, the neural network of Caenorhabditis elegans, and others. With increasing damage, the giant components decrease in size while the number and size of tendril layers increase, enhancing the susceptibility of the networks to damage.

Metastable localization of diseases in complex networks

We describe the phenomenon of localization in the epidemic susceptible-infective-susceptible model on highly heterogeneous networks in which strongly connected nodes (hubs) play the role of centers of localization. We find that in this model the localized states below the epidemic threshold are metastable. The longevity and scale of the metastable outbreaks do not show a sharp localization transition; instead there is a smooth crossover from localized to delocalized states as we approach the epidemic threshold from below. Analyzing these long-lasting local outbreaks for a random regular graph with a hub, we show how this localization can be detected from the shape of the distribution of the number of infective nodes.

Scale-free networks with exponent one

A majority of studied models for scale-free networks have degree distributions with exponents greater than two. Real networks, however, can demonstrate essentially more heavy-tailed degree distributions. We explore two models of scale-free equilibrium networks that have the degree distribution exponent γ=1, P(q)∼q^{-γ}. Such degree distributions can be identified in empirical data only if the mean degree of a network is sufficiently high. Our models exploit a rewiring mechanism. They are local in the sense that no knowledge of the network structure, apart from the immediate neighborhood of the vertices, is required. These models generate uncorrelated networks in the infinite size limit, where they are solved explicitly. We investigate finite size effects by the use of simulations. We find that both models exhibit disassortative degree-degree correlations for finite network sizes. In addition, we observe a markedly degree-dependent clustering in the finite networks. We indicate a real-world network with a similar degree distribution.

Synchronization in the random-field Kuramoto model on complex networks

We study the impact of random pinning fields on the emergence of synchrony in the Kuramoto model on complete graphs and uncorrelated random complex networks. We consider random fields with uniformly distributed directions and homogeneous and heterogeneous (Gaussian) field magnitude distribution. In our analysis, we apply the Ott-Antonsen method and the annealed-network approximation to find the critical behavior of the order parameter. In the case of homogeneous fields, we find a tricritical point above which a second-order phase transition gives place to a first-order phase transition when the network is either fully connected or scale-free with the degree exponent γ>5. Interestingly, for scale-free networks with 2<γ≤5, the phase transition is of second-order at any field magnitude, except for degree distributions with γ=3 when the transition is of infinite order at K_{c}=0 independent of the random fields. Contrary to the Ising model, even strong Gaussian random fields do not suppress the second-order phase transition in both complete graphs and scale-free networks, although the fields increase the critical coupling for γ>3. Our simulations support these analytical results.

Solution of the explosive percolation quest. II. Infinite-order transition produced by the initial distributions of clusters

We describe the effect of power-law initial distributions of clusters on ordinary percolation and its generalizations, specifically, models of explosive percolation processes based on local optimization. These aggregation processes were shown to exhibit continuous phase transitions if the evolution starts from a set of disconnected nodes. Since the critical exponents of the order parameter in explosive percolation transitions turned out to be very small, these transitions were first believed to be discontinuous. In this article we analyze the evolution starting from clusters of nodes whose sizes are distributed according to a power law. We show that these initial distributions change dramatically the position and order of the phase transitions in these problems. We find a particular initial power-law distribution producing a peculiar effect on explosive percolation, namely, before the emergence of the percolation cluster, the system is in a "critical phase" with an infinite generalized susceptibility. This critical phase is absent in ordinary percolation models with any power-law initial conditions. The transition from the critical phase is an infinite-order phase transition, which resembles the scenario of the Berezinskii-Kosterlitz-Thouless phase transition. We obtain the critical singularity of susceptibility at this peculiar infinite-order transition in explosive percolation. It turns out that susceptibility in this situation does not obey the Curie-Weiss law.

Inverting the Achlioptas rule for explosive percolation

In the usual Achlioptas processes the smallest clusters of a few randomly chosen ones are selected to merge together at each step. The resulting aggregation process leads to the delayed birth of a giant cluster and the so-called explosive percolation transition showing a set of anomalous features. We explore a process with the opposite selection rule, in which the biggest clusters of the randomly chosen ones merge together. We develop a theory of this kind of percolation based on the Smoluchowsky equation, find the percolation threshold, and describe the scaling properties of this continuous transition, namely, the critical exponents and amplitudes, and scaling functions. We show that, qualitatively, this transition is similar to the ordinary percolation one, though occurring in less connected systems.

Critical behavior of the relaxation rate, the susceptibility, and a pair correlation function in the Kuramoto model on scale-free networks

We study the impact of network heterogeneity on relaxation dynamics of the Kuramoto model on uncorrelated complex networks with scale-free degree distributions. Using the Ott-Antonsen method and the annealed-network approach, we find that the critical behavior of the relaxation rate near the synchronization phase transition does not depend on network heterogeneity and critical slowing down takes place at the critical point when the second moment of the degree distribution is finite. In the case of a complete graph we obtain an explicit result for the relaxation rate when the distribution of natural frequencies is Lorentzian. We also find a response of the Kuramoto model to an external field and show that the susceptibility of the model is inversely proportional to the relaxation rate. We reveal that network heterogeneity strongly impacts a field dependence of the relaxation rate and the susceptibility when the network has a divergent fourth moment of degree distribution. We introduce a pair correlation function of phase oscillators and show that it has a sharp peak at the critical point, signaling emergence of long-range correlations. Our numerical simulations of the Kuramoto model support our analytical results.

Giant components in directed multiplex networks

We describe the complex global structure of giant components in directed multiplex networks that generalizes the well-known bow-tie structure, generic for ordinary directed networks. By definition, a directed multiplex network contains vertices of one type and directed edges of m different types. In directed multiplex networks, we distinguish a set of different giant components based on the existence of directed paths of different types between their vertices such that for each type of edges, the paths run entirely through only edges of that type. If, in particular, m=2, we define a strongly viable component as a set of vertices in which for each type of edges each two vertices are interconnected by at least two directed paths in both directions, running through the edges of only this type. We show that in this case, a directed multiplex network contains in total nine different giant components including the strongly viable component. In general, the total number of giant components is 3^{m}. For uncorrelated directed multiplex networks, we obtain exactly the size and the emergence point of the strongly viable component and estimate the sizes of other giant components.

Noise-enhanced nonlinear response and the role of modular structure for signal detection in neuronal networks

We show that sensory noise can enhance the nonlinear response of neuronal networks, and when delivered together with a weak signal, it improves the signal detection by the network. We reveal this phenomenon in neuronal networks that are in a dynamical state preceding a saddle-node bifurcation corresponding to the appearance of sustained network oscillations. In this state, even a weak subthreshold pulse can evoke a large-amplitude oscillation of neuronal activity. The signal-to-noise ratio reaches a maximum at an optimum level of sensory noise, manifesting stochastic resonance (SR) at the population level. We demonstrate SR by use of simulations and numerical integration of rate equations in a cortical model. Using this model, we mimic the experiments of Gluckman et al. [Phys. Rev. Lett. 77, 4098 (1996)PRLTAO0031-900710.1103/PhysRevLett.77.4098] that have given evidence of SR in mammalian brain. We also study neuronal networks in which neurons are grouped in modules and every module works in the regime of SR. We find that even a few modules can strongly enhance the reliability of signal detection in comparison with the case when a modular organization is absent.

Solution of the explosive percolation quest: scaling functions and critical exponents

Percolation refers to the emergence of a giant connected cluster in a disordered system when the number of connections between nodes exceeds a critical value. The percolation phase transitions were believed to be continuous until recently when, in a new so-called "explosive percolation" problem for a competition-driven process, a discontinuous phase transition was reported. The analysis of evolution equations for this process showed, however, that this transition is actually continuous, though with surprisingly tiny critical exponents. For a wide class of representative models, we develop a strict scaling theory of this exotic transition which provides the full set of scaling functions and critical exponents. This theory indicates the relevant order parameter and susceptibility for the problem and explains the continuous nature of this transition and its unusual properties.

Critical exponents of the explosive percolation transition

In a new type of percolation phase transition, which was observed in a set of nonequilibrium models, each new connection between vertices is chosen from a number of possibilities by an Achlioptas-like algorithm. This causes preferential merging of small components and delays the emergence of the percolation cluster. First simulations led to a conclusion that a percolation cluster in this irreversible process is born discontinuously, by a discontinuous phase transition, which results in the term "explosive percolation transition." We have shown that this transition is actually continuous (second order) though with an anomalously small critical exponent of the percolation cluster. Here we propose an efficient numerical method enabling us to find the critical exponents and other characteristics of this second-order transition for a representative set of explosive percolation models with different number of choices. The method is based on gluing together the numerical solutions of evolution equations for the cluster size distribution and power-law asymptotics. For each of the models, with high precision, we obtain critical exponents and the critical point.

Biased imitation in coupled evolutionary games in interdependent networks

We explore the evolutionary dynamics of two games—the Prisoner's Dilemma and the Snowdrift Game—played within distinct networks (layers) of interdependent networks. In these networks imitation and interaction between individuals of opposite layers is established through interlinks. We explore an update rule in which revision of strategies is a biased imitation process: individuals imitate neighbors from the same layer with probability p, and neighbors from the second layer with complementary probability 1 − p. We demonstrate that a small decrease of p from p = 1 (which corresponds to forbidding strategy transfer between layers) is sufficient to promote cooperation in the Prisoner's Dilemma subpopulation. This, on the other hand, is detrimental for cooperation in the Snowdrift Game subpopulation. We provide results of extensive computer simulations for the case in which layers are modelled as regular random networks, and support this study with analytical results for coupled well-mixed populations.

Critical phenomena and noise-induced phase transitions in neuronal networks

We study numerically and analytically first- and second-order phase transitions in neuronal networks stimulated by shot noise (a flow of random spikes bombarding neurons). Using an exactly solvable cortical model of neuronal networks on classical random networks, we find critical phenomena accompanying the transitions and their dependence on the shot noise intensity. We show that a pattern of spontaneous neuronal activity near a critical point of a phase transition is a characteristic property that can be used to identify the bifurcation mechanism of the transition. We demonstrate that bursts and avalanches are precursors of a first-order phase transition, paroxysmal-like spikes of activity precede a second-order phase transition caused by a saddle-node bifurcation, while irregular spindle oscillations represent spontaneous activity near a second-order phase transition caused by a supercritical Hopf bifurcation. Our most interesting result is the observation of the paroxysmal-like spikes. We show that a paroxysmal-like spike is a single nonlinear event that appears instantly from a low background activity with a rapid onset, reaches a large amplitude, and ends up with an abrupt return to lower activity. These spikes are similar to single paroxysmal spikes and sharp waves observed in electroencephalographic (EEG) measurements. Our analysis shows that above the saddle-node bifurcation, sustained network oscillations appear with a large amplitude but a small frequency in contrast to network oscillations near the Hopf bifurcation that have a small amplitude but a large frequency. We discuss an amazing similarity between excitability of the cortical model stimulated by shot noise and excitability of the Morris-Lecar neuron stimulated by an applied current.

Avalanche collapse of interdependent networks

We reveal the nature of the avalanche collapse of the giant viable component in multiplex networks under perturbations such as random damage. Specifically, we identify latent critical clusters associated with the avalanches of random damage. Divergence of their mean size signals the approach to the hybrid phase transition from one side, while there are no critical precursors on the other side. We find that this discontinuous transition occurs in scale-free multiplex networks whenever the mean degree of at least one of the interdependent networks does not diverge.

Localization and spreading of diseases in complex networks

Using the susceptible-infected-susceptible model on unweighted and weighted networks, we consider the disease localization phenomenon. In contrast to the well-recognized point of view that diseases infect a finite fraction of vertices right above the epidemic threshold, we show that diseases can be localized on a finite number of vertices, where hubs and edges with large weights are centers of localization. Our results follow from the analysis of standard models of networks and empirical data for real-world networks.

Belief-propagation algorithm and the Ising model on networks with arbitrary distributions of motifs

We generalize the belief-propagation algorithm to sparse random networks with arbitrary distributions of motifs (triangles, loops, etc.). Each vertex in these networks belongs to a given set of motifs (generalization of the configuration model). These networks can be treated as sparse uncorrelated hypergraphs in which hyperedges represent motifs. Here a hypergraph is a generalization of a graph, where a hyperedge can connect any number of vertices. These uncorrelated hypergraphs are treelike (hypertrees), which crucially simplifies the problem and allows us to apply the belief-propagation algorithm to these loopy networks with arbitrary motifs. As natural examples, we consider motifs in the form of finite loops and cliques. We apply the belief-propagation algorithm to the ferromagnetic Ising model with pairwise interactions on the resulting random networks and obtain an exact solution of this model. We find an exact critical temperature of the ferromagnetic phase transition and demonstrate that with increasing the clustering coefficient and the loop size, the critical temperature increases compared to ordinary treelike complex networks. However, weak clustering does not change the critical behavior qualitatively. Our solution also gives the birth point of the giant connected component in these loopy networks.

Critical behavior and correlations on scale-free small-world networks: application to network design

We analyze critical phenomena on networks generated as the union of hidden variable models (networks with any desired degree sequence) with arbitrary graphs. The resulting networks are general small worlds similar to those à la Watts and Strogatz, but with a heterogeneous degree distribution. We prove that the critical behavior (thermal or percolative) remains completely unchanged by the presence of finite loops (or finite clustering). Then, we show that, in large but finite networks, correlations of two given spins may be strong, i.e., approximately power-law-like, at any temperature. Quite interestingly, if γ is the exponent for the power-law distribution of the vertex degree, for γ≤3 and with or without short-range couplings, such strong correlations persist even in the thermodynamic limit, contradicting the common opinion that, in mean-field models, correlations always disappear in this limit. Finally, we provide the optimal choice of rewiring under which percolation phenomena in the rewired network are best performed, a natural criterion to reach best communication features, at least in noncongested regimes.

Heterogeneous k-core versus bootstrap percolation on complex networks

We introduce the heterogeneous k-core, which generalizes the k-core, and contrast it with bootstrap percolation. Vertices have a threshold r(i), that may be different at each vertex. If a vertex has fewer than r(i) neighbors it is pruned from the network. The heterogeneous k-core is the subgraph remaining after no further vertices can be pruned. If the thresholds r(i) are 1 with probability f, or k ≥ 3 with probability 1-f, the process can be thought of as a pruning process counterpart to ordinary bootstrap percolation, which is an activation process. We show that there are two types of transitions in this heterogeneous k-core process: the giant heterogeneous k-core may appear with a continuous transition and there may be a second discontinuous hybrid transition. We compare critical phenomena, critical clusters, and avalanches at the heterogeneous k-core and bootstrap percolation transitions. We also show that the network structure has a crucial effect on these processes, with the giant heterogeneous k-core appearing immediately at a finite value for any f>0 when the degree distribution tends to a power law P(q)~q(-γ) with γ<3.

Explosive percolation transition is actually continuous

Recently a discontinuous percolation transition was reported in a new "explosive percolation" problem for irreversible systems [D. Achlioptas, R. M. D'Souza, and J. Spencer, Science 323, 1453 (2009)] in striking contrast to ordinary percolation. We consider a representative model which shows that the explosive percolation transition is actually a continuous, second order phase transition though with a uniquely small critical exponent of the percolation cluster size. We describe the unusual scaling properties of this transition and find its critical exponents and dimensions.

First- and second-order phase transitions in Ising models on small-world networks: simulations and comparison with an effective field theory

We perform simulations of random Ising models defined over small-world networks and we check the validity and the level of approximation of a recently proposed effective field theory. Simulations confirm a rich scenario with the presence of multicritical points with first- or second-order phase transitions. In particular, for second-order phase transitions, independent of the dimension d0 of the underlying lattice, the exact predictions of the theory in the paramagnetic regions, such as the location of critical surfaces and correlation functions, are verified. Quite interestingly, we verify that the Edwards-Anderson model with d0=2 is not thermodynamically stable under graph noise.

Bootstrap percolation on complex networks

We consider bootstrap percolation on uncorrelated complex networks. We obtain the phase diagram for this process with respect to two parameters: f, the fraction of vertices initially activated, and p, the fraction of undamaged vertices in the graph. We observe two transitions: the giant active component appears continuously at a first threshold. There may also be a second, discontinuous, hybrid transition at a higher threshold. Avalanches of activations increase in size as this second critical point is approached, finally diverging at this threshold. We describe the existence of a special critical point at which this second transition first appears. In networks with degree distributions whose second moment diverges (but whose first moment does not), we find a qualitatively different behavior. In this case the giant active component appears for any f>0 and p>0, and the discontinuous transition is absent. This means that the giant active component is robust to damage, and also is very easily activated. We also formulate a generalized bootstrap process in which each vertex can have an arbitrary threshold.

Stochastic cellular automata model of neural networks

We propose a stochastic dynamical model of noisy neural networks with complex architectures and discuss activation of neural networks by a stimulus, pacemakers, and spontaneous activity. This model has a complex phase diagram with self-organized active neural states, hybrid phase transitions, and a rich array of behaviors. We show that if spontaneous activity (noise) reaches a threshold level then global neural oscillations emerge. Stochastic resonance is a precursor of this dynamical phase transition. These oscillations are an intrinsic property of even small groups of 50 neurons.

Zero Pearson coefficient for strongly correlated growing trees

We obtained Pearson's coefficient of strongly correlated recursive networks growing by preferential attachment of every new vertex by m edges. We found that the Pearson coefficient is exactly zero in the infinite network limit for the recursive trees (m=1). If the number of connections of new vertices exceeds one (m>1), then the Pearson coefficient in the infinite networks equals zero only when the degree distribution exponent gamma does not exceed 4. We calculated the Pearson coefficient for finite networks and observed a slow power-law-like approach to an infinite network limit. Our findings indicate that Pearson's coefficient strongly depends on size and details of networks, which makes this characteristic virtually useless for quantitative comparison of different networks.

Communication and correlation among communities

Given a network and a partition in communities, we consider the issues "how communities influence each other" and "when two given communities do communicate." Specifically, we address these questions in the context of small-world networks, where an arbitrary quenched graph is given and long-range connections are randomly added. We prove that, among the communities, a superposition principle applies and gives rise to a natural generalization of the effective field theory already presented by M. Ostilli and J. F. F. Mendes [Phys. Rev. E 78, 031102 (2008)] (n=1), which here (n>1) consists in a sort of effective TAP (Thouless, Anderson, and Palmer) equations in which each community plays the role of a microscopic spin. The relative susceptibilities derived from these equations calculated at finite or zero temperature, where the method provides an effective percolation theory, give us the answers to the above issues. Unlike the case n=1, asymmetries among the communities may lead, via the TAP-like structure of the equations, to many metastable states whose number, in the case of negative shortcuts among the communities, may grow exponentially fast with n. As examples we consider the n Viana-Bray communities model and the n one-dimensional small-world communities model. Despite being the simplest ones, the relevance of these models in network theory, as, e.g., in social networks, is crucial and no analytic solution were known until now. Connections between percolation and the fractal dimension of a network are also discussed. Finally, as an inverse problem, we show how, from the relative susceptibilities, a natural and efficient method to detect the community structure of a generic network arises.

Organization of modular networks

We examine the global organization of heterogeneous equilibrium networks consisting of a number of well-distinguished interconnected parts-"communities" or modules. We develop an analytical approach allowing us to obtain the statistics of connected components and the intervertex distance distribution in these modular networks, and to describe their global organization and structure. In particular, we study the evolution of the intervertex distance distribution with an increasing number of interlinks connecting two infinitely large uncorrelated networks. We demonstrate that even a relatively small number of shortcuts unite the networks into one. In more precise terms, if the number of interlinks is any finite fraction of the total number of connections, then the intervertex distance distribution approaches a delta -function peaked form, and so the network is united.

Percolation on correlated networks

We reconsider the problem of percolation on an equilibrium random network with degree-degree correlations between nearest-neighboring vertices focusing on critical singularities at a percolation threshold. We obtain criteria for degree-degree correlations to be irrelevant for critical singularities. We present examples of networks in which assortative and disassortative mixing leads to unusual percolation properties and new critical exponents.

Simple reaction-diffusion population model on scale-free networks

We study a simple reaction-diffusion population model [proposed by A. Windus and H. J. Jensen, J. Phys. A: Math. Theor. 40, 2287 (2007)] on scale-free networks. In the case of fully random diffusion, the network topology cannot affect the critical death rate, whereas the heterogeneous connectivity can cause smaller steady population density and critical population density. In the case of modified diffusion, we obtain a larger critical death rate and steady population density, at the meanwhile, lower critical population density, which is good for the survival of species. The results were obtained using a mean-field-like framework and were confirmed by computer simulations.

Effective field theory for models defined over small-world networks: first- and second-order phase transitions

We present an effective field theory to analyze, in a very general way, models defined over small-world networks. Even if the exactness of the method is limited to the paramagnetic regions and to some special limits, it provides, yielding a clear and immediate (also in terms of calculation) physical insight, the exact critical behavior and the exact critical surfaces and percolation thresholds. The underlying structure of the nonrandom part of the model-i.e., the set of spins filling up a given lattice L0 of dimension d_{0} and interacting through a fixed coupling J0 -is exactly taken into account. When J_{0}> or = 0 , the small-world effect gives rise, as is known, to a second-order phase transition that takes place independently of the dimension d_{0} and of the added random connectivity c . When J0<0 , a different and novel scenario emerges in which, besides a spin-glass transition, multiple first- and second-order phase transitions may take place. As immediate analytical applications we analyze the Viana-Bray model (d_{0}=0) , the one-dimensional chain (d_{0}=1) , and the spherical model for arbitrary d_{0} .

Laplacian spectra of, and random walks on, complex networks: are scale-free architectures really important?

We study the Laplacian operator of an uncorrelated random network and, as an application, consider hopping processes (diffusion, random walks, signal propagation, etc.) on networks. We develop a strict approach to these problems. We derive an exact closed set of integral equations, which provide the averages of the Laplacian operator's resolvent. This enables us to describe the propagation of a signal and random walks on the network. We show that the determining parameter in this problem is the minimum degree q(m) of vertices in the network and that the high-degree part of the degree distribution is not that essential. The position of the lower edge of the Laplacian spectrum lambda(c) appears to be the same as in the regular Bethe lattice with the coordination number q(m). Namely, lambda(c)>0 if q(m)>2 , and lambda(c)=0 if q(m)< or =2 . In both of these cases the density of eigenvalues rho(lambda)-->0 as lambda-->lambda(c)+0 , but the limiting behaviors near lambda(c) are very different. In terms of a distance from a starting vertex, the hopping propagator is a steady moving Gaussian, broadening with time. This picture qualitatively coincides with that for a regular Bethe lattice. Our analytical results include the spectral density rho(lambda) near lambda(c) and the long-time asymptotics of the autocorrelator and the propagator.

Impacts of preference and geography on epidemic spreading

We investigate the standard susceptible-infected-susceptible model on a random network to study the effects of preference and geography on diseases spreading. The network grows by introducing one random node with m links on a Euclidean space at unit time. The probability of a new node i linking to a node j with degree k(j) at distance d(ij) from node i is proportional to k(j)(A)/d(ij)(B), where A and B are positive constants governing preferential attachment and the cost of the node-node distance. In the case of A=0 , we recover the usual epidemic behavior with a critical threshold below which diseases eventually die out. Whereas for B=0 , the critical behavior is absent only in the condition A=1. While both ingredients are proposed simultaneously, the network becomes robust to infection for larger A and smaller B.

Berezinskii-Kosterlitz-Thouless-like transition in the Potts model on an inhomogeneous annealed network

We solve the ferromagnetic q-state Potts model on an inhomogeneous annealed network which mimics a random recursive graph. We find that this system has the inverted Berezinskii-Kosterlitz-Thouless (BKT) phase transition for any q > or =1 , including the values q > or =3 , where the Potts model normally shows a first order phase transition. We obtain the temperature dependences of the order parameter, specific heat, and susceptibility demonstrating features typical for the BKT transition. We show that in the entire normal phase, both the distribution of a linear response to an applied local field and the distribution of spin-spin correlations have a critical, i.e., power-law form.

Degree-dependent intervertex separation in complex networks

We study the mean length (l)(k) of the shortest paths between a vertex of degree k and other vertices in growing networks, where correlations are essential. In a number of deterministic scale-free networks we observe a power-law correction to a logarithmic dependence, (l)(k) = A ln[N/k((gamma-1)/2)]-Ck(gamma-1)/N+ in a wide range of network sizes. Here N is the number of vertices in the network, gamma is the degree distribution exponent, and the coefficients A and C depend on a network. We compare this law with a corresponding (l)(k) dependence obtained for random scale-free networks growing through the preferential attachment mechanism. In stochastic and deterministic growing trees with an exponential degree distribution, we observe a linear dependence on degree, (l)(k)approximately A ln N-Ck. We compare our findings for growing networks with those for uncorrelated graphs.

k-core (bootstrap) percolation on complex networks: critical phenomena and nonlocal effects

We develop the theory of the -core (bootstrap) percolation on uncorrelated random networks with arbitrary degree distributions. We show that the -core percolation is an unusual, hybrid phase transition with a jump emergence of the k-core as at a first order phase transition but also with a critical singularity as at a continuous transition. We describe the properties of the -core, explain the meaning of the order parameter for the k-core percolation, and reveal the origin of the specific critical phenomena. We demonstrate that a so-called "corona" of the k-core plays a crucial role (corona is a subset of vertices in the k-core which have exactly neighbors in the -core). It turns out that the k-core percolation threshold is at the same time the percolation threshold of finite corona clusters. The mean separation of vertices in corona clusters plays the role of the correlation length and diverges at the critical point. We show that a random removal of even one vertex from the k-core may result in the collapse of a vast region of the k-core around the removed vertex. The mean size of this region diverges at the critical point. We find an exact mapping of the k-core percolation to a model of cooperative relaxation. This model undergoes critical relaxation with a divergent rate at some critical moment.

k-Core organization of complex networks

We analytically describe the architecture of randomly damaged uncorrelated networks as a set of successively enclosed substructures--k-cores. The k-core is the largest subgraph where vertices have at least k interconnections. We find the structure of k-cores, their sizes, and their birthpoints--the bootstrap percolation thresholds. We show that in networks with a finite mean number zeta2 of the second-nearest neighbors, the emergence of a k-core is a hybrid phase transition. In contrast, if zeta2 diverges, the networks contain an infinite sequence of k-cores which are ultrarobust against random damage.

Correlations in interacting systems with a network topology

We study pair correlations in interacting systems placed on complex networks. We show that usually in these systems, pair correlations between interacting objects (e.g., spins), separated by a distance l, decay, on average, faster than 1/(lzl). Here zl is the mean number of the lth nearest neighbors of a vertex in a network. This behavior, in particular, leads to a dramatic weakening of correlations between second and more distant neighbors on networks with fat-tailed degree distributions, which have a divergent number z2 in the infinite network limit. In large networks of this kind, only pair correlations between the nearest neighbors are actually observable. We find the pair correlation function of the Ising model on a complex network. This exact result is confirmed by a phenomenological approach.

Organization of complex networks without multiple connections

We find a new structural feature of equilibrium complex random networks without multiple and self-connections. We show that if the number of connections is sufficiently high, these networks contain a core of highly interconnected vertices. The number of vertices in this core varies in the range between const x N1/2 and const x N2/3, where is the number of vertices in a network. At the birth point of the core, we obtain the size-dependent cutoff of the distribution of the number of connections and find that its position differs from earlier estimates.

Scale-free network with Boolean dynamics as a function of connectivity

In this work we analyze scale-free networks with different power-law spectra N (k) approximately k(-gamma) under a Boolean dynamic, where the Boolean rule that each node obeys is a function of its connectivity k. This is done by using only two logical functions (AND and XOR) which are controlled by a parameter q. Using a damage spreading technique we show that the Hamming distance and the number of 1's exhibit power-law behavior as a function of q. The exponents appearing in the power laws depend on the value of gamma.