Tailored graph ensembles as proxies or null models for real networks I: tools for quantifying structure

Abstract

We study the tailoring of structured random graph ensembles to real networks, with the objective of generating precise and practical mathematical tools for quantifying and comparing network topologies macroscopically, beyond the level of degree statistics. Our family of ensembles can produce graphs with any prescribed degree distribution and any degree-degree correlation function, its control parameters can be calculated fully analytically, and as a result we can calculate (asymptotically) formulae for entropies and complexities, and for information-theoretic distances between networks, expressed directly and explicitly in terms of their measured degree distribution and degree correlations.

25 pages, 3 figures

References in corpus (9)

• Generation of uncorrelated random scale-free networks
• Mixture models and exploratory analysis in networks
• The entropy of network ensembles
• The entropy of randomized network ensembles
• Tuning clustering in random networks with arbitrary degree distributions
• Entropies of complex networks with hierarchically constrained topologies
• Constrained Markovian dynamics of random graphs
• Spin models on random graphs with controlled topologies beyond degree constraints
• Link and subgraph likelihoods in random undirected networks with fixed and partially fixed degree sequence

Cited by in corpus (27)

• The Statistical Physics of Real-World Networks
• Statistical Mechanics of Multiplex Ensembles: Entropy and Overlap
• Quantifying randomness in real networks
• The Shannon and the Von Neumann entropy of random networks with heterogeneous expected degree
• Evolving networks in the human epileptic brain
• Reconstructing networks
• Correlations between weights and overlap in ensembles of weighted multiplex networks
• Linear stability analysis for large dynamical systems on directed random graphs
• Statistical Mechanics of Multi-Edge Networks
• Duality between equilibrium and growing networks
• Entropy rate of non-equilibrium growing networks
• Network resilience against intelligent attacks constrained by degree dependent node removal cost
• Analysis of the convergence of the degree distribution of contracting random networks towards a Poisson distribution using the relative entropy
• Tailored graph ensembles as proxies or null models for real networks II: results on directed graphs
• Convergence towards an Erd{\H o}s-Rényi graph structure in network contraction processes
• The role of adjacency matrix degeneration in maximum entropy weighted network models
• Replica methods for loopy sparse random graphs
• The structure of networks that evolve under a combination of growth, via node addition and random attachment, and contraction, via random node deletion
• Maximal modularity and the optimal size of parliaments
• The distribution of first hitting times of random walks on directed Erdős-Rényi networks
• The configuration multi-edge model: Assessing the effect of fixing node strengths on weighted network magnitudes
• Analytic solution of the two-star model with correlated degrees
• The Fate of Articulation Points and Bredges in Percolation
• Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes
• Generating random networks that consist of a single connected component with a given degree distribution
• Ensemble inequivalence and phase transitions in unlabeled networks
• Vaccination with partial transmission and social distancing on contact networks