Collective frequency variation in network synchronization and reverse PageRank

A wide range of natural and engineered phenomena rely on large networks of interacting units to reach a dynamical consensus state where the system collectively operates. Here we study the dynamics of self-organizing systems and show that for generic directed networks the collective frequency of the ensemble is not the same as the mean of the individuals' natural frequencies. Specifically, we show that the collective frequency equals a weighted average of the natural frequencies, where the weights are given by an outflow centrality measure that is equivalent to a reverse PageRank centrality. Our findings uncover an intricate dependence of the collective frequency on both the structural directedness and dynamical heterogeneity of the network, and also reveal an unexplored connection between synchronization and PageRank, which opens the possibility of applying PageRank optimization to synchronization. Finally, we demonstrate the presence of collective frequency variation in real-world networks by considering the UK and Scandinavian power grids.

Figure 1

Collective frequency variation. (a, b) Two networks of size $N=8$ with 16 links. In (b), the in- and out-degrees match at each node, in particular, $k_i^{\text{in}}=k_i^{\text{out}}=2$. In (a) this balance is broken, so $k_i^{\text{in}}\ne k_i^{\text{out}}$. Each node's area is proportional to the ratio $k_i^{\text{out}}/k_i^{\text{in}}$, which represents a mean field approximation to the first-left-singular vector ${\mathit{u}}^1$ of the Laplacian matrix $L$. (c) The density $P\left(\mathrm{\Omega }\right)$ of collective frequencies $\mathrm{\Omega }$ observed in networks (a) and (b) (solid blue and dashed red, respectively) for different permutations of a normally distributed frequency vector $\mathbf{\omega }$ with mean $\langle \omega \rangle =0$ and variance ${\sigma }^2=1$. We find $\mathrm{\Omega }$ to relate closely to the alignment of $\mathbf{\omega }$ with vector ${\mathit{u}}^1$, which represents an outflow centrality.

Figure 2

Range of collective frequency variation. For (a) ER and (b) SF networks of size $N=200$ and various mean degrees, the collective frequency variation range ${max}_{\text{var}\left(\mathbf{\omega }\right)={\sigma }^2}|\mathrm{\Omega }-\langle \omega \rangle |$ for ${\sigma }^2=1$.

Figure 3

First-left-singular-vector centrality and PageRank. (a) Entries ${\mathit{u}}_i^1$ of the first-left-singular vector vs the out-to-in-degree ratio $k_i^{\text{out}}/k_i^{\text{in}}$ for an ER network of size $N=200$ and $p=0.1$. (b) The relationship between PageRank entries $v_i$ (damped and undamped cases are plotted with red triangles and blue dots, respectively) and first-left-singular-vector entries for the same network. The expected inverse relationship $u_i^1{v}_i\approx \text{const.}$ is plotted as a black curve.

Figure 4

Collective frequency variation in power grid networks. (a, b) Course-grain representations of the UK and Scandinavian power grids, respectively. (c) Collective frequency variation $\mathrm{\Omega }-\langle \omega \rangle$ as observed from direct simulations of the power grid model given by Eq. (12) on the UK and Scandinavian power grid networks compared to the theoretical prediction of Eq. (7) given Eq. (13) in $50000$ realizations. Parameters $P_i$ and $C_i$ are drawn from a bimodal normal distribution and a $\gamma$ distribution with mean 1, respectively, as described in the text. (d) Distribution of collective frequency variation found for each network.