Thomas

Networks of Kuramoto oscillators with a positive correlation between the oscillators frequencies and the degree of the their corresponding vertices exhibits the so-called explosive synchronization behavior, which is now under intensive investigation. Here, we study and report explosive synchronization in a situation that has not yet been considered, namely when only a part, typically small, of the vertices is subjected to a degree frequency correlation. Our results show that in order to have explosive synchronization, it suffices to have degree-frequency correlations only for the hubs, the vertices with the highest degrees. Moreover, we show that a partial degree-frequency correlation does not only promotes but also allows explosive synchronization to happen in networks for which a full degree-frequency correlation would not allow it. We perform exhaustive numerical experiments for synthetic networks and also for the undirected and unweighted version of the neural network of the worm Caenorhabditis elegans. The latter is an explicit example where partial degree-frequency correlation leads to explosive synchronization with hysteresis, in contrast with the fully correlated case, for which no explosive synchronization is observed.

What can we learn from the collective dynamics of a complex network about its interaction topology? Taking the perspective from nonlinear dynamics, we briefly review recent progress on how to infer structural connectivity (direct interactions) from accessing the dynamics of the units. Potential applications range from interaction networks in physics, to chemical and metabolic reactions, protein and gene regulatory networks as well as neural circuits in biology and electric power grids or wireless sensor networks in engineering. Moreover, we briefly mention some standard ways of inferring effective or functional connectivity.

Author(s): Tongfeng Weng, Yi Zhao, Michael Small, and Defeng (David) Huang

We generate time series from scale-free networks based on a finite-memory random walk traversing the network. These time series reveal topological and functional properties of networks via their temporal correlations. Remarkably, networks with different node-degree mixing patterns exhibit distinct s...

[Phys. Rev. E 90, 022804] Published Fri Aug 08, 2014

Complex networks are ubiquitous in nature and play a role of paramount importance in many contexts. Internet and the cyberworld, which permeate our everyday life, are self-organized hierarchical graphs. Urban traffic flows on intricate road networks, which impact both transportation design and epidemic control. In the brain, neurons are cabled through heterogeneous connections, which support the propagation of electric signals. In all these cases, the true challenge is to unveil the mechanisms through which specific dynamical features are modulated by the underlying topology of the network. Here, we consider agents randomly hopping along the links of a graph, with the additional possibility of performing long-range hops to randomly chosen disconnected nodes with a given probability. We show that an optimal combination of the two jump rules exists that maximises the efficiency of target search, the optimum reflecting the topology of the network.

Recent years have witnessed a growing interest in understanding the fundamental principles of how epidemic, ideas or behaviour spread over large networks (e.g. the Internet or online social networks). The conventional approach is to use the susceptible-infected-susceptible (SIS) model or its derivatives. We like to note that these models are often too restrictive and may not be applicable in many realistic situations. In this paper, we propose a ‘generalized SIS model’ by allowing the existence of intermediate states between susceptible and infected states. To analyse the diffusion process of the generalized SIS model on large graphs, we use the ‘mean-field analysis technique’ to determine which initial condition leads to or prevents the outbreak of information or virus. For any general connected graphs, we show that the condition which can prevent the spread of contagions depends on two de-coupled effects: the network topology and the parametric values of the generalized SIS model. Experimental results based on both synthetic and real-world datasets show that our methodology can accurately predict the behaviour of the phase-transition process for any general graphs. We also extend our generalized SIS model to analyse the dynamics and behaviour of two competing sources. This is useful if one wants to model competing products in a large network or competition between virus and antidote in a large communication network. We present the analytical derivation and show via experiment how different factors such as initial condition, transmission rates, recovery rates or the number of states can affect the phase transition process and the final equilibrium. Our models and methodology can serve as an essential tool in analysing and understanding the information diffusion process in large networks.

When resources are shared between interacting networks, the importance of each node depends strongly on how collaborative or competitive each sub-network is. In this paper, we develop a new method of measuring centrality in the complex network of patent citations that can take political borders into account, where the national benefit of domestic citations relative to foreign citations can be controlled by a free parameter. We find that while some patent classes are of high importance both in the global and the domestic economy, there often exist patent classes in individual countries that are more central nationally than in global economy. We characterize the most important classes globally and domestically for six different nations, and describe their robustness to various perturbations to the model and to noise.

