Math Insight

The master stability function approach to determine the synchronizability of a network

The master stability function of Pecora and Carroll1 allows one to study the stability of the synchronous state for a large class of oscillator models coupled through a complex network.

The underlying model must be of the form \begin{align*} \diff{\vc{x}_i}{t} = \vc{F}(\vc{x}_i) + S \sum_{j \ne i} A_{ij} (\vc{H}(\vc{x}_j) - \vc{H}(\vc{x}_i)) \end{align*} $\vc{F}$: internal dynamics function. $\vc{H}$: coupling function. $S$: coupling strength. $A$: network adjacency matrix.

Due to the form of coupling, one solution is alwasy the synchronous state $\vc{x}_i(t) = \tilde{\vc{x}}(t)$, where all nodes $i$ are equal to the solution $\tilde{\vc{x}}(t)$ of the uncoupled equation.

Define the network Laplacian as $L=D-A$, where $D$ is diagonal of row sums of $A$. Rewrite model as: \begin{align*} \diff{\vc{x}_i}{t} = \vc{F}(\vc{x}_i) - S \sum_{j\ne i} L_{ij} \vc{H}(\vc{x}_j) \end{align*}

Linearize around synchronous state $\vc{x}_i=\tilde{\vc{x}}$. \begin{align*} \delta \vc{x}_i = \vc{x}_i - \tilde{\vc{x}} \end{align*} Assume can diagonalize $L$. Can decompose into separate equations along eigenvectors of $L$. \begin{align*} \textstyle \diff{\vc{y}_i}{t} = \left[D_{\vc{F}}(\tilde{\vc{x}}) - S\mu_i D_{\vc{H}}(\tilde{\vc{x}})\right] \vc{y}_i \end{align*} where $\vc{y}_i$ is mode of $\delta \vc{x}$ corresponding to $i$th eigenvector.

Calculate Lyapunov exponents of system. Need all to be negative to be stable. Find a region in complex plane in which all $S\mu_i$ must lie for stability.

Conclusion from Master Stability Function analysis: The effect of the network and the dynamics are separate. The dynamics $F$ and $H$ determine the region a critical region in the complex plane. In order for the completely synchronous state of a network to be stable, all scaled eigenvalues $S\mu_i$ must fit into the region.

If we are studying a network without knowing anything about the dynamics, we can still conclude that the more spread out the eigenvalues of $L=D-A$, the more likely the synchronous state will be unstable. We can use the spread of Laplacian eigenvalues as a synchronizability index.

For undirected graphs, the adjacency matrix $A$, and hence the Laplacian $L$, is symmetric. The eigenvalue are real. As one eigenvalue of the $L$ is always zero, so a measure for the spread of eigenvalues is the ratio of the largest to the smallest, $\mu_N/\mu_2$.

For directed networks, Nishikawa and Motter2 proposed using the normalized standard deviation of the eigenvalues as a synchronizability index. \begin{align} \sigma_\mu^2 = \frac{1}{d^2(N-1)}\sum_{i=2}^N | \mu_i - \bar{\mu}|^2, \label{eq:var_mu} \end{align} where $\bar{\mu} = \frac{1}{N-1} \sum_{i=2}^N \mu_i$ is the mean of the eigenvalues, $N$ is the number of nodes, and $d$ is the mean degree. This variance ignores the zero eigenvalue $\mu_1=0$ present in every Laplacian matrix.