Thomas

In previous work, we developed the scaled SIS process, which models the dynamics of SIS epidemics over networks. We derived for the scaled SIS process a closed-form expression for the time-asymptotic probability distribution of the configurations of all the agents in the network, which explicitly exhibits the underlying network topology through its adjacency matrix. This is accomplished for networks that are of finite-size and of arbitrary topology. This paper determines which network configuration is the most probable. We prove that, for a range of epidemic parameters, this combinatorial inference problem leads to a submodular optimization problem, which can be solved in polynomial time. We relate the most-probable configuration to the network structure, and in particular to the existence of high-density subgraphs. Depending on the model parameters, subset of agents may be more likely to be infected than others; these more vulnerable agents form subgraphs that are denser than the overall network. We illustrate our results with a 193 node social network of drug users and with the 4941 node Western US power grid under different model parameters.

Author(s): José A. Capitán and Susanna Manrubia

The distribution of human linguistic groups presents a number of interesting and nontrivial patterns. The distributions of the number of speakers per language and the area each group covers follow log-normal distributions, while population and area fulfill an allometric relationship. The topology of…

[Phys. Rev. E 92, 062811] Published Wed Dec 09, 2015

Author(s): Laurent Hébert-Dufresne, Edward Laurence, Antoine Allard, Jean-Gabriel Young, and Louis J. Dubé

Real complex systems are not rigidly structured; no clear rules or blueprints exist for their construction. Yet, amidst their apparent randomness, complex structural properties universally emerge. We propose that an important class of complex systems can be modeled as an organization of many embedde…

[Phys. Rev. E 92, 062809] Published Wed Dec 09, 2015

Author(s): Young-Ho Eom, Andrea Perna, Santo Fortunato, Eric Darrouzet, Guy Theraulaz, and Christian Jost

A new model shows how complex termite nests can be built using only local interactions between the insects.

[Phys. Rev. E 92, 062810] Published Wed Dec 09, 2015

Author(s): Chengwei Wang, Nicolás Rubido, Celso Grebogi, and Murilo S. Baptista

Scientists have been considering the Kuramoto model to understand the mechanism behind the appearance of collective behavior, such as frequency synchronization (FS) as a paradigm, in real-world networks with a finite number of oscillators. A major current challenge is to obtain an analytical solutio…

[Phys. Rev. E 92, 062808] Published Tue Dec 08, 2015

We study phase locking in the Kuramoto model of coupled oscillators in the special case where the number of oscillators, $N$, is large but finite, and the oscillators' natural frequencies are evenly spaced on a given interval. In this case, stable phase-locked solutions are known to exist if and only if the frequency interval is narrower than a certain critical width, called the locking threshold. For infinite $N$, the exact value of the locking threshold was calculated 30 years ago; however, the leading corrections to it for finite $N$ have remained unsolved analytically. Here we derive an asymptotic formula for the locking threshold when $N \gg 1$. The leading correction to the infinite-$N$ result scales like either $N^{-3/2}$ or $N^{-1}$, depending on whether the frequencies are evenly spaced according to a midpoint rule or an endpoint rule. These scaling laws agree with numerical results obtained by Paz\'{o} [Phys. Rev. E 72, 046211 (2005)]. Moreover, our analysis yields the exact prefactors in the scaling laws, which also match the numerics.

Author(s): Pan Zhang, Cristopher Moore, and M. E. J. Newman

Recently, a phase transition has been discovered in the network community detection problem below which no algorithm can tell which nodes belong to which communities with success any better than a random guess. This result has, however, so far been limited to the case where the communities have the …

[Phys. Rev. E] Published Wed Dec 02, 2015

Author(s): Antoine Allard, Laurent Hébert-Dufresne, Jean-Gabriel Young, and Louis J. Dubé

We present a comprehensive and versatile theoretical framework to study site and bond percolation on clustered and correlated random graphs. Our contribution can be summarized in three main points. (i) We introduce a set of iterative equations that solve the exact distribution of the size and compos…

