Early fragmentation in the adaptive voter model on directed networks

We consider voter dynamics on a directed adaptive network with fixed out-degree distribution. A transition between an active phase and a fragmented phase is observed. This transition is similar to the undirected case if the networks are sufficiently dense and have a narrow out-degree distribution. However, if a significant number of nodes with low out degree is present, then fragmentation can occur even far below the estimated critical point due to the formation of self-stabilizing structures that nucleate fragmentation. This process may be relevant for fragmentation in current political opinion formation processes.

Figure 1

Typical trajectories from network simulations. The state of the network is characterized by the density of active links $\rho$ and the magnetization $m$. The trajectories shown correspond to networks with Poissonian out-degree distributions with $\langle k\rangle =4$ [light gray (red)] and $\langle k\rangle =8$ (black) and an out-degree distribution following $P_{\mathrm{out}}\left(k\right)\propto k^{-2}$ [dark gray (blue)]. The trajectories initially drift along a parabola of active states [dotted (red), dashed (black), and dash-dotted (blue) lines, denoting analytical results from Eq. (10)]; however, only the black trajectory reaches a consensus state, whereas the others eventually collapse to a fragmented state. The inset shows a time series of $\rho$ from the scale-free network shortly before fragmentation. The parameters are $N={10}^4$ and $p=0.1$.

Figure 2

Transitions of a general active motif $(m_{\mathrm{in}},m_{\mathrm{out}},l_{\mathrm{in}},l_{\mathrm{out}})$. The transition probabilities follow from the link update rule of the directed adaptive voter model. New active motifs are created only when an opinion update occurs on an incoming active link (second transition). In this case the number of incoming and outgoing active links (dashed) of the new motif is estimated based on the in-degree distribution $P_{\text{in}}$ and out-degree distribution $P_{\text{out}}$ of the underlying network.

Figure 3

Fragmentation of a network with Poissonian out-degree distribution and $\langle k\rangle =8$. Shown is the absolute value of the magnetization in the final frozen state (top) and the proportion $r$ of simulation runs that reaches a fragmented state before $t_{\max }=80000$ (bottom) as a function of the rewiring rate $p$. Each point is an average over 100 simulations. The critical point computed by the moment closure approximation (dotted line) overestimates the critical rewiring rate, whereas the motif expansion yields a better estimate of the true fragmentation point. For the motif expansion a cutoff of ${\widehat{k}}_{\mathrm{in}}={\widehat{k}}_{\mathrm{out}}=10$ was used. For a higher cutoff the estimated critical rewiring rate is expected to shift to slightly higher values.

Figure 4

Early fragmentation in scale-free networks. The plots are analogous to Fig. 3, but describe networks with an out-degree distribution $P_{\mathrm{out}}\left(k\right)\propto k^{-\alpha }$. Fragmentation occurs far below the estimated transition points [for the motif expansion $\alpha =2$ (dashed line), $\alpha =2.25$ (dash–double-dotted line), and $\alpha =2.5$ (dash-dotted line) and for the moment closure $\alpha =2$ (dotted line)] and extends over a wider range. The parameters are $N={10}^4$, ${\widehat{k}}_{\mathrm{in}}={\widehat{k}}_{\mathrm{out}}=10$, and $\langle k\rangle =5.5665$, $2.7042$, and $1.876$ for $\alpha =2$, $2.25$, and $2.5$, respectively.

Figure 5

Average in degree vs out degree at the initial ($t=0$, circles), intermediate ($t=20$, squares), and stabilized stage before full fragmentation ($t=500$, diamonds). Shown is the average in degree of the network nodes vs their logarithmically binned out degree, averaged over 10 simulation runs. On average, the in degree of nodes with large out degree decreases with time. The parameters are $N=5000$, $P_{\mathrm{out}}\left(k\right)\propto k^{-2}$, and $p=0.3$.

Figure 6

Snapshots of an exemplary network of $N=100$ nodes with out-degree distribution $P_{\mathrm{out}}\left(k\right)\propto k^{-2}$ at $t=200$, 250, 350, and 400 (from top to bottom). Two state-homogeneous attracting components [dark gray (blue)] nucleate self-stabilizing structures leading to early fragmentation. Note that the nodes with high out degree (represented by the node size) have very low or zero in degree and keep the network connected for a long time. Here fragmentation is reached at $t\approx 413$.

Figure 7

Typical restriction of the permissible magnetization range by self-stabilizing structures. Shown are the upper and lower bounds for $m$ [dashed (red) and dotted (blue) lines] computed from the total size $S_A$ and $S_B$ of the stable $A$ and $B$ components, i.e., maximally connected components in which each node has outgoing links to nodes in the same state only. The magnetization is confined to the shaded area and effectively arrested eventually at a fixed value. The arrow marks the point when only a single remaining hub node connects the two parts of the network (cf. Fig. 6). Here fragmentation is reached at $t\approx 524$. The jumps occur when the last links leaving a self-stabilizing structure are rewired to nodes within the same structure so that it is fully stabilized and can be detected. The parameters are $N=500$, $P_{\mathrm{out}}\left(k\right)\propto k^{-2}$, and $p=0.3$.

Figure 8

Fragmentation of networks with Poissonian out-degree distribution and low $\langle k\rangle$, in which the inert links are also rewired (squares) or are not rewired (circles). Early fragmentation is clearly visible, although the shown averages over 100 simulation runs are still rather noisy due to the highly stochastic nature of early fragmentation. Shown are the absolute value of the magnetization (top), the proportion of fragmenting simulation runs (middle), and the correlation coefficient between the in and out degree of the nodes in the final state (bottom). The parameters are $N={10}^4$, $\langle k\rangle =4$, and ${\widehat{k}}_{\mathrm{in}}={\widehat{k}}_{\mathrm{out}}=10$.