Subgraphs in random networks

Abstract

Understanding the subgraph distribution in random networks is important for modelling complex systems. In classic Erdos networks, which exhibit a Poissonian degree distribution, the number of appearances of a subgraph G with n nodes and g edges scales with network size as \mean{G} ~ N^{n-g}. However, many natural networks have a non-Poissonian degree distribution. Here we present approximate equations for the average number of subgraphs in an ensemble of random sparse directed networks, characterized by an arbitrary degree sequence. We find new scaling rules for the commonly occurring case of directed scale-free networks, in which the outgoing degree distribution scales as P(k) ~ k^{-γ}. Considering the power exponent of the degree distribution, γ, as a control parameter, we show that random networks exhibit transitions between three regimes. In each regime the subgraph number of appearances follows a different scaling law, \mean{G} ~ N^α, where α=n-g+s-1 for γ<2, α=n-g+s+1-γfor 2<γ<γ_c, and α=n-g for γ>γ_c, s is the maximal outdegree in the subgraph, and γ_c=s+1. We find that certain subgraphs appear much more frequently than in Erdos networks. These results are in very good agreement with numerical simulations. This has implications for detecting network motifs, subgraphs that occur in natural networks significantly more than in their randomized counterparts.

8 pages, 5 figures

References in corpus (23)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Assortative mixing in networks
• Random graphs with arbitrary degree distributions and their applications
• Evolution of networks
• Classes of behavior of small-world networks
• Specificity and stability in topology of protein networks
• Resilience of the Internet to random breakdowns
• Hierarchical Organization in Complex Networks
• How Popular is Your Paper? An Empirical Study of the Citation Distribution
• Scaling and percolation in the small-world network model
• Bose-Einstein condensation in complex networks
• Pattern Detection in Complex Networks: Correlation Profile of the Internet
• Curvature of Co-Links Uncovers Hidden Thematic Layers in the World Wide Web
• Degree Distributions of Growing Networks
• Percolation Critical Exponents in Scale-Free Networks
• Random graphs as models of networks
• Statistical ensemble of scale-free random graphs
• Correlated random networks
• Number of loops of size h in growing scale-free networks
• Mesoscopics and fluctuations in networks
• Modern architecture of random graphs: Constructions and correlations
• Defining statistical ensembles of random graphs

Cited by in corpus (43)

• Community detection algorithms: a comparative analysis
• Structural Properties of the Caenorhabditis elegans Neuronal Network
• Classes of complex networks defined by role-to-role connectivity profiles
• The topological relationship between the large-scale attributes and local interaction patterns of complex networks
• Complex Networks as Hypergraphs
• On the uniform generation of random graphs with prescribed degree sequences
• Local graph alignment and motif search in biological networks
• Topological Generalizations of network motifs
• The role of mentorship in protege performance
• Potential Theory for Directed Networks
• Coarse-Graining and Self-Dissimilarity of Complex Networks
• Loops of any size and Hamilton cycles in random scale-free networks
• Topology comparison of Twitter diffusion networks effectively reveals misleading information
• Kinetic Theory of Random Graphs: from Paths to Cycles
• Subgraphs and network motifs in geometric networks
• Fitness for Synchronization of Network Motifs
• Loops structure of the Internet at the Autonomous System Level
• Constructing and sampling directed graphs with given degree sequences
• Statistics of Cycles: How Loopy is your Network?
• Self-organization of feedforward structure and entrainment in excitatory neural networks with spike-timing-dependent plasticity
• Subgraph Ensembles and Motif Discovery Using a New Heuristic for Graph Isomorphism
• Spectral Analysis of Protein-Protein Interactions in Drosophila melanogaster
• Perturbing General Uncorrelated Networks
• Empirical study on clique-degree distribution of networks
• Structure of n-clique networks embedded in a complex network
• Network Motifs in Object-Oriented Software Systems
• Link and subgraph likelihoods in random undirected networks with fixed and partially fixed degree sequence
• Rigorous results on the threshold network model
• K-Scaffold subgraphs of Complex networks
• Random graph model with power-law distributed triangle subgraphs
• Subgraphs and motifs in a dynamic airline network
• Motif Dynamics in Signed Directional Complex Networks
• Higher-order distributions and nongrowing complex networks without multiple connections
• Motif based hierarchical random graphs: structural properties and critical points of an Ising model
• A comparative evolutionary study of transcription networks
• Parallel Global Edge Switching for the Uniform Sampling of Simple Graphs with Prescribed Degrees
• Random Networks Tossing Biased Coins
• Degree switching and partitioning for enumerating graphs to arbitrary orders of accuracy
• Sharpest possible clustering bounds using robust random graph analysis
• Directionality of contact networks suppresses selection pressure in evolutionary dynamics
• Hierarchical Random Graphs Based on Motifs
• Robust subgraph counting with distribution-free random graph analysis
• Toy Models and Statistical Mechanics of Subgraphs and Motifs of Genetic and Protein Networks