Broad lifetime distributions for ordering dynamics in complex networks

We search for conditions under which a characteristic time scale for ordering dynamics toward either of two absorbing states in a finite complex network of interactions does not exist. With this aim, we study random networks and networks with mesoscale community structure built up from randomly connected cliques. We find that large heterogeneity at the mesoscale level of the network appears to be a sufficient mechanism for the absence of a characteristic time for the dynamics. Such heterogeneity results in dynamical metastable states that survive at any time scale.

Figure 1

(Color online) Fraction $P\left(t\right)$ of runs alive at time $t$ for Erdős-Rényi (ER) networks with different average degrees (◻, $⟨k⟩=10$; △, $⟨k⟩=5$). Solid symbols, network size $N={10}^3$; open symbols, $N={10}^5$. Averaged over 100 network realizations, 100 runs in each (1000 in each for $N={10}^3$).

Figure 2

(Color online) Time evolution of the fraction $f_m$ of nodes in the state ($A$ or $B$) that became the minority and finally died out, in several individual runs. (a) ER $⟨k⟩=5$, $N={10}^5$; (b) ER $⟨k⟩=10$, $N={10}^5$.

Figure 3

(Color online) (a) Schematic illustration of branches in the different ER networks studied. The root nodes are indicated by open circles. (b) The fraction of alive runs $P\left(t\right)$ for ER networks with $⟨k⟩=5$ and $N={10}^5$, and their two-cores. (c) ER networks with $⟨k⟩=2$ and $N=2\times {10}^3$, and their two-cores. Averaged over 100 network realizations, 100 runs in each (5000 network realizations for two-core of $⟨k⟩=2$).

Figure 4

Characterization of the dynamical robustness against invasion for a given topological structure $G$. We show a schematic view for two example cases: (a) a branch excluding the root node and (b) a clique.

Figure 5

(Color online) Fraction of alive runs $P\left(t\right)$ for a chain (a branch with no bifurcations) with diameter 2 (open circles), a branch with diameter 2 with a single bifurcation (diamonds), and a chain with diameter 3 (solid circles), initialized such that the nodes denoted by open squares are permanently set to one state, and the remaining nodes are initially set to the opposing state. We performed 10 000 runs in each topology.

Figure 6

Generation of networks with equally sized cliques: (a) EDH and (b) ERH. To obtain an ERH network of size $N$, we begin with an underlying ER network with $N∕s$ nodes, where $s$ is the clique size.

Figure 7

Time evolution of the fraction of $A$ agents $f_A$ in each clique, labeled with numbers from 1 to 100, in a single run in an ERH network with clique size $s=10$, $N=1000$, and $⟨k_{c,\mathrm{out}}⟩=10$. The resolution is ten time steps.

Figure 8

(Color online) Time evolution of (a) the number $n_m$ of agents in the minority state, and (b) interface density $\rho$, for two typical runs that developed metastable states in an ERH network, $s=10$, $⟨k_{c,\mathrm{out}}⟩=10$, $N=1000$.

Figure 9

(Color online) Dynamical robustness of a clique [as in Fig. 4b, see text]. (a) The fraction of alive runs $P\left(t\right)\sim e^{-t∕\tau }$ shows a trend with $r=s(s-1)∕k_{c,\mathrm{out}}$. Various ratios $r$ are each represented by two pairs of $(s,k_{c,\mathrm{out}})$. From left to right: $r=2$, (6,15) and (3,3); $r=3$, (6,10) and (4,4); $r=5$, (6,6) and (5,4); $r=7$, (8,8) and (7,6); $r=10$, (6,3) and (10,9). We performed 10 000 runs in each topology. (b) Dependence $\tau \left(r\right)$. Clique sizes $s=6$ (◻), $s=10$ (∗), and $s=13$ (○), and $k_{c,\mathrm{out}}$ ranging from 1 to 15, 20, or 30 respectively, leading to the displayed $r$ values.

Figure 10

(Color online) Fraction of alive runs in EDH, ERH, and PERH networks with $N\approx {10}^3$ and $k_{c,\mathrm{out}}=10$. (a) EDH networks with clique sizes $s=6$, 8, 9, and 10. (b) ERH networks with clique sizes $s=3$, 6, and 10. (c) The ERH network with $s=10$ together with the corresponding PERH network. All cases averaged over 100 network realizations (except ${10}^3$ for ERH $s=6$), with 100 runs in each.

Figure 11

(Color online) Two typical runs that developed metastable states in EDE networks with $k_{c,\mathrm{out}}=3$, $\mu =1.2$, $s_{\min }=3$, and $N_c=270$, leading to $N\approx {10}^3$. Time evolution of (a) the fraction and (b) the number of agents in the state that became the minority, and (c) the number of cliques in which more than 90% of agents were in the minority state.

Figure 12

(Color online) Fraction of alive runs $P\left(t\right)$ in EDE networks with various factors $\mu$ of the clique size distribution $p\left(s\right)\sim \exp [-(s-s_{\min })∕\mu ]$ with $s_{\min }=3$. From left to right: $\mu =1.0$, 1.2, 1.5, 2.0 and $N_c=280$, 270, 260, 225, leading to $N\approx 1000$. Clique out-degree $k_{c,\mathrm{out}}=3$. Results are averaged over 1000 network realizations (2000 for $\mu =1.0$) with ten runs in each. The fitted lines are power laws $P\left(t\right)\sim t^{-\eta }$ with exponents from left to right $\eta =1.51,1.3,0.92$.