Fluctuations of motifs and non self-averaging in complex networks. A self- vs non-self-averaging phase transition scenario

Abstract

Complex networks have been mostly characterized from the point of view of the degree distribution of their nodes and a few other motifs (or modules), with a special attention to triangles and cliques. The most exotic phenomena have been observed when the exponent $\gamma$ of the associated power law degree-distribution is sufficiently small. In particular, a zero percolation threshold takes place for $\gamma <3$, and an anomalous critical behavior sets in for $\gamma <5$. In this Letter we prove that in sparse scale-free networks characterized by a cut-off scaling with the sistem size $N$, relative fluctuations are actually never negligible: given a motif $\Gamma$, we analyze the relative fluctuations $R_{\Gamma }$ of the associated density of $\Gamma$, and we show that there exists an interval in $\gamma$, $[{\gamma }_1,{\gamma }_2]$, where $R_{\Gamma }$ does not go to zero in the thermodynamic limit, where ${\gamma }_1\approx k_{\min }$ and ${\gamma }_2\approx 2k_{\max }$, $k_{\min }$ and $k_{\max }$ being the smallest and the largest degree of $\Gamma$, respectively. Remarkably, in $({\gamma }_1,{\gamma }_2)$ $R_{\Gamma }$ diverges, implying the instability of $\Gamma$ to small perturbations.

6 pages, 6 figures

References in corpus (5)

• Power-law distributions in empirical data
• Critical phenomena in complex networks
• The entropy of randomized network ensembles
• All scale-free networks are sparse
• Clustering of random scale-free networks

Cited by in corpus (4)

• Structural Transitions in Dense Networks
• Densification and Structural Transitions in Networks that Grow by Node Copying
• Fluctuations analysis in complex networks modeled by hidden variable models. Necessity of a large cut-off in hidden-variable models
• Statistical mechanics of random geometric graphs: Geometry-induced first order phase transition