Thomas

We address here the problem of generating random graphs uniformly from the set of simple connected graphs having a prescribed degree sequence. Our goal is to provide an algorithm designed for practical use both because of its ability to generate very large graphs (efficiency) and because it is easy to implement (simplicity). We focus on a family of heuristics for which we introduce optimality conditions, and show how this optimality can be reached in practice. We then propose a different approach, specifically designed for real-world degree distributions, which outperforms the first one. Based on a conjecture which we argue rigorously and which was confirmed by strong empirical evidence, we finally reduce the best asymptotic complexity bound known so far.

Author(s): Wesley F. C. Cota, Silvio C. Ferreira, and Géza Ódor

We provide numerical evidence for slow dynamics of the susceptible-infected-susceptible model evolving on finite-size random networks with power-law degree distributions. Extensive simulations were done by averaging the activity density over many realizations of networks. We investigated the effects…

[Phys. Rev. E] Published Wed Feb 24, 2016

Author(s): Vivek Kohar, Behnam Kia, John F. Lindner, and William L. Ditto

We illustrate through theory and numerical simulations that redundant coupled dynamical systems can be extremely robust against local noise in comparison to uncoupled dynamical systems evolving in the same noisy environment. Previous studies have shown that the noise robustness of redundant coupled …

[Phys. Rev. E] Published Thu Feb 25, 2016

Author(s): Dirk Witthaut, Martin Rohden, Xiaozhu Zhang, Sarah Hallerberg, and Marc Timme

Link failures repeatedly induce large-scale outages in power grids and other supply networks. Yet, it is still not well understood, which links are particularly prone to inducing such outages. Here we analyze how the nature and location of each link impact the network's capability to maintain stable…

[Phys. Rev. Lett.] Published Tue Feb 23, 2016

Author(s): Iryna Omelchenko, Oleh E. Omel’chenko, Anna Zakharova, Matthias Wolfrum, and Eckehard Schöll

We propose a control scheme which can stabilize and fix the position of chimera states in small networks. Chimeras consist of coexisting domains of spatially coherent and incoherent dynamics in systems of nonlocally coupled identical oscillators. Chimera states are generally difficult to observe in …

[Phys. Rev. Lett.] Published Wed Feb 24, 2016

The Traveling Salesperson problem asks for the shortest cyclic tour visiting a set of cities given their pairwise distances and belongs to the NP-hard complexity class, which means that with all known algorithms in the worst case instances are not solvable in polynomial time, i.e. , the problem is hard . However, this does not mean that there are not subsets of the problem which are easy to solve. To examine numerically transitions from an easy to a hard phase, a random ensemble of cities in the Euclidean plane, given a parameter σ , which governs the hardness, is introduced. Here, a linear programming approach together with suitable cutting planes is applied. Such algorithms operate outside the space of feasible solutions and are often used in practical applications but rarely studied in physics so far. We observe several transitions. To characterize these transitions, scaling assumptions from continuous phase transitions are applie...

We derive a concise and general expression of the energy dissipation rate for coupled oscillators rotating on circular trajectories by unifying the nonequilibrium aspects with the nonlinear dynamics via stochastic thermodynamics. In the framework of phase oscillator models, it is known that the even and odd parts of the coupling function express the effect on collective and relative dynamics, respectively. We reveal that the odd part always decreases the dissipation upon synchronization, while the even part yields a characteristic square-root change of the dissipation near the bifurcation point whose sign depends on the specific system parameters. We apply our theory to hydrodynamically coupled Stokes spheres rotating on circular trajectories that can be interpreted as a simple model of synchronization of coupled oscillators in a biophysical system. We show that the coupled Stokes spheres gain the ability to do more work on the surrounding fluid as the degree of phase synchronization increases.