We introduce network $L$-cloning, a technique for creating ensembles of random networks from any given real-world or artificial network. Each member of the ensemble is an $L$-cloned network constructed from $L$ copies of the original network. The degree distribution of an $L$-cloned network and, more importantly, the degree-degree correlation between and beyond nearest neighbors are identical to those of the original network. The density of triangles in an \LC network, and hence its clustering coefficient, is reduced by a factor of $L$ compared to those of the original network. Furthermore, the density of loops of any fixed length approaches zero for sufficiently large values of $L$. Other variants of $L$-cloning allow us to keep intact the short loops of certain lengths. As an application, we employ these network cloning methods to investigate the effect of short loops on dynamical processes running on networks and to inspect the accuracy of corresponding tree-based theories. We demonstrate that dynamics on $L$-cloned networks (with sufficiently large $L$) are accurately described by the so-called adjacency tree-based theories, examples of which include the message passing technique, some pair approximation methods, and the belief propagation algorithm used respectively to study bond percolation, SI epidemics, and the Ising model.

We numerically study bootstrap percolation on Kleinberg's spatial networks, in which the probability density function of a node to have a long-range link at distance $r$ scales as $P(r)\sim r^{\alpha}$. Setting the ratio of the size of the giant active component to the network size as the order parameter, we find a critical exponent $\alpha_{c}=-1$, above which a hybrid phase transition is observed, with both the first-order and second-order critical points being constant. When $\alpha<\alpha_{c}$, the second-order critical point increases as the decreasing of $\alpha$, and there is either absent of the first-order phase transition or with a decreasing first-order critical point as the decreasing of $\alpha$, depending on other parameters. Our results expand the current understanding on the spreading of information and the adoption of behaviors on spatial social networks.

Social and biological contagions are influenced by the spatial embeddedness of networks. Historically, many epidemics spread as a wave across part of the Earth's surface; however, in modern contagions long-range edges -- for example, due to airline transportation or communication media -- allow clusters of a contagion to appear in distant locations. Here we study the spread of contagions on networks through a methodology grounded in topological data analysis and nonlinear dimension reduction. We construct "contagion maps" that use multiple contagions on a network to map the nodes as a point cloud. By analyzing the topology, geometry, and dimensionality of manifold structure in such point clouds, we reveal insights to aid in the modeling, forecast, and control of spreading processes. Our approach highlights contagion maps also as a viable tool for inferring low-dimensional structure in networks.

Recent empirical studies using large-scale data sets have validated the Granovetter hypothesis on the structure of the society in that there are strongly wired communities connected by weak ties. However, as interaction between individuals takes place in diverse contexts, these communities turn out to be overlapping. This implies that the society has a multilayered structure, where the layers represent the different contexts. To model this structure we begin with a single-layer weighted social network (WSN) model showing the Granovetterian structure. We find that when merging such WSN models, a sufficient amount of interlayer correlation is needed to maintain the relationship between topology and link weights, while these correlations destroy the enhancement in the community overlap due to multiple layers. To resolve this, we devise a geographic multilayer WSN model, where the indirect interlayer correlations due to the geographic constraints of individuals enhance the overlaps between the communities and, at the same time, the Granovetterian structure is preserved.

Citation networks represent the flow of information between agents. They are constrained in time and so form directed acyclic graphs which have a causal structure. Here we provide novel quantitative methods to characterise that structure by adapting methods used in the causal set approach to quantum gravity by considering the networks to be embedded in a Minkowski spacetime and measuring its dimension using Myrheim-Meyer and Midpoint-scaling estimates. We illustrate these methods on citation networks from the arXiv, supreme court judgements from the USA, and patents and find that otherwise similar citation networks have measurably different dimensions. We suggest that these differences can be interpreted in terms of the level of diversity or narrowness in citation behaviour.

