Search

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 a 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 critical slowing down there is also a critical change in the system structure that precedes the network collapse. The change can serve as early warning of the critical transition. In order 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., Comment: 11 pages, 9 figures

We study the sensitivity of directed complex networks to the addition and pruning of edges and vertices and 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 \emph{Caenorhabditis elegans} neural network, directed Erd\H{o}s-R\'enyi graphs, and others. We reveal a non-monotonous dependence of the sensitivity to random pruning of edges or vertices in the case of \emph{Caenorhabditis 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., Comment: 15 pages

Many real complex systems cannot be represented by a single network, but due to multiple sub-systems and types of interactions, must be represented as a multiplex network. This is a set of nodes which exist in several layers, with each layer having its own kind of edges, represented by different colours. An important fundamental structural feature of networks is their resilience to damage, the percolation transition. Generalisation of these concepts to multiplex networks requires careful definition of what we mean by connected clusters. We consider two different definitions. One, a rigorous generalisation of the single-layer definition leads to a strong non-local rule, and results in a dramatic change in the response of the system to damage. The giant component collapses discontinuously in a hybrid transition characterised by avalanches of diverging mean size. We also consider another definition, which imposes weaker conditions on percolation and allows local calculation, and also leads to different sized giant components depending on whether we consider an activation or pruning process. This 'weak' process exhibits both continuous and discontinuous transitions., Comment: arXiv admin note: text overlap with arXiv:1312.3814

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 \emph{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., Comment: 5 pages, 4 figures

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 $\gamma>5$. Interestingly, for scale-free networks with $2<\gamma \leq 5$, the phase transition is of second-order at any field magnitude, except for degree distributions with $\gamma=3$ when the transition is of infinite order at $K_c=0$ independently on the random fields. Contrarily 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 though the fields increase the critical coupling for $\gamma > 3$. Our simulations support these analytical results., Comment: 7 pages, 2 figures

We present the theory of the k-core pruning process (progressive removal of nodes with degree less than k) in uncorrelated random networks. We derive exact equations describing this process and the evolution of the network structure, and solve them numerically and, in the critical regime of the process, analytically. We show that the pruning process exhibits three different behaviors depending on whether the mean degree of the initial network is above, equal to, or below the threshold _c corresponding to the emergence of the giant k-core. We find that above the threshold the network relaxes exponentially to the k-core. The system manifests the phenomenon known as "critical slowing down", as the relaxation time diverges when tends to _c. At the threshold, the dynamics become critical characterized by a power-law relaxation (1/t^2). Below the threshold, a long-lasting transient process (a "plateau" stage) occurs. This transient process ends with a collapse in which the entire network disappears completely. The duration of the process diverges when tends to _c. We show that the critical dynamics of the pruning are determined by branching processes of spreading damage. Clusters of nodes of degree exactly k are the evolving substrate for these branching processes. Our theory completely describes this branching cascade of damage in uncorrelated networks by providing the time dependent distribution function of branching. These theoretical results are supported by our simulations of the $k$-core pruning in Erdos-Renyi graphs., Comment: 12 pages, 10 figures

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 Smoluchowski 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., Comment: 6 pages, 2 figures

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 the susceptibility in this situation does not obey the Curie-Weiss law., Comment: 17 pages, 5 figures

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., Comment: 10 pages, 4 figures

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., Comment: 15 pages, 5 figures

In a new type of percolation phase transition, which was observed in a set of non-equilibrium 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., Comment: 7 pages, 4 figures

Using an exactly solvable cortical model of a neuronal network, we show that, by increasing the intensity of shot noise (flow of random spikes bombarding neurons), the network undergoes first- and second-order non-equilibrium phase transitions. We study the nature of the transitions, bursts and avalanches of neuronal activity. Saddle-node and supercritical Hopf bifurcations are the mechanisms of emergence of sustained network oscillations. We show that the network stimulated by shot noise behaves similar to the Morris-Lecar model of a biological neuron stimulated by an applied current.

We study the role of scale-free structure and noise in collective dynamics of neuronal networks. For this purpose, we simulate and study analytically a cortical circuit model with stochastic neurons. We compare collective neuronal activity of networks with different topologies: classical random graphs and scale-free networks. We show that, in scale-free networks with divergent second moment of degree distribution, an influence of noise on neuronal activity is strongly enhanced in comparison with networks with a finite second moment. A very small noise level can stimulate spontaneous activity of a finite fraction of neurons and sustained network oscillations. We demonstrate tolerance of collective dynamics of the scale-free networks to random damage in a broad range of the number of randomly removed excitatory and inhibitory neurons. A random removal of neurons leads to gradual decrease of frequency of network oscillations similar to the slowing-down of the alpha rhythm in Alzheimer's disease. However, the networks are vulnerable to targeted attacks. A removal of a few excitatory or inhibitory hubs can impair sustained network oscillations., Comment: 12 pages, 10 figures

Understanding of short-term synaptic depression (STSD) and other forms of synaptic plasticity is a topical problem in neuroscience. Here we study the role of STSD in the formation of complex patterns of brain rhythms. We use a cortical circuit model of neural networks composed of irregular spiking excitatory and inhibitory neurons having type 1 and 2 excitability and stochastic dynamics. In the model, neurons form a sparsely connected network and their spontaneous activity is driven by random spikes representing synaptic noise. Using simulations and analytical calculations, we found that if the STSD is absent, the neural network shows either asynchronous behavior or regular network oscillations depending on the noise level. In networks with STSD, changing parameters of synaptic plasticity and the noise level, we observed transitions to complex patters of collective activity: mixed-mode and spindle oscillations, bursts of collective activity, and chaotic behaviour. Interestingly, these patterns are stable in a certain range of the parameters and separated by critical boundaries. Thus, the parameters of synaptic plasticity can play a role of control parameters or switchers between different network states. However, changes of the parameters caused by a disease may lead to dramatic impairment of ongoing neural activity. We analyze the chaotic neural activity by use of the 0-1 test for chaos (Gottwald, G. & Melbourne, I., 2004) and show that it has a collective nature., Comment: 7 pages, Proceedings of 12th Granada Seminar, September 17-21, 2012

Brain rhythms contribute to every aspect of brain function. Here, we study critical and resonance phenomena that precede the emergence of brain rhythms. Using an analytical approach and simulations of a cortical circuit model of neural networks with stochastic neurons in the presence of noise, we show that spontaneous appearance of network oscillations occurs as a dynamical (non-equilibrium) phase transition at a critical point determined by the noise level, network structure, the balance between excitatory and inhibitory neurons, and other parameters. We find that the relaxation time of neural activity to a steady state, response to periodic stimuli at the frequency of the oscillations, amplitude of damped oscillations, and stochastic fluctuations of neural activity are dramatically increased when approaching the critical point of the transition., Comment: 8 pages, Proceedings of 12th Granada Seminar, September 17-21, 2012

We study the Kuramoto model on complex networks, in which natural frequencies of phase oscillators and the vertex degrees are correlated. Using the annealed network approximation and numerical simulations we explore a special case in which the natural frequencies of the oscillators and the vertex degrees are linearly coupled. We find that in uncorrelated scale-free networks with the degree distribution exponent $2 < \gamma < 3$, the model undergoes a first-order phase transition, while the transition becomes of the second order at $\gamma>3$. If $\gamma=3$, the phase synchronization emerges as a result of a hybrid phase transition that combines an abrupt emergence of synchronization, as in first-order phase transitions, and a critical singularity, as in second-order phase transitions. The critical fluctuations manifest themselves as avalanches in synchronization process. Comparing our analytical calculations with numerical simulations for Erd\H{o}s--R\'{e}nyi and scale-free networks, we demonstrate that the annealed network approach is accurate if the the mean degree and size of the network are sufficiently large. We also study analytically and numerically the Kuramoto model on star graphs and find that if the natural frequency of the central oscillator is sufficiently large in comparison to the average frequency of its neighbors, then synchronization emerges as a result of a first-order phase transition. This shows that oscillators sitting at hubs in a network may generate a discontinuous synchronization transition., Comment: 11 pages

Using the SIS 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., Comment: 5 pages, 3 figures

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 tree-like (hypertrees), which crucially simplify the problem and allow 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 on the resulting random networks. We obtain an exact solution of this model on networks with finite loops or cliques as motifs. 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 tree-like complex networks. Our solution also gives the birth point of the giant connected component in these loopy networks., Comment: 9 pages, 4 figures

The basic notion of percolation in physics assumes the emergence of a giant connected (percolation) cluster in a large disordered system when the density of connections exceeds some critical value. Until recently, the percolation phase transitions were believed to be continuous, however, in 2009, a remarkably different, discontinuous phase transition was reported in a new so-called "explosive percolation" problem. Each link in this problem is established by a specific optimization process. Here, employing strict analytical arguments and numerical calculations, we find that in fact the "explosive percolation" transition is continuous though with an uniquely small critical exponent of the percolation cluster size. These transitions provide a new class of critical phenomena in irreversible systems and processes., Comment: 22 pages, 4 figures, 1 table

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 behavior. 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., Comment: 10 pages, 5 figures