Entropies of tailored random graph ensembles: bipartite graphs, generalised degrees, and node neighbourhoods

For a random graph subject to a topological constraint, the microcanonical ensemble requires the constraint to be met by every realisation of the graph (`hard constraint'), while the canonical ensemble requires the constraint to be met only on average (`soft constraint'). It is known that breaking of ensemble equivalence may occur when the size of the graph tends to infinity, signalled by a non-zero specific relative entropy of the two ensembles. In this paper we analyse a fo...

We develop a statistical mechanics approach for random networks with uncorrelated vertices. We construct equilibrium statistical ensembles of such networks and obtain their partition functions and main characteristics. We find simple dynamical construction procedures that produce equilibrium uncorrelated random graphs with an arbitrary degree distribution. In particular, we show that in equilibrium uncorrelated networks, fat-tailed degree distributions may exist only starting...

Consider the setting of sparse graphs on N vertices, where the vertices have distinct "names", which are strings of length O(log N) from a fixed finite alphabet. For many natural probability models, the entropy grows as cN log N for some model-dependent rate constant c. The mathematical content of this paper is the (often easy) calculation of c for a variety of models, in particular for various standard random graph models adapted to this setting. Our broader purpose is to pu...

We introduce a broad class of random graph models: the generalised hypergeometric ensemble (GHypEG). This class enables to solve some long standing problems in random graph theory. First, GHypEG provides an elegant and compact formulation of the well-known configuration model in terms of an urn problem. Second, GHypEG allows to incorporate arbitrary tendencies to connect different vertex pairs. Third, we present the closed-form expressions of the associated probability distri...

Even though power-law or close-to-power-law degree distributions are ubiquitously observed in a great variety of large real networks, the mathematically satisfactory treatment of random power-law graphs satisfying basic statistical requirements of realism is still lacking. These requirements are: sparsity, exchangeability, projectivity, and unbiasedness. The last requirement states that entropy of the graph ensemble must be maximized under the degree distribution constraints....

This work considers new entropy-based proofs of some known, or otherwise refined, combinatorial bounds for bipartite graphs. These include upper bounds on the number of the independent sets, lower bounds on the minimal number of colors in constrained edge coloring, and lower bounds on the number of walks of a given length in bipartite graphs. The proofs of these combinatorial results rely on basic properties of the Shannon entropy.

We introduce and study random bipartite networks with hidden variables. Nodes in these networks are characterized by hidden variables which control the appearance of links between node pairs. We derive analytic expressions for the degree distribution, degree correlations, the distribution of the number of common neighbors, and the bipartite clustering coefficient in these networks. We also establish the relationship between degrees of nodes in original bipartite networks and ...

We investigate the joint distribution of the vertex degrees in three models of random bipartite graphs. Namely, we can choose each edge with a specified probability, choose a specified number of edges, or specify the vertex degrees in one of the two colour classes. This problem can alternatively be described in terms of the row and sum columns of random binary matrix or the in-degrees and out-degrees of a random digraph, in which case we can optionally forbid loops. It can al...

Inspired by applications to theories of coding and communication in networks of nervous tissue, we study maximum entropy distributions on weighted graphs with a given expected degree sequence. These distributions are characterized by independent edge weights parameterized by a shared vector of vertex potentials. Using the general theory of exponential family distributions, we derive the existence and uniqueness of the maximum likelihood estimator (MLE) of the vertex parameter...

We propose and investigate a unifying class of sparse random graph models, based on a hidden coloring of edge-vertex incidences, extending an existing approach, Random graphs with a given degree distribution, in a way that admits a nontrivial correlation structure in the resulting graphs. The approach unifies a number of existing random graph ensembles within a common general formalism, and allows for the analytic calculation of observable graph characteristics. In partic...