Variational principle for scale-free network motifs

Abstract

For scale-free networks with degrees following a power law with an exponent $\tau \in (2,3)$, the structures of motifs (small subgraphs) are not yet well understood. We introduce a method designed to identify the dominant structure of any given motif as the solution of an optimization problem. The unique optimizer describes the degrees of the vertices that together span the most likely motif, resulting in explicit asymptotic formulas for the motif count and its fluctuations. We then classify all motifs into two categories: motifs with small and large fluctuations.

References in corpus (20)

• Power-law distributions in empirical data
• The diameter of the world wide web
• The large-scale organization of metabolic networks
• Hierarchical Organization in Complex Networks
• Higher-order organization of complex networks
• Universal Behavior of Load Distribution in Scale-free Networks
• Intensity and coherence of motifs in weighted complex networks
• Large-scale topological and dynamical properties of Internet
• The statistical mechanics of networks
• Class of correlated random networks with hidden variables
• A General Formalism for Inhomogeneous Random Graphs
• Epidemic spreading on complex networks with community structures
• Lack of Self-Averaging in Critical Disordered Systems
• Absence of self-averaging and of homogeneity in the large scale galaxy distribution
• Testing Network Structure Using Relations Between Small Subgraph Probabilities
• Clustering Spectrum of scale-free networks
• Beyond clustering: Mean-field dynamics on networks with arbitrary subgraph composition
• Fluctuations analysis in complex networks modeled by hidden variable models. Necessity of a large cut-off in hidden-variable models
• Self-averaging fluctuations in the chaoticity of simple fluids
• Epidemics on contact networks: a general stochastic approach

Cited by in corpus (7)

• A Survey on Subgraph Counting: Concepts, Algorithms and Applications to Network Motifs and Graphlets
• Detecting hyperbolic geometry in networks: why triangles are not enough
• Cliques in geometric inhomogeneous random graph
• Distinguishing power-law uniform random graphs from inhomogeneous random graphs through small subgraphs
• Locating highly connected clusters in large networks with HyperLogLog counters
• Sharpest possible clustering bounds using robust random graph analysis
• Robust subgraph counting with distribution-free random graph analysis