ID: 0908.1759

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

August 12, 2009

View on ArXiv
A. Annibale, A. C. C. Coolen, L. P. Fernandes, F. Fraternali, J. Kleinjung
Condensed Matter
Disordered Systems and Neura...

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.

Similar papers 1

E. S. Roberts, A. C. C. Coolen, T. Schlitt
Quantitative Methods
Disordered Systems and Neura...
Social and Information Netwo...
Physics and Society

We generate new mathematical tools with which to quantify the macroscopic topological structure of large directed networks. This is achieved via a statistical mechanical analysis of constrained maximum entropy ensembles of directed random graphs with prescribed joint distributions for in- and outdegrees and prescribed degree-degree correlation functions. We calculate exact and explicit formulae for the leading orders in the system size of the Shannon entropies and complexitie...

The entropy of randomized network ensembles

August 1, 2007

94% Match
Ginestra Bianconi
Disordered Systems and Neura...
Statistical Mechanics

Randomized network ensembles are the null models of real networks and are extensivelly used to compare a real system to a null hypothesis. In this paper we study network ensembles with the same degree distribution, the same degree-correlations or the same community structure of any given real network. We characterize these randomized network ensembles by their entropy, i.e. the normalized logarithm of the total number of networks which are part of these ensembles. We estima...

Find SimilarView on arXiv

Entropy of random graph ensembles constrained with generalised degrees

September 14, 2013

93% Match
Ekaterina S. Roberts, Anthonius C. C. Coolen
Disordered Systems and Neura...

Generalised degrees provide a natural bridge between local and global topological properties of networks. We define the generalised degree to be the number of neighbours of a node within one and two steps respectively. Tailored random graph ensembles are used to quantify and compare topological properties of networks in a systematic and precise manner, using concepts from information theory. We calculate the Shannon entropy of random graph ensembles constrained with a specifi...

Find SimilarView on arXiv

The entropy of network ensembles

February 20, 2008

92% Match
Ginestra Bianconi
Disordered Systems and Neura...
Statistical Mechanics

In this paper we generalize the concept of random networks to describe networks with non trivial features by a statistical mechanics approach. This framework is able to describe ensembles of undirected, directed as well as weighted networks. These networks might have not trivial community structure or, in the case of networks embedded in a given space, non trivial distance dependence of the link probability. These ensembles are characterized by their entropy which evaluate th...

Find SimilarView on arXiv

Exchangeable Random Networks

July 24, 2007

92% Match
F. Bassetti, M. Cosentino Lagomarsino, S. MandrĂ¡
Probability
Statistics Theory
Statistics Theory

We introduce and study a class of exchangeable random graph ensembles. They can be used as statistical null models for empirical networks, and as a tool for theoretical investigations. We provide general theorems that carachterize the degree distribution of the ensemble graphs, together with some features that are important for applications, such as subgraph distributions and kernel of the adjacency matrix. These results are used to compare to other models of simple and compl...

Find SimilarView on arXiv

The Statistical Physics of Real-World Networks

October 11, 2018

91% Match
Giulio Cimini, Tiziano Squartini, Fabio Saracco, Diego Garlaschelli, ... , Caldarelli Guido
physics.soc-ph
cond-mat.dis-nn
cond-mat.stat-mech
cs.IT
cs.SI
math.IT

In the last 15 years, statistical physics has been a very successful framework to model complex networks. On the theoretical side, this approach has brought novel insights into a variety of physical phenomena, such as self-organisation, scale invariance, emergence of mixed distributions and ensemble non-equivalence, that display unconventional features on heterogeneous networks. At the same time, thanks to their deep connection with information theory, statistical physics and...

Find SimilarView on arXiv

Entropy measures for complex networks: Toward an information theory of complex topologies

July 9, 2009

91% Match
Kartik Anand, Ginestra Bianconi
Disordered Systems and Neura...
Statistical Mechanics
Physics and Society

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...

Find SimilarView on arXiv

A surrogate for networks -- How scale-free is my scale-free network?

June 18, 2013

91% Match
Michael Small, Kevin Judd, Thomas Stemler
Physics and Society
Social and Information Netwo...
Adaptation and Self-Organizi...
Data Analysis, Statistics an...

Complex networks are now being studied in a wide range of disciplines across science and technology. In this paper we propose a method by which one can probe the properties of experimentally obtained network data. Rather than just measuring properties of a network inferred from data, we aim to ask how typical is that network? What properties of the observed network are typical of all such scale free networks, and which are peculiar? To do this we propose a series of methods t...

Find SimilarView on arXiv

Analytical maximum-likelihood method to detect patterns in real networks

March 2, 2011

91% Match
Tiziano Squartini, Diego Garlaschelli
Data Analysis, Statistics an...
Social and Information Netwo...
Physics and Society

In order to detect patterns in real networks, randomized graph ensembles that preserve only part of the topology of an observed network are systematically used as fundamental null models. However, their generation is still problematic. The existing approaches are either computationally demanding and beyond analytic control, or analytically accessible but highly approximate. Here we propose a solution to this long-standing problem by introducing an exact and fast method that a...

Find SimilarView on arXiv

Generalized Hypergeometric Ensembles: Statistical Hypothesis Testing in Complex Networks

July 8, 2016

90% Match
Giona Casiraghi, Vahan Nanumyan, ... , Schweitzer Frank
Physics and Society
Social and Information Netwo...
Combinatorics
Data Analysis, Statistics an...

Statistical ensembles of networks, i.e., probability spaces of all networks that are consistent with given aggregate statistics, have become instrumental in the analysis of complex networks. Their numerical and analytical study provides the foundation for the inference of topological patterns, the definition of network-analytic measures, as well as for model selection and statistical hypothesis testing. Contributing to the foundation of these data analysis techniques, in this...

Find SimilarView on arXiv