Our understanding of a variety of phenomena in physics, biology and economics crucially depends on the analysis of multivariate time series. While a wide range of tools and techniques for time series analysis already exist, the increasing availability of massive data structures calls for new approaches for multidimensional signal processing. We present here a non-parametric method to analyse multivariate time series, based on the mapping of a multidimensional time series into a multilayer network, which allows to extract information on a high dimensional dynamical system through the analysis of the structure of the associated multiplex network. The method is simple to implement, general, scalable, does not require ad hoc phase space partitioning, and is thus suitable for the analysis of large, heterogeneous and non-stationary time series. We show that simple structural descriptors of the associated multiplex networks allow to extract and quantify nontrivial properties of coupled chaotic maps, including the transition between different dynamical phases and the onset of various types of synchronization. As a concrete example we then study financial time series, showing that a multiplex network analysis can efficiently discriminate crises from periods of financial stability, where standard methods based on time-series symbolization often fail.

Author(s): Jun Tanimoto

In 2 × 2 prisoner's dilemma games, network reciprocity is one mechanism for adding social viscosity, which leads to cooperative equilibrium. This study introduced an intriguing framework for the strategy update rule that allows any combination of a purely deterministic method, imitation max (IM), an...

[Phys. Rev. E 90, 022105] Published Tue Aug 05, 2014

The critical behavior of the susceptible–infected–susceptible model is investigated on quenched directed scale-free networks with the in-degree ( k ) distribution ##IMG## [http://ej.iop.org/images/1742-5468/2014/8/P08004/jstat497361ieqn001.gif] {${{P}_{\text{in}}}\left(k\right)\sim {{k}^{-{{\gamma}_{\text{in}}}}}$} and the out-degree (ℓ) distribution, ##IMG## [http://ej.iop.org/images/1742-5468/2014/8/P08004/jstat497361ieqn002.gif] {${{P}_{\text{out}}}\left(\ell \right)\sim {{\ell}^{-{{\gamma}_{\text{out}}}}}$} . The correlation 〈 kl 〉 of each node is controlled. In the model, an infected individual becomes healthy with unit rate and infects all healthy neighbors with rate λ . On quenched undirected networks with degree distribution P ( q) ∼ q − γ , the system is always in an endemic state for any γ , so the critical threshold λ c is always zero. Heterogene...

With the availability of detailed information about the connectivity among brain areas, network analysis tools have been applied to datasets comprising cat and macaque cortical networks. Using evolutionary optimization algorithms (based on global analysis of the network), similarities between anatomical connections and functional properties of the areas of the brain have been found in previous works. To find functional properties of the brain, we have applied NetExplorer, a novel community detection algorithm based on local information dynamics, to two different datasets of cortical connectivity. We have compared the performances of NetExplorer with the results obtained by other six algorithms (Infomap, Hierarchical Infomap, Louvain, Modularity Optimization, Label Propagation and Oslom) with the same two datasets of cortical connectivity. In both datasets, NetExplorer places among the best algorithms in predicting the actual functional cortical clusters. We discuss the algorithm results considering the misattributions of brain areas to the different clusters and emphasizing the connections that are explainable by their multimodal functions.

Author(s): Ilker Tunc and Leah B. Shaw

When an epidemic spreads in a population, individuals may adaptively change the structure of their social contact network to reduce risk of infection. Here we study the spread of an epidemic on an adaptive network with community structure. We model two communities with different average degrees. The...

[Phys. Rev. E 90, 022801] Published Mon Aug 04, 2014

Random walk is one of the basic mechanisms found in many network applications. We study the epidemic spreading dynamics driven by biased random walks on complex networks. In our epidemic model, each time infected nodes constantly spread some infected packets by biased random walks to their neighbor nodes causing the infection of the susceptible nodes that receive the packets. An infected node get recovered from infection with a fixed probability. Simulation and analytical results on model and real-world networks show that the epidemic spreading becomes intense and wide with the increase of delivery capacity of infected nodes, average node degree, homogeneity of node degree distribution. Furthermore, there are corresponding optimal parameters such that the infected nodes have instantaneously the largest population, and the epidemic spreading process covers the largest part of a network.

