Atomic subgraphs and the statistical mechanics of networks

Abstract

We develop random graph models where graphs are generated by connecting not only pairs of vertices by edges but also larger subsets of vertices by copies of small atomic subgraphs of arbitrary topology. This allows the for the generation of graphs with extensive numbers of triangles and other network motifs commonly observed in many real world networks. More specifically we focus on maximum entropy ensembles under constraints placed on the counts and distributions of atomic subgraphs and derive general expressions for the entropy of such models. We also present a procedure for combining distributions of multiple atomic subgraphs that enables the construction of models with fewer parameters. Expanding the model to include atoms with edge and vertex labels we obtain a general class of models that can be parametrized in terms of basic building blocks and their distributions that includes many widely used models as special cases. These models include random graphs with arbitrary distributions of subgraphs, random hypergraphs, bipartite models, stochastic block models, models of multilayer networks and their degree corrected and directed versions. We show that the entropy for all these models can be derived from a single expression that is characterized by the symmetry groups of atomic subgraphs.

arXiv comment15 pages, 2 figures

References in corpus (30)

• Random graphs with arbitrary degree distributions and their applications
• Stochastic blockmodels and community structure in networks
• Link communities reveal multiscale complexity in networks
• Networks beyond pairwise interactions: structure and dynamics
• Higher-order organization of complex networks
• The statistical mechanics of networks
• Line Graphs, Link Partitions and Overlapping Communities
• The phase transition in inhomogeneous random graphs
• Random graphs with clustering
• The Statistical Physics of Real-World Networks
• Statistical Mechanics of Multiplex Ensembles: Entropy and Overlap
• The entropy of network ensembles
• Random hypergraphs and their applications
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Parsimonious module inference in large networks
• Estimating and understanding exponential random graph models
• Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Random graphs containing arbitrary distributions of subgraphs
• Multilayer motif analysis of brain networks
• Inferring the mesoscale structure of layered, edge-valued and time-varying networks
• Network reconstruction and community detection from dynamics
• Entropy of stochastic blockmodel ensembles
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Multilayer stochastic block models reveal the multilayer structure of complex networks
• Reconstructing networks with unknown and heterogeneous errors
• Clustering via Hypergraph Modularity
• Spectra of networks containing short loops
• Introduction to papers on the modeling and analysis of network data
• Sparse random graphs with clustering

Cited by in corpus (5)

• Disentangling homophily, community structure and triadic closure in networks
• Entropy of labeled versus unlabeled networks
• Entropy-based models to randomize real-world hypergraphs
• Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes
• Compression-based inference of network motif sets