Free-energy density functional for Strauss's model of transitive networks

Ensemble models of graphs are one of the most important theoretical tools to study complex networks. Among them, exponential random graphs (ERGs) have proven to be very useful in the analysis of social networks. In this paper we develop a technique, borrowed from the statistical mechanics of lattice gases, to solve Strauss's model of transitive networks. This model was introduced long ago as an ERG ensemble for networks with high clustering and exhibits a first-order phase transition above a critical value of the triangle interaction parameter where two different kinds of networks with different densities of links (or, alternatively, different clustering) coexist. Compared to previous mean-field approaches, our method describes accurately even small networks and can be extended beyond Strauss's classical model-e.g., to networks with different types of nodes. This allows us to tackle, for instance, models with node homophily. We provide results for the latter and show that they accurately reproduce the outcome of Monte Carlo simulations.

Automated summary

Ensemble models of graphs, especially exponential random graphs (ERGs), are important tools in studying complex networks, particularly in the analysis of social networks. This paper presents a technique borrowed from the statistical mechanics of lattice gases to solve Strauss's model of transitive networks. The method accurately describes even small networks and can be extended to networks with different types of nodes.