[Phys. Rev. E 92, 062807] Published Mon Dec 07, 2015

Designing algorithms that generate networks with a given degree sequence while varying both subgraph composition and distribution of subgraphs around nodes is an important but challenging research problem. Current algorithms lack control of key network parameters, the ability to specify to what subgraphs a node belongs to, come at a considerable complexity cost or, critically, sample from a limited ensemble of networks. To enable controlled investigations of the impact and role of subgraphs, especially for epidemics, neuronal activity or complex contagion, it is essential that the generation process be versatile and the generated networks as diverse as possible. In this paper, we present two new network generation algorithms that use subgraphs as building blocks to construct networks preserving a given degree sequence. Additionally, these algorithms provide control over clustering both at node and global level. In both cases, we show that, despite being constrained by a degree sequence and global clustering, generated networks have markedly different topologies as evidenced by both subgraph prevalence and distribution around nodes, and large-scale network structure metrics such as path length and betweenness measures. Simulations of standard epidemic and complex contagion models on those networks reveal that degree distribution and global clustering do not always accurately predict the outcome of dynamical processes taking place on them. We conclude by discussing the benefits and limitations of both methods.

Donate to arXiv

In this paper, we present a method for characterizing the evolution of time-varying complex networks by adopting a thermodynamic representation of network structure computed from a polynomial (or algebraic) characterization of graph structure. Commencing from a representation of graph structure based on a characteristic polynomial computed from the normalized Laplacian matrix, we show how the polynomial is linked to the Boltzmann partition function of a network. This allows us to compute a number of thermodynamic quantities for the network, including the average energy and entropy. Assuming that the system does not change volume, we can also compute the temperature, defined as the rate of change of entropy with energy. All three thermodynamic variables can be approximated using low-order Taylor series that can be computed using the traces of powers of the Laplacian matrix, avoiding explicit computation of the normalized Laplacian spectrum. These polynomial approximations allow a smoothed representation of the evolution of networks to be constructed in the thermodynamic space spanned by entropy, energy, and temperature. We show how these thermodynamic variables can be computed in terms of simple network characteristics, e.g., the total number of nodes and node degree statistics for nodes connected by edges. We apply the resulting thermodynamic characterization to real-world time-varying networks representing complex systems in the financial and biological domains. The study demonstrates that the method provides an efficient tool for detecting abrupt changes and characterizing different stages in network evolution.

Donate to arXiv

Publication date: 1 March 2016
Source:Physica A: Statistical Mechanics and its Applications, Volume 445
Author(s): Xiangrong Wang, Stojan Trajanovski, Robert E. Kooij, Piet Van Mieghem
Topological characteristics of links of complex networks influence the dynamical processes executed on networks triggered by links, such as cascading failures triggered by links in power grids and epidemic spread due to link infection. The line graph transforms links in the original graph into nodes. In this paper, we investigate how graph metrics in the original graph are mapped into those for its line graph. In particular, we study the degree distribution and the assortativity of a graph and its line graph. Specifically, we show, both analytically and numerically, the degree distribution of the line graph of an Erdős–Rényi graph follows the same distribution as its original graph. We derive a formula for the assortativity of line graphs and indicate that the assortativity of a line graph is not linearly related to its original graph. Additionally, line graphs of various graphs, e.g. Erdős–Rényi graphs, scale-free graphs, show positive assortativity. In contrast, we find certain types of trees and non-trees whose line graphs have negative assortativity.

Author(s): A. Navas, J. A. Villacorta-Atienza, I. Leyva, J. A. Almendral, I. Sendiña-Nadal, and S. Boccaletti

Synchronization of networked oscillators is known to depend fundamentally on the interplay between the dynamics of the graph's units and the microscopic arrangement of the network's structure. We here propose an effective network whose topological properties reflect the interplay between the topolog…

