Observability and coarse graining of consensus dynamics through the external equitable partition

Scalable synchronization cluster in networked chaotic oscillators

Cluster synchronization in synthetic networks of coupled chaotic oscillators is investigated. It is found that despite the asymmetric nature of the network structure, a subset of the oscillators can be synchronized as a cluster while the other oscillators remain desynchronized. Interestingly, with the increase in the coupling strength, the cluster is expanding gradually by recruiting the desynchronized oscillators one by one. This new synchronization phenomenon, which is named "scalable synchronization cluster," is explored theoretically by the method of eigenvector-based analysis, and it is revealed that the scalability of the cluster is attributed to the unique feature of the eigenvectors of the network coupling matrix. The transient dynamics of the cluster in response to random perturbations are also studied, and it is shown that in restoring to the synchronization state, oscillators inside the cluster are stabilized in sequence, illustrating again the hierarchy of the oscillators. The findings shed new light on the collective behaviors of networked chaotic oscillators and are helpful for the design of real-world networks where scalable synchronization clusters are concerned.

Multi-type synchronization for coupled van der Pol oscillator systems with multiple coupling modes

In this paper, we investigate synchronous solutions of coupled van der Pol oscillator systems with multiple coupling modes using the theory of rotating periodic solutions. Multiple coupling modes refer to two or three types of coupling modes in van der Pol oscillator networks, namely, position, velocity, and acceleration. Rotating periodic solutions can represent various types of synchronous solutions corresponding to different phase differences of coupled oscillators. When matrices representing the topology of different coupling modes have symmetry, the overall symmetry of the oscillator system depends on the intersection of the symmetries of the different topologies, determining the type of synchronous solutions for the coupled oscillator network. When matrices representing the topology of different coupling modes lack symmetry, if the adjacency matrices representing different coupling modes can be simplified into structurally identical quotient graphs (where weights can be proportional) through the same external equitable partition, the symmetry of the quotient graph determines the synchronization type of the original system. All these results are consistent with multi-layer networks where connections between different layers are one-to-one.

Master stability functions of networks of Izhikevich neurons

Synchronization has attracted interest in many areas where the systems under study can be described by complex networks. Among such areas is neuroscience, where it is hypothesized that synchronization plays a role in many functions and dysfunctions of the brain. We study the linear stability of synchronized states in networks of Izhikevich neurons using master stability functions (MSFs), and to accomplish that, we exploit the formalism of saltation matrices. Such a tool allows us to calculate the Lyapunov exponents of the MSF properly since the Izhikevich model displays a discontinuity within its spikes. We consider both electrical and chemical couplings as well as global and cluster synchronized states. The MSF calculations are compared with a measure of the synchronization error for simulated networks. We give special attention to the case of electric and chemical coupling, where a riddled basin of attraction makes the synchronized solution more sensitive to perturbations.

Graph Partitions in Chemistry

We study partitions (equitable, externally equitable, or other) of graphs that describe physico-chemical systems at the atomic or molecular level; provide examples that show how these partitions are intimately related with symmetries of the systems; and discuss how such a link can further lead to insightful relations with the systems' physical and chemical properties. We define a particular kind of graph partition, which we call Chemical Equitable Partition (CEP), accounting for chemical composition as well as connectivity and associate it with a quantitative measure of information reduction that accompanies its derivation. These concepts are applied to model molecular and crystalline solid systems, illustrating their potential as a means to classify atoms according to their chemical or crystallographic role. We also cluster materials in meaningful manners that take their microstructure into account and even correlate them with the materials' physical properties.

Hierarchical community structure in networks

Modular and hierarchical community structures are pervasive in real-world complex systems. A great deal of effort has gone into trying to detect and study these structures. Important theoretical advances in the detection of modular have included identifying fundamental limits of detectability by formally defining community structure using probabilistic generative models. Detecting hierarchical community structure introduces additional challenges alongside those inherited from community detection. Here we present a theoretical study on hierarchical community structure in networks, which has thus far not received the same rigorous attention. We address the following questions. (1) How should we define a hierarchy of communities? (2) How do we determine if there is sufficient evidence of a hierarchical structure in a network? (3) How can we detect hierarchical structure efficiently? We approach these questions by introducing a definition of hierarchy based on the concept of stochastic externally equitable partitions and their relation to probabilistic models, such as the popular stochastic block model. We enumerate the challenges involved in detecting hierarchies and, by studying the spectral properties of hierarchical structure, present an efficient and principled method for detecting them.

Predicting network dynamics without requiring the knowledge of the interaction graph

A network consists of two interdependent parts: the network topology or graph, consisting of the links between nodes and the network dynamics, specified by some governing equations. A crucial challenge is the prediction of dynamics on networks, such as forecasting the spread of an infectious disease on a human contact network. Unfortunately, an accurate prediction of the dynamics seems hardly feasible, because the network is often complicated and unknown. In this work, given past observations of the dynamics on a fixed graph, we show the contrary: Even without knowing the network topology, we can predict the dynamics. Specifically, for a general class of deterministic governing equations, we propose a two-step prediction algorithm. First, we obtain a surrogate network by fitting past observations of every nodal state to the dynamical model. Second, we iterate the governing equations on the surrogate network to predict the dynamics. Surprisingly, even though there is no similarity between the surrogate topology and the true topology, the predictions are accurate, for a considerable prediction time horizon, for a broad range of observation times, and in the presence of a reasonable noise level. The true topology is not needed for predicting dynamics on networks, since the dynamics evolve in a subspace of astonishingly low dimension compared to the size and heterogeneity of the graph. Our results constitute a fresh perspective on the broad field of nonlinear dynamics on complex networks.