The problem of decomposing networks into modules (or clusters) has gained much attention in recent years, as it can account for a coarse-grained description of complex systems, often revealing functional subunits of these systems. A variety of module detection algorithms have been proposed, mostly oriented towards finding hard partitionings of undirected networks. Despite the increasing number of fuzzy clustering methods for directed networks, many of these approaches tend to neglect important directional information. In this paper, we present a novel random walk based approach for finding fuzzy partitions of directed, weighted networks, where edge directions play a crucial role in defining how well nodes in a module are interconnected. We will show that cycle decomposition of a random walk process connects the notion of network modules and information transport in a network, leading to a new, symmetric measure of node communication. walk process, for which we will prove that although being time-reversible it inherits all necessary information about directions and modular structure of the original network. Finally, we will use this measure to introduce a communication graph, for which we will show that although being undirected it inherits all necessary information about modular structures from the original network.

Author(s): K. Hoppe and G. J. Rodgers

The ability to understand the impact of adversarial processes on networks is crucial to various disciplines. The objects of study in this article are fitness-driven networks. Fitness-dependent networks are fully described by a probability distribution of fitness and an attachment kernel. Every node ...

[Phys. Rev. E 90, 012815] Published Wed Jul 30, 2014

We generate time series from scale free networks based on a finite-memory random walk traversing the network. These time series reveal topological and functional properties of networks via their temporal correlations. Remarkably, networks with different node-degree mixing patterns exhibit distinct s...

We consider a dynamical network model in which two competitors have fixed and different states, and each normal agent adjusts its state according to a distributed consensus protocol. The state of each normal agent converges to a steady value which is a convex combination of the competitors' states, and is independent of the initial states of agents. This implies that the competition result is fully determined by the network structure and positions of competitors in the network. We compute an Influence Matrix (IM) in which each element characterizing the influence of an agent on another agent in the network. We use the IM to predict the bias of each normal agent and thus predict which competitor will win. Furthermore, we compare the IM criterion with seven node centrality measures to predict the winner. We find that the competitor with higher Katz Centrality in an undirected network or higher PageRank in a directed network is most likely to be the winner. These findings may shed new light on the role of network structure in competition and to what extent could competitors adjust network structure so as to win the competition.

Scientific Reports 4 doi: 10.1038/srep05858

Author(s): Luca Ferreri, Paolo Bajardi, Mario Giacobini, Silvia Perazzo, and Ezio Venturino

The structure of a network dramatically affects the spreading phenomena unfolding upon it. The contact distribution of the nodes has long been recognized as the key ingredient in influencing the outbreak events. However, limited knowledge is currently available on the role of the weight of the edges...

[Phys. Rev. E 90, 012812] Published Mon Jul 28, 2014

Author(s): Stefano Bonaccorsi, Stefania Ottaviano, Francesco De Pellegrini, Annalisa Socievole, and Piet Van Mieghem

We consider a model for the diffusion of epidemics in a population that is partitioned into local communities. In particular, assuming a mean-field approximation, we analyze a continuous-time susceptible-infected-susceptible (SIS) model that has appeared recently in the literature. The probability b...

[Phys. Rev. E 90, 012810] Published Mon Jul 21, 2014

Complex networks grow subject to structural constraints which affect their measurable properties. Assessing the effect that such constraints impose on their observables is thus a crucial aspect to be taken into account in their analysis. To this end, we examine the effect of fixing the strength sequence in multi-edge networks on several network observables such as degrees, disparity, average neighbor properties and weight distribution using an ensemble approach. We provide a general method to calculate any desired weighted network metric and we show that several features detected in real data could be explained solely by structural constraints. We thus justify the need of analytical null models to be used as basis to assess the relevance of features found in real data represented in weighted network form.

Characterizing the occupation statistics of random walks through confined geometries amounts to assessing the distribution of the travelled length ℓ and the number of collisions n performed by the stochastic process in a given region, for which remarkably simple Cauchy-like formulas were established in the case of branching Pearson random walks with exponentially distributed jumps. In this letter, we derive two key results: first, we show that such formulas strikingly carry over to the much broader class of branching processes with arbitrary jumps, and have thus a universal character; second, we obtain a stronger version of these formulas relating the travelled length density and the collision density at any point of the phase space. Our results are key to such technological issues as the analysis of radiation flow for nuclear reactor design and medical diagnosis and apply more broadly to physical and biological systems with diffusion, reproduction and death.