[Phys. Rev. E] Published Mon Nov 23, 2015

Author(s): Arindam Mishra, Chittaranjan Hens, Mridul Bose, Prodyot K. Roy, and Syamal K. Dana

We report chimeralike states in an ensemble of oscillators using a type of global coupling consisting of two components: attractive and repulsive mean-field feedback. We identify existence of two types of chimeralike states in a bistable Liénard system; in one type, both the coherent and the in…

[Phys. Rev. E] Published Mon Nov 23, 2015

Author(s): Yusuke Suda and Koji Okuda

Chimera states in the systems of nonlocally coupled phase oscillators are considered stable in the continuous limit of spatially distributed oscillators. However, it is reported that in the numerical simulations without taking such limit, chimera states are chaotic transient and finally collapse int…

[Phys. Rev. E] Published Mon Nov 23, 2015

Author(s): S. Belan

Decentralised control of autonomous phase oscillators integrated into networked systems is of great interest for many technological applications, from clock synchronization in sensor nets to coordinated motion in swarm robotics. In simplest distributed synchronization scheme, each oscillator updates…

[Phys. Rev. E] Published Mon Nov 23, 2015

Author(s): Kaori Sugimura and Hiroshi Kori

Excitable media can develop spiral chaos, in which the number of spirals changes chaotically with time. Depending on parameter values in dynamical equations, spiral chaos may permanently persist or spontaneously arrive at a steady state after a transient time, referred to as the lifetime. Previous n…

[Phys. Rev. E] Published Mon Nov 30, 2015

Author(s): Juan Ignacio Perotti, Claudio Juan Tessone, and Guido Caldarelli

The quest for a quantitative characterization of community and modular structure of complex networks produced a variety of methods and algorithms to classify different networks. However, it is not clear if such methods provide consistent, robust and meaningful results when considering hierarchies as…

[Phys. Rev. E] Published Mon Nov 30, 2015

Author(s): Charo I. del Genio, Miguel Romance, Regino Criado, and Stefano Boccaletti

We provide a rigorous solution to the problem of constructing a structural evolution for a network of coupled identical dynamical units that switches between specified topologies without constraints on their structure. The evolution of the structure is determined indirectly, from a carefully built t…

[Phys. Rev. E] Published Mon Nov 30, 2015

We consider a general criterion to discern the nature of the threshold in epidemic models on scale-free (SF) networks. Comparing the epidemic lifespan of the nodes with largest degrees with the infection time between them, we propose a general dual scenario, in which the epidemic transition is either ruled by a hub activation process, leading to a null threshold in the thermodynamic limit, or given by a collective activation process, corresponding to a standard phase transition with a finite threshold. We validate the proposed criterion applying it to different epidemic models, with waning immunity or heterogeneous infection rates in both synthetic and real SF networks. In particular, a waning immunity, irrespective of its strength, leads to collective activation with finite threshold in scale-free networks with large exponent, at odds with canonical theoretical approaches.

Donate to arXiv

Author(s): L. Q. English, Zhuwei Zeng, and David Mertens

The authors explored synchronization dynamics of a system of coupled electronic oscillators. From a series of measurements on a pair of coupled oscillators, they obtained two adjustable parameters for the Sakaguchi-Kuramoto model. They found good agreement between predictions of this model and their experimental measurements on a system of 20 oscillators.

[Phys. Rev. E 92, 052912] Published Mon Nov 30, 2015

Author(s): Debarati Ghosh and Tanmoy Banerjee

We report a collective dynamical state, namely the mixed-mode oscillation suppression state where the steady states of the state variables of a system of coupled oscillators show heterogeneous behaviors. We identify two variants of it: The first one is a mixed-mode death (MMD) state, which is an int…

[Phys. Rev. E 92, 052913] Published Mon Nov 30, 2015

