Entropy of microcanonical finite-graph ensembles

Breaking of ensemble equivalence between the microcanonical ensemble and the canonical ensemble may occur for random graphs whose size tends to infinity, and is signaled by a non-zero specific relative entropy of the two ensembles. In [3] and [4] it was shown that breaking occurs when the constraint is put on the degree sequence (configuration model). It is not known what is the effect on the relative entropy when the number of constraints is reduced, i.e., when only part of ...

The entropy of network ensembles characterizes the amount of information encoded in the network structure, and can be used to quantify network complexity, and the relevance of given structural properties observed in real network datasets with respect to a random hypothesis. In many real networks the degrees of individual nodes are not fixed but change in time, while their statistical properties, such as the degree distribution, are preserved. Here we characterize the distribu...

We study the family of network models derived by requiring the expected properties of a graph ensemble to match a given set of measurements of a real-world network, while maximizing the entropy of the ensemble. Models of this type play the same role in the study of networks as is played by the Boltzmann distribution in classical statistical mechanics; they offer the best prediction of network properties subject to the constraints imposed by a given set of observations. We giv...

Entropic measures of complexity are able to quantify the information encoded in complex network structures. Several entropic measures have been proposed in this respect. Here we study the relation between the Shannon entropy and the Von Neumann entropy of networks with a given expected degree sequence. We find in different examples of network topologies that when the degree distribution contains some heterogeneity, an intriguing correlation emerges between the two entropies. ...

The entropy of a hierarchical network topology in an ensemble of sparse random networks with "hidden variables" associated to its nodes, is the log-likelihood that a given network topology is present in the chosen ensemble.We obtain a general formula for this entropy,which has a clear simple interpretation in some simple limiting cases. The results provide new keys with which to solve the general problem of "fitting" a given network with an appropriate ensemble of random netw...

In this work we study the entropy of the Gibbs state corresponding to a graph. The Gibbs state is obtained from the Laplacian, normalized Laplacian or adjacency matrices associated with a graph. We calculated the entropy of the Gibbs state for a few classes of graphs and studied their behavior with changing graph order and temperature. We illustrate our analytical results with numerical simulations for Erd\H{o}s-R\'enyi, Watts-Strogatz, Barab\'asi-Albert and Chung-Lu graph mo...

Using a maximum entropy principle to assign a statistical weight to any graph, we introduce a model of random graphs with arbitrary degree distribution in the framework of standard statistical mechanics. We compute the free energy and the distribution of connected components. We determine the size of the percolation cluster above the percolation threshold. The conditional degree distribution on the percolation cluster is also given. We briefly present the analogous discussion...

Stochastic blockmodels are generative network models where the vertices are separated into discrete groups, and the probability of an edge existing between two vertices is determined solely by their group membership. In this paper, we derive expressions for the entropy of stochastic blockmodel ensembles. We consider several ensemble variants, including the traditional model as well as the newly introduced degree-corrected version [Karrer et al. Phys. Rev. E 83, 016107 (2011)]...

In this paper we consider a random graph on which topological restrictions are imposed, such as constraints on the total number of edges, wedges, and triangles. We work in the dense regime, in which the number of edges per vertex scales proportionally to the number of vertices $n$. Our goal is to compare the micro-canonical ensemble (in which the constraints are satisfied for every realisation of the graph) with the canonical ensemble (in which the constraints are satisfied o...

The first degree-based entropy of a graph is the Shannon entropy of its degree sequence normalized by the degree sum. Its correct interpretation as a measure of uniformity of the degree sequence requires the determination of its extremal values given natural constraints. In this paper, we prove that the graphs with given size that minimize the first degree-based entropy are the colex graphs.