ID: 1404.5786

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

April 23, 2014

View on ArXiv

Similar papers 3

Covariance structure behind breaking of ensemble equivalence in random graphs

November 12, 2017

83% Match
Diego Garlaschelli, Frank den Hollander, Andrea Roccaverde
Mathematical Physics
Probability

For a random graph subject to a topological constraint, the microcanonical ensemble requires the constraint to be met by every realisation of the graph (`hard constraint'), while the canonical ensemble requires the constraint to be met only on average (`soft constraint'). It is known that breaking of ensemble equivalence may occur when the size of the graph tends to infinity, signalled by a non-zero specific relative entropy of the two ensembles. In this paper we analyse a fo...

Find SimilarView on arXiv

Principles of statistical mechanics of random networks

April 4, 2002

83% Match
S. N. Dorogovtsev, J. F. F. Mendes, A. N. Samukhin
Statistical Mechanics
Networking and Internet Arch...
Mathematical Physics
Adaptation and Self-Organizi...

We develop a statistical mechanics approach for random networks with uncorrelated vertices. We construct equilibrium statistical ensembles of such networks and obtain their partition functions and main characteristics. We find simple dynamical construction procedures that produce equilibrium uncorrelated random graphs with an arbitrary degree distribution. In particular, we show that in equilibrium uncorrelated networks, fat-tailed degree distributions may exist only starting...

Find SimilarView on arXiv

Entropy of Some Models of Sparse Random Graphs With Vertex-Names

January 2, 2013

83% Match
David J. Aldous, Nathan Ross
Probability

Consider the setting of sparse graphs on N vertices, where the vertices have distinct "names", which are strings of length O(log N) from a fixed finite alphabet. For many natural probability models, the entropy grows as cN log N for some model-dependent rate constant c. The mathematical content of this paper is the (often easy) calculation of c for a variety of models, in particular for various standard random graph models adapted to this setting. Our broader purpose is to pu...

Find SimilarView on arXiv

Generalised hypergeometric ensembles of random graphs: the configuration model as an urn problem

October 15, 2018

83% Match
Giona Casiraghi, Vahan Nanumyan
Probability
Social and Information Netwo...
Data Analysis, Statistics an...
Physics and Society

We introduce a broad class of random graph models: the generalised hypergeometric ensemble (GHypEG). This class enables to solve some long standing problems in random graph theory. First, GHypEG provides an elegant and compact formulation of the well-known configuration model in terms of an urn problem. Second, GHypEG allows to incorporate arbitrary tendencies to connect different vertex pairs. Third, we present the closed-form expressions of the associated probability distri...

Find SimilarView on arXiv

Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution

May 29, 2017

83% Match
der Hoorn Pim van, Gabor Lippner, Dmitri Krioukov
math.PR
cond-mat.stat-mech
cs.SI
math.ST
physics.soc-ph
stat.TH

Even though power-law or close-to-power-law degree distributions are ubiquitously observed in a great variety of large real networks, the mathematically satisfactory treatment of random power-law graphs satisfying basic statistical requirements of realism is still lacking. These requirements are: sparsity, exchangeability, projectivity, and unbiasedness. The last requirement states that entropy of the graph ensemble must be maximized under the degree distribution constraints....

Find SimilarView on arXiv

Entropy-Based Proofs of Combinatorial Results on Bipartite Graphs

June 14, 2021

83% Match
Igal Sason
Information Theory
Combinatorics
Information Theory

This work considers new entropy-based proofs of some known, or otherwise refined, combinatorial bounds for bipartite graphs. These include upper bounds on the number of the independent sets, lower bounds on the minimal number of colors in constrained edge coloring, and lower bounds on the number of walks of a given length in bipartite graphs. The proofs of these combinatorial results rely on basic properties of the Shannon entropy.

Find SimilarView on arXiv

Hidden Variables in Bipartite Networks

April 16, 2011

83% Match
Maksim Kitsak, Dmitri Krioukov
Data Analysis, Statistics an...
Disordered Systems and Neura...
Statistical Mechanics
Social and Information Netwo...
Physics and Society

We introduce and study random bipartite networks with hidden variables. Nodes in these networks are characterized by hidden variables which control the appearance of links between node pairs. We derive analytic expressions for the degree distribution, degree correlations, the distribution of the number of common neighbors, and the bipartite clustering coefficient in these networks. We also establish the relationship between degrees of nodes in original bipartite networks and ...

Find SimilarView on arXiv

Degree sequences of random digraphs and bipartite graphs

February 11, 2013

82% Match
Brendan D. McKay, Fiona Skerman
Combinatorics

We investigate the joint distribution of the vertex degrees in three models of random bipartite graphs. Namely, we can choose each edge with a specified probability, choose a specified number of edges, or specify the vertex degrees in one of the two colour classes. This problem can alternatively be described in terms of the row and sum columns of random binary matrix or the in-degrees and out-degrees of a random digraph, in which case we can optionally forbid loops. It can al...

Find SimilarView on arXiv

Maximum entropy distributions on graphs

January 15, 2013

82% Match
Christopher Hillar, Andre Wibisono
Statistics Theory
Probability
Neurons and Cognition
Statistics Theory

Inspired by applications to theories of coding and communication in networks of nervous tissue, we study maximum entropy distributions on weighted graphs with a given expected degree sequence. These distributions are characterized by independent edge weights parameterized by a shared vector of vertex potentials. Using the general theory of exponential family distributions, we derive the existence and uniqueness of the maximum likelihood estimator (MLE) of the vertex parameter...

Find SimilarView on arXiv

Random Graphs with Hidden Color

March 21, 2003

82% Match
Bo Söderberg
Statistical Mechanics
Disordered Systems and Neura...

We propose and investigate a unifying class of sparse random graph models, based on a hidden coloring of edge-vertex incidences, extending an existing approach, Random graphs with a given degree distribution, in a way that admits a nontrivial correlation structure in the resulting graphs. The approach unifies a number of existing random graph ensembles within a common general formalism, and allows for the analytic calculation of observable graph characteristics. In partic...

Find SimilarView on arXiv