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

2009/08/13 by A Annibale, A. Annibale, A C C Coolen +7 · 2 citations
Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #Correlation #Degree (music) #Degree distribution #Graph #Graph theory and applications #Network topology #Null model #Random graph #Statistical Mechanics and Entropy #cond-mat.dis-nn

paper · pdf · doi:10.1088/1751-8113/42/48/485001

25 pages, 3 figures

arxiv created 2009/08/13 · openalex publication_date 2009/11/11 · arxiv updated 2015/05/13 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05

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.

Citations

• Detection of topological patterns in complex networks: correlation profile of the internet
• Dynamical and Correlation Properties of the Internet
• Entropies of complex networks with hierarchically constrained topologies
• Emergence of scaling in random networks
• The Binary Protein Interactome of Treponema pallidum – The Syphilis Spirochete
• Sequential Monte Carlo Methods for Statistical Analysis of Tables
• Assortative Mixing in Networks
• Functional organization of the yeast proteome by systematic analysis of protein complexes
• Spin models on random graphs with controlled topologies beyond degree constraints
• A Human Protein-Protein Interaction Network: A Resource for Annotating the Proteome
• Statistical mechanics of complex networks

Cited by

• Reconstructing Networks
• Analytic solution of the two-star model with correlated degrees