Islands of Stability in Motif Distributions of Random Networks

We consider random nondirected networks subject to dynamics conserving vertex degrees and study, analytically and numerically, equilibrium three-vertex motif distributions in the presence of an external field $h$ coupled to one of the motifs. For small $h$, the numerics is well described by the “chemical kinetics” for the concentrations of motifs based on the law of mass action. For larger $h$, a transition into some trapped motif state occurs in Erdős-Rényi networks. We explain the existence of the transition by employing the notion of the entropy of the motif distribution and describe it in terms of a phenomenological Landau-type theory with a nonzero cubic term. A localization transition should always occur if the entropy function is nonconvex. We conjecture that this phenomenon is the origin of the motifs’ pattern formation in real evolutionary networks.

Figure 1

(a) Possible triads in a nondirected network. (b) Single link permutation: links (12) and (34) are removed, and links (13) and (24) are created. Triad $\{135\}$ goes from type [0] to type [1], triads $\{125,345\}$—from type [2] to type [1], and triad $\{245\}$—from type [2] to type [3]: three new triads of type [1] and one triad of type [3] are created instead of three triads of type [2] and one of type [0], compare (1).

Figure 2

The motif distribution $\varphi (h)=c-c(h=0)$ in ER networks with $p=0.05$ (a) and $p=0.35$ (b), reequilibrated at different $h$. Solid lines—numerical results for networks of sizes $N=80$ (magenta diamonds), 160 (blue triangles), 240 (red circles), and 320 (black squares), dashed line—predictions of the LMA (5).

Figure 3

Comparison of the numeric dependence $\varphi (h)$ for $N=320$ (squares) and the best fitting Landau theory (9) (lines). (a) $p=0.05$, $\chi =p^{-3}(1-p{)}^{-3}=9330$, $b=1.72\times {10}^7$, $c=8.45\times {10}^9$; (b) $p=0.35$, $\chi =p^{-3}(1-p{)}^{-3}=85$, $b=4.46\times {10}^3$, $c=5.7\times {10}^4$.