Three years ago, we initiated a programme of research in which ideas and tools from statistical physics and network theory were applied to the field of comparative mythology. The eclecticism of the work, together with the perspectives it delivered, led to widespread media coverage and academic discussion. Here we review some aspects of the project, contextualised with a brief history of the long relationship between science and the humanities. We focus in particular on an Irish epic, summarising some of the outcomes of our quantitative investigation. We also describe the emergence of a new sub-discipline and our hopes for its future.

Author(s): Sang-Yoon Kim and Woochang Lim

We consider a clustered network with small-world subnetworks of inhibitory fast spiking interneurons and investigate the effect of intermodular connection on the emergence of fast sparsely synchronized rhythms by varying both the intermodular coupling strength Jinter and the average number of interm…

[Phys. Rev. E 92, 052716] Published Mon Nov 23, 2015

We investigate the Laplacian spectra of random geometric graphs (RGGs). The spectra are found to consist of both a discrete and a continuous part. The discrete part is a collection of Dirac delta peaks at integer values roughly centred around the mean degree. The peaks are mainly due to the existence of mesoscopic structures that occur far more abundantly in RGGs than in non-spatial networks. The probability of certain mesoscopic structures is analytically calculated for one-dimensional RGGs and they are shown to produce integer-valued eigenvalues that comprise a significant fraction of the spectrum, even in the large network limit. A phenomenon reminiscent of Bose–Einstein condensation in the appearance of zero eigenvalues is also found.

We survey the concept of assortativity, starting from its original definition by Newman in 2002. Degree assortativity is the most commonly used form of assortativity. Degree assortativity is extensively used in network science. Since degree assortativity alone is not sufficient as a graph analysis tool, assortativity is usually combined with other graph metrics. Much of the research on assortativity considers undirected, non-weighted networks. The research on assortativity needs to be extended to encompass also directed links and weighted links. In addition, the relation between assortativity and line graphs, complementary graphs and graph spectra needs further work, to incorporate directed graphs and weighted links. The present survey paper aims to summarize the work in this area and provides a new scope of research.

Author(s): Xiao Zhang and M. E. J. Newman

One of the most widely used methods for community detection in networks is the maximization of the quality function known as modularity. Of the many maximization techniques that have been used in this context, some of the most conceptually attractive are the spectral methods, which are based on the …

[Phys. Rev. E 92, 052808] Published Thu Nov 19, 2015

Author(s): Ernesto Estrada, Eusebio Vargas-Estrada, and Hiroyasu Ando

We consider the question of determining how the topological structure influences a consensus dynamical processes taking place on a network. By considering a large data set of real-world networks we first determine that the removal of edges according to their communicability angle, an angle between p…

[Phys. Rev. E 92, 052809] Published Thu Nov 19, 2015

Author(s): Jonathan Kadmon and Haim Sompolinsky

Cortical neural circuits have been hypothesized to operate in a regime termed the “edge of chaos.” A new theoretical study puts this regime in a more biologically plausible perspective.

[Phys. Rev. X 5, 041030] Published Thu Nov 19, 2015

The synchronization of self-propelled particles (SPPs) is a fascinating instance of emergent behavior in living and man-made systems, such as colonies of bacteria, flocks of birds, robot ensembles, and many others. The recent discovery of chimera states in coupled oscillators opens up new perspectives and indicates that other emergent behaviors may exist for SPPs. Indeed, for a minimal extension of the classical Vicsek model we show the existence of chimera states for SPPs, i.e., one group of particles synchronizes while others wander around chaotically. Compared to chimeras in coupled oscillators where the site position is fixed, SPPs give rise to new distinctive forms of chimeric behavior. We emphasize that the found behavior is directly implied by the structure of the deterministic equation of motion and is not caused by exogenous stochastic excitation. In the scaling limit of infinitely many particles, we show that the chimeric state persists. Our findings provide the starting point for the search or elicitation of chimeric states in real world SPP systems.