Atomic structures and the statistical mechanics of networks

28 April 2020

We consider random graph models where graphs are generated by connecting not only pairs of nodes by edges but also larger subsets of
nodes by copies of small atomic subgraphs of arbitrary topology. More specifically we consider canonical and microcanonical ensembles
corresponding to constraints placed on the counts and distributions of atomic subgraphs and derive general expressions for the entropy of such
models. We also introduce a procedure that enables the distributions of multiple atomic subgraphs to be combined resulting in more coarse
grained models. As a result 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 (Karrer & Newman PRE 2010, Bollobas et al. RSA 2011), random hypergraphs, bipartite models, stochastic block models, models of multilayer networks and their degree corrected and directed versions. We show that the entropy expressions for all these models can be derived from a single expression that is characterized by the symmetry groups of their atomic subgraphs.