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

I report on the development of a novel statistical mechanical formalism for the analysis of random graphs with many short loops, and processes on such graphs. The graphs are defined via maximum entropy ensembles, in which both the degrees (via hard constraints) and the adjacency matrix spectrum (via a soft constraint) are prescribed. The sum over graphs can be done analytically, using a replica formalism with complex replica dimensions. All known results for tree-like graphs ...

The quantification of the complexity of networks is, today, a fundamental problem in the physics of complex systems. A possible roadmap to solve the problem is via extending key concepts of information theory to networks. In this paper we propose how to define the Shannon entropy of a network ensemble and how it relates to the Gibbs and von Neumann entropies of network ensembles. The quantities we introduce here will play a crucial role for the formulation of null models of n...

Here we present the entropic dynamics formalism for networks. That is, a framework for the dynamics of graphs meant to represent a network derived from the principle of maximum entropy and the rate of transition is obtained taking into account the natural information geometry of probability distributions. We apply this framework to the Gibbs distribution of random graphs obtained with constraints on the node connectivity. The information geometry for this graph ensemble is ca...

Recent work on the structure of social networks and the internet has focussed attention on graphs with distributions of vertex degree that are significantly different from the Poisson degree distributions that have been widely studied in the past. In this paper we develop in detail the theory of random graphs with arbitrary degree distributions. In addition to simple undirected, unipartite graphs, we examine the properties of directed and bipartite graphs. Among other results...

We provide a novel family of generative block-models for random graphs that naturally incorporates degree distributions: the block-constrained configuration model. Block-constrained configuration models build on the generalised hypergeometric ensemble of random graphs and extend the well-known configuration model by enforcing block-constraints on the edge generation process. The resulting models are analytically tractable and practical to fit even to large networks. These mod...

Sampling random graphs with given properties is a key step in the analysis of networks, as random ensembles represent basic null models required to identify patterns such as communities and motifs. An important requirement is that the sampling process is unbiased and efficient. The main approaches are microcanonical, i.e. they sample graphs that match the enforced constraints exactly. Unfortunately, when applied to strongly heterogeneous networks (like most real-world example...

We introduce a mapping between graphs and pure quantum bipartite states and show that the associated entanglement entropy conveys non-trivial information about the structure of the graph. Our primary goal is to investigate the family of random graphs known as complex networks. In the case of classical random graphs we derive an analytic expression for the averaged entanglement entropy $\bar S$ while for general complex networks we rely on numerics. For large number of nodes $...

The entropy of a graph was first introduced by Rashevsky \cite{Rashevsky} and Trucco \cite{Trucco} to interpret as the structural information content of the graph and serve as a complexity measure. In this paper, we first state a number of definitions of graph entropy measures and generalized graph entropies. Then we survey the known results about them from the following three respects: inequalities and extremal properties on graph entropies, relationships between graph struc...

Let d = (d1, d2, ..., dn) be a vector of non-negative integers with even sum. We prove some basic facts about the structure of a random graph with degree sequence d, including the probability of a given subgraph or induced subgraph. Although there are many results of this kind, they are restricted to the sparse case with only a few exceptions. Our focus is instead on the case where the average degree is approximately a constant fraction of n. Our approach is the multidimensio...

Network science has traditionally focused on pairwise relationships while disregarding many-body interactions. Hypergraphs are promising mathematical objects for the description of the latter ones. Here, we propose null models to analyse hypergraphs that generalise the classical Erd\"os-R\'enyi and Configuration Model by randomising incidence matrices in a constrained fashion. After discussing them, we extend the definition of several network quantities to hypergraphs, derive...