State Aggregations in Markov Chains and Block Models of Networks

We consider state-aggregation schemes for Markov chains from an information-theoretic perspective. Specifically, we consider aggregating the states of a Markov chain such that the mutual information of the aggregated states separated by T time steps is maximized. We show that for T=1 this recovers the maximum-likelihood estimator of the degree-corrected stochastic block model as a particular case, which enables us to explain certain features of the likelihood landscape of this generative network model from a dynamical lens. We further highlight how we can uncover coherent, long-range dynamical modules for which considering a timescale T≫1 is essential. We demonstrate our results using synthetic flows and real-world ocean currents, where we are able to recover the fundamental features of the surface currents of the oceans.

Clustering for epidemics on networks: A geometric approach

Infectious diseases typically spread over a contact network with millions of individuals, whose sheer size is a tremendous challenge to analyzing and controlling an epidemic outbreak. For some contact networks, it is possible to group individuals into clusters. A high-level description of the epidemic between a few clusters is considerably simpler than on an individual level. However, to cluster individuals, most studies rely on equitable partitions, a rather restrictive structural property of the contact network. In this work, we focus on Susceptible-Infected-Susceptible (SIS) epidemics, and our contribution is threefold. First, we propose a geometric approach to specify all networks for which an epidemic outbreak simplifies to the interaction of only a few clusters. Second, for the complete graph and any initial viral state vectors, we derive the closed-form solution of the nonlinear differential equations of the N-intertwined mean-field approximation of the SIS process. Third, by relaxing the notion of equitable partitions, we derive low-complexity approximations and bounds for epidemics on arbitrary contact networks. Our results are an important step toward understanding and controlling epidemics on large networks.

Multiscale dynamical embeddings of complex networks

Complex systems and relational data are often abstracted as dynamical processes on networks. To understand, predict, and control their behavior, a crucial step is to extract reduced descriptions of such networks. Inspired by notions from control theory, we propose a time-dependent dynamical similarity measure between nodes, which quantifies the effect a node-input has on the network. This dynamical similarity induces an embedding that can be employed for several analysis tasks. Here we focus on (i) dimensionality reduction, i.e., projecting nodes onto a low-dimensional space that captures dynamic similarity at different timescales, and (ii) how to exploit our embeddings to uncover functional modules. We exemplify our ideas through case studies focusing on directed networks without strong connectivity and signed networks. We further highlight how certain ideas from community detection can be generalized and linked to control theory, by using the here developed dynamical perspective.

Controllability of heterogeneous multiagent systems with two-time-scale feature

In this paper, we investigate the controllability problems for heterogeneous multiagent systems (MASs) with two-time-scale feature under fixed topology. Firstly, the heterogeneous two-time-scale MASs are modeled by singular perturbation system with a singular perturbation parameter, which distinguishes fast and slow subsystems evolving on two different time scales. Due to the ill-posedness problems caused by the singular perturbation parameter, we analyze the two-time-scale MASs via the singular perturbation method, instead of the general methods. Then, we split the heterogeneous two-time-scale MASs into slow and fast subsystems to eliminate the singular perturbation parameter. Subsequently, according to the matrix theory and the graph theory, we propose some necessary/sufficient criteria for the controllability of the heterogeneous two-time-scale MASs. Lastly, we give some simulation and numerical examples to demonstrate the effectiveness of the proposed theoretical results.

Graph partitions and cluster synchronization in networks of oscillators

Synchronization over networks depends strongly on the structure of the coupling between the oscillators. When the coupling presents certain regularities, the dynamics can be coarse-grained into clusters by means of External Equitable Partitions of the network graph and their associated quotient graphs. We exploit this graph-theoretical concept to study the phenomenon of cluster synchronization, in which different groups of nodes converge to distinct behaviors. We derive conditions and properties of networks in which such clustered behavior emerges and show that the ensuing dynamics is the result of the localization of the eigenvectors of the associated graph Laplacians linked to the existence of invariant subspaces. The framework is applied to both linear and non-linear models, first for the standard case of networks with positive edges, before being generalized to the case of signed networks with both positive and negative interactions. We illustrate our results with examples of both signed and unsigned graphs for consensus dynamics and for partial synchronization of oscillator networks under the master stability function as well as Kuramoto oscillators.

Introduction to focus issue: Patterns of network synchronization

The study of synchronization of coupled systems is currently undergoing a major surge fueled by recent discoveries of new forms of collective dynamics and the development of techniques to characterize a myriad of new patterns of network synchronization. This includes chimera states, phenomena determined by symmetry, remote synchronization, and asymmetry-induced synchronization. This Focus Issue presents a selection of contributions at the forefront of these developments, to which this introduction is intended to offer an up-to-date foundation.