We study temporal networks of characters in literature focusing on "Alice's Adventures in Wonderland" (1865) by Lewis Carroll and the anonymous "La Chanson de Roland" (around 1100). The former, one of the most influential pieces of nonsense literature ever written, describes the adventures of Alice in a fantasy world with logic plays interspersed along the narrative. The latter, a song of heroic deeds, depicts the Battle of Roncevaux in 778 A.D. during Charlemagne's campaign on the Iberian Peninsula. We apply methods recently developed by Taylor and coworkers \cite{Taylor+2015} to find time-averaged eigenvector centralities, Freeman indices and vitalities of characters. We show that temporal networks are more appropriate than static ones for studying stories, as they capture features that the time-independent approaches fail to yield.

Donate to arXiv

Theoretical attempts proposed so far to describe ordinary percolation processes on real-world networks rely on the locally tree-like ansatz. Such an approximation, however, holds only to a limited extent, as real graphs are often characterized by high frequencies of short loops. We present here a theoretical framework able to overcome such a limitation for the case of site percolation. Our method is based on a message passing algorithm that discounts redundant paths along triangles in the graph. We systematically test the approach on 98 real-world graphs and on synthetic networks. We find excellent accuracy in the prediction of the whole percolation diagram, with significant improvement with respect to the prediction obtained under the locally tree-like approximation. Residual discrepancies between theory and simulations do not depend on clustering and can be attributed to the presence of loops longer than three edges. We present also a method to account for clustering in bond percolation, but the improvement with respect to the method based on the tree-like approximation is much less apparent.

Donate to arXiv

Author(s): Peter Talkner and Peter Hänggi

Various approaches of defining and determining work performed on a quantum system are compared. Any operational definition of work, however, must allow for two facts: first, that work characterizes a process rather than an instantaneous state of a system and, second, that quantum systems are sensiti…

[Phys. Rev. E 93, 022131] Published Tue Feb 23, 2016

Author(s): Ekkehard Ullner and Antonio Politi

Complex ensembles of multiple components are found in many biological systems, such as brains. Researchers model a population of oscillators acting like firing neurons to study the onset of irregular collective dynamics.

[Phys. Rev. X 6, 011015] Published Fri Feb 19, 2016

Problem solving ( e.g. , drug design, traffic engineering, software development) by task forces represents a substantial portion of the economy of developed countries. Here we use an agent-based model of cooperative problem-solving systems to study the influence of diversity on the performance of a task force. We assume that agents cooperate by exchanging information on their partial success and use that information to imitate the more successful agent in the system —the model. The agents differ only in their propensities to copy the model. We find that, for easy tasks, the optimal organization is a homogeneous system composed of agents with the highest possible copy propensities. For difficult tasks, we find that diversity can prevent the system from being trapped in sub-optimal solutions. However, when the system size is adjusted to maximize the performance the homogeneous systems outperform the heterogeneous systems, i.e. , for optimal performance, sameness should ...

We study optimal synchronization of networks of coupled phase oscillators. We extend previous theory for optimizing the synchronization properties of undirected networks to the important case of directed networks. We derive a generalized synchrony alignment function that encodes the interplay between network structure and the oscillators' natural frequencies and serves as an objective measure for the network's degree of synchronization. Using the generalized synchrony alignment function, we show that a network's synchronization properties can be systematically optimized. This framework also allows us to study the properties of synchrony-optimized networks, and in particular, investigate the role of directed network properties such as nodal in- and out-degrees. For instance, we find that in optimally rewired networks the heterogeneity of the in-degree distribution roughly matches the heterogeneity of the natural frequency distribution, but no such relationship emerges for out-degrees. We also observe that a network's synchronization properties are promoted by a strong correlation between the nodal in-degrees and the natural frequencies of oscillators, whereas the relationship between the nodal out-degrees and the natural frequencies has comparatively little effect. This result is supported by our theory, which indicates that synchronization is promoted by a strong alignment of the natural frequencies with the left singular vectors corresponding to the largest singular values of the Laplacian matrix.

Attractors of dynamical systems may be networks in phase space that can be heteroclinic (where there are dynamical connections between simple invariant sets) or excitable (where a perturbation threshold needs to be crossed to a dynamical connection between "nodes"). Such network attractors can display a high degree of sensitivity to noise both in terms of the regions of phase space visited and in terms of the sequence of transitions around the network. The two types of network are intimately related---one can directly bifurcate to the other.