We characterize the statistical law according to which Italian primary school-size distributes. We find that the school-size can be approximated by a log-normal distribution, with a fat lower tail that collects a large number of very small schools. The upper tail of the school-size distribution decreases exponentially and the growth rates are distributed with a Laplace PDF. These distributions are similar to those observed for firms and are consistent with a Bose-Einstein preferential attachment process. The body of the distribution features a bimodal shape suggesting some source of heterogeneity in the school organization that we uncover by an in-depth analysis of the relation between schools-size and city-size. We propose a novel cluster methodology and a new spatial interaction approach among schools which outline the variety of policies implemented in Italy. Different regional policies are also discussed shedding lights on the relation between policy and geographical features.

We describe the complex global structure of giant components in directed multiplex networks which 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, $9$ 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.

Random walks are basic diffusion processes on networks and have applications in, for example, searching, navigation, ranking, and community detection. Recent recognition of the importance of temporal aspects on networks spurred studies of random walks on temporal networks. Here we theoretically study two types of event-driven random walks on a stochastic temporal network model that produces arbitrary distributions of interevent-times. In the so-called active random walk, the interevent-time is reinitialized on all links upon each movement of the walker. In the so-called passive random walk, the interevent-time is only reinitialized on the link that has been used last time, and it is a type of correlated random walk. We find that the steady state is always the uniform density for the passive random walk. In contrast, for the active random walk, it increases or decreases with the node's degree depending on the distribution of interevent-times. The mean recurrence time of a node is inversely proportional to the degree for both active and passive random walks. Furthermore, the mean recurrence time does or does not depend on the distribution of interevent-times for the active and passive random walks, respectively.

In most natural and engineered systems, a set of entities interact with each other in complicated patterns that can encompass multiple types of relationships, change in time and include other types of complications. Such systems include multiple subsystems and layers of connectivity, and it is important to take such ‘multilayer’ features into account to try to improve our understanding of complex systems. Consequently, it is necessary to generalize ‘traditional’ network theory by developing (and validating) a framework and associated tools to study multilayer systems in a comprehensive fashion. The origins of such efforts date back several decades and arose in multiple disciplines, and now the study of multilayer networks has become one of the most important directions in network science. In this paper, we discuss the history of multilayer networks (and related concepts) and review the exploding body of work on such networks. To unify the disparate terminology in the large body of recent work, we discuss a general framework for multilayer networks, construct a dictionary of terminology to relate the numerous existing concepts to each other and provide a thorough discussion that compares, contrasts and translates between related notions such as multilayer networks, multiplex networks, interdependent networks, networks of networks and many others. We also survey and discuss existing data sets that can be represented as multilayer networks. We review attempts to generalize single-layer-network diagnostics to multilayer networks. We also discuss the rapidly expanding research on multilayer-network models and notions like community structure, connected components, tensor decompositions and various types of dynamical processes on multilayer networks. We conclude with a summary and an outlook.

A general ##IMG## [http://ej.iop.org/images/0295-5075/107/2/28005/epl16408ieqn1.gif] {$(k,l)$} clique community of a network, which consists of adjacent k -cliques sharing at least l vertices with ##IMG## [http://ej.iop.org/images/0295-5075/107/2/28005/epl16408ieqn2.gif] {$k-1\ge l\ge1$} , is introduced. With the emergence of a giant ##IMG## [http://ej.iop.org/images/0295-5075/107/2/28005/epl16408ieqn3.gif] {$(k,l)$} clique community in the network, there is a ##IMG## [http://ej.iop.org/images/0295-5075/107/2/28005/epl16408ieqn4.gif] {$(k,l)$} clique percolation. Using the largest size jump Δ of the largest clique community during network evolution and the corresponding evolution step T c , we study the general ##IMG## [http://ej.iop.org/images/0295-5075/107/2/28005/epl16408ieqn5.gif] {$(k,l)$} clique percolation of the Erdős-Rényi ...