Graphical Notation Reveals Topological Stability Criteria for Collective Dynamics in Complex Networks

We propose a graphical notation by which certain spectral properties of complex systems can be rewritten concisely and interpreted topologically. Applying this notation to analyze the stability of a class of networks of coupled dynamical units, we reveal stability criteria on all scales. In particular, we show that in systems such as the Kuramoto model the Coates graph of the Jacobian matrix must contain a spanning tree of positive elements for the system to be locally stable.

Figure 1

Examples for the graphical notation. Symbols denote the sum over all nonequivalent possibilities to build the depicted subgraph with the $q$ nodes $\in S$. Plotted are two example terms and their algebraic and topological equivalents.

Figure 2

Symbolic calculation of a determinant using the graphical notation. Consider the minor $D_{4,S}$ of the graph $\mathcal{G}$ sketched above. If $S$ is chosen to be the set of nodes plotted in grey, the terms of the fourth JSC, $D_{4,S}$, can be written as $\times ·\times ·\times ·\times =J_{11}{J}_{22}{J}_{33}{J}_{44}=(-1{)}^4(J_{12}+J_{13})(J_{21}+J_{23})(J_{31}+J_{32}+J_{34})·(J_{43}+J_{45})=A+B+C+2D$, $-\times ·\times ·|=-(B+2C)$, $|·|=C$, $2\times ·\Delta =-2D$, and $-2\square =0$. We can immediately read off that $D_{4,S}\equiv A={\Phi }_S$, defined in the text.

Figure 3

Decomposition of a graph $\mathcal{G}$ in acyclic parts (black), unbranched segments of cycles (grey), and branching points (open black). Lines represent paths of $\mathcal{G}$ that may contain several nodes. Stability requires that (i) the acyclic parts only contain links with positive weights; (ii) any unbranched segment of a cycle contains at most one link with negative weight and (iii) the number of links with negative weight do not exceed the number of independent cycles (here, 5).