In this paper we attempt to quantify the effect of additive noise on such network attractors. Noise increases the average rate at which the networks are explored, and can result in "macroscopic" random motion around the network. We perform an asymptotic analysis of local behaviour of an escape model near heteroclinic/excitable nodes in the limit of noise $\eta\rightarrow 0^+$ as a model for the mean residence time $T$ near equilibria.

We also explore transition probabilities between nodes of the network in the presence of anisotropic noise. For low levels of noise, numerical results suggest that a (heteroclinic or excitable) network can approximately realise any set of transition probabilities and any sufficiently large mean residence times at the given nodes. We show that this can be well modelled in our example network by multiple independent escape processes, where the direction of first escape determines the transition. This suggests that it is feasible to design noisy network attractors with arbitrary Markov transition probabilities and residence times.

Donate to arXiv

Author(s): Kevin P. O’Keeffe

We consider the transient behavior of globally coupled systems of identical pulse coupled oscillators. Synchrony develops through an aggregation phenomenon, with clusters of synchronized oscillators forming and growing larger in time. Previous work derived expressions for these time dependent cluste…

[Phys. Rev. E] Published Wed Feb 17, 2016

Author(s): Soumen K. Patra and Anandamohan Ghosh

Characterization of spatiotemporal dynamics of coupled oscillatory systems can be done by computing the Lyapunov exponents. We study the spatiotemporal dynamics of randomly coupled network of Kuramoto oscillators and find that the spectral statistics obtained from the Lyapunov exponent spectrum show…

[Phys. Rev. E] Published Wed Feb 17, 2016

Author(s): Ginestra Bianconi and Christoph Rahmede

Network geometry is attracting increasing attention because it has a wide range of applications, ranging from data mining to routing protocols in the Internet. At the same time advances in the understanding of the geometrical properties of networks are essential for further progress in quantum gravi…

[Phys. Rev. E] Published Thu Feb 18, 2016

Chimera states—curious symmetry-broken states in systems of identical coupled oscillators—typically occur only for certain initial conditions. Here we analyze their basins of attraction in a simple system comprised of two populations. Using perturbative analysis and numerical simulation we evaluate asymptotic states and associated destination maps, and demonstrate that basins form a complex twisting structure in phase space. Understanding the basins’ precise nature may help in the development of control methods to switch between chimera patterns, with possible technological and neural system applications.

Explosive synchronization (ES) has recently received increasing attention and studies have mainly focused on the conditions of its onset so far. However, its inverse problem, i.e. the suppression of ES, has not been systematically studied so far. As ES is usually considered to be harmful in certain circumstances such as the cascading failure of power grids and epileptic seizure, etc., its suppression is definitely important and deserves to be studied. We here study this inverse problem by presenting an efficient approach to suppress ES from a first-order to second-order transition, without changing the intrinsic network structure. We find that ES can be suppressed by only changing a small fraction of oscillators into contrarians with negative couplings and the critical fraction for the transition from the first order to the second order increases with both the network size and the average degree. A brief theory is presented to explain the underlying mechanism. This findin...

The degree-degree correlation is important in understanding the structural organization of a network and the dynamics upon a network. Such correlation is usually measured by the assortativity coefficient $r$, with natural bounds $r \in [-1,1]$. For scale-free networks with power-law degree distribution $p(k) \sim k^{-\gamma}$, we analytically obtain the lower bound of assortativity coefficient in the limit of large network size, which is not -1 but dependent on the power-law exponent $\gamma$. This work challenges the validation of assortativity coefficient in heterogeneous networks, suggesting that one cannot judge whether a network is positively or negatively correlated just by looking at its assortativity coefficient.

Donate to arXiv

Author(s): Michael A. Zaks and Petar Tomov

We consider the effect of global repulsive coupling on an ensemble of identical excitable elements. An increase of the coupling strength destabilizes the synchronous equilibrium and replaces it with many attracting oscillatory states, created in the transcritical heteroclinic bifurcation. The period…

[Phys. Rev. E 93, 020201(R)] Published Wed Feb 10, 2016

We develop the theory of sparse multiplex networks with partially overlapping links based on their local tree-likeness. This theory enables us to find the giant mutually connected component in a two-layer multiplex network with arbitrary correlations between connections of different types. We find that correlations between the overlapping and non-overlapping links markedly change the phase diagram of the system, leading to multiple hybrid phase transitions. For assortative correlations we observe recurrent hybrid phase transitions.

Understanding how person-to-person contagious processes spread through a population requires accurate information on connections between population members. However, such connectivity data, when collected via interview, is often incomplete due to partial recall, respondent fatigue or study design, e.g., fixed choice designs (FCD) truncate out-degree by limiting the number of contacts each respondent can report. Past research has shown how FCD truncation affects network properties, but its implications for predicted speed and size of spreading processes remain largely unexplored. To study the impact of degree truncation on spreading processes, we generated collections of synthetic networks containing specific properties (degree distribution, degree-assortativity, clustering), and also used empirical social network data from 75 villages in Karnataka, India. We simulated FCD using various truncation thresholds and ran a susceptible-infectious-recovered (SIR) process on each network. We found that spreading processes propagated on truncated networks resulted in slower and smaller epidemics, with a sudden decrease in prediction accuracy at a level of truncation that varied by network type. Our results have implications beyond FCD to truncation due to any limited sampling from a larger network. We conclude that knowledge of network structure is important for understanding the accuracy of predictions of process spread on degree truncated networks.

Donate to arXiv

Given a power grid and a transmission (coupling) strength, basin stability is a measure of synchronization stability for individual nodes. Earlier studies have focused on the basin stability's dependence of the position of the nodes in the network for single values of transmission strength. Basin stability grows from zero to one as transmission strength increases, but often in a complex, nonmonotonous way. In this study, we investigate the entire functional form of the basin stability's dependence on transmission strength. To be able to perform a systematic analysis, we restrict ourselves to small networks. We scan all isomorphically distinct networks with an equal number of power producers and consumers of six nodes or less. We find that the shapes of the basin stability fall into a few, rather well-defined classes, that could be characterized by the number of edges and the betweenness of the nodes, whereas other network positional quantities matter less.

DONATE to arXiv: One hundred percent of your contribution will fund improvements and new initiatives to benefit arXiv's global scientific community. Please join the Simons Foundation and our generous member organizations and research labs in supporting arXiv. https://goo.gl/QIgRpr

Increasing evidence shows that real-world systems interact with one another via dependency connectivities. Failing connectivities are the mechanism behind the breakdown of interacting complex systems, e.g., blackouts caused by the interdependence of power grids and communication networks. Previous research analyzing the robustness of interdependent networks has been limited to undirected...

As has been shown by Watanabe and Strogatz (WS) [Phys. Rev. Lett., 70, 2391 (1993)], a population of identical phase oscillators, sine-coupled to a common field, is a partially integrable system for any size: its dynamics reduces to equations for several collective variables. Here we develop a perturbation approach for weakly nonidentical ensembles. We calculate corrections to the WS dynamics for two types of perturbations: due to a distribution of natural frequencies and of forcing terms, and due to small white noise. We demonstrate, that in both cases the complex mean field for which the dynamical equations are written, is close up to the leading order in the perturbation to the Kuramoto order parameter. This supports validity of the dynamical reduction suggested by Ott and Antonsen [Chaos, 18, 037113 (2008)] for weakly inhomogeneous populations.

Donate to arXiv

Author(s): Michael A. Zaks and Petar Tomov

We consider effect of global repulsive coupling on an ensemble of identical excitable elements. Increase of the coupling strength destabilizes the synchronous equilibrium and replaces it by many attracting oscillatory states, born from the transcritical heteroclinic bifurcation. The period of oscill…

[Phys. Rev. E] Published Mon Jan 25, 2016