Maximum-entropy random graph model
None
Part of a series on | ||||
Network science | ||||
---|---|---|---|---|
Network types | ||||
Graphs | ||||
|
||||
Models | ||||
|
||||
|
||||
Maximum-entropy random graph models are random graph models used to study complex networks subject to the principle of maximum entropy under a set of structural constraints, [1] which may be global, distributional, or local.
Overview
Any random graph model (at a fixed set of parameter values) results in a
probability distribution
on
graphs
, and those that are maximum
entropy
within the considered class of distributions have the special property of being maximally
unbiased
null models
for network inference
[2]
(e.g.
biological network inference
). Each model defines a family of probability distributions on the set of graphs of size
(for each
for some finite
), parameterized by a collection of constraints on
observables
defined for each graph
(such as fixed expected average
degree
,
degree distribution
of a particular form, or specific
degree sequence
), enforced in the graph distribution alongside entropy maximization by the
method of Lagrange multipliers
. Note that in this context "maximum entropy" refers not to the
entropy of a single graph
, but rather the entropy of the whole probabilistic ensemble of random graphs.
Several commonly studied random network models are in fact maximum entropy, for example the
ER
graphs
and
(which each have one global constraint on the number of edges), as well as the
configuration model
(CM).
[3]
and
soft configuration model
(SCM) (which each have
local constraints, one for each nodewise degree-value). In the two pairs of models mentioned above, an important distinction
[4]
[5]
is in whether the constraint is sharp (i.e. satisfied by every element of the set of size-
graphs with nonzero probability in the ensemble), or soft (i.e. satisfied on average across the whole ensemble). The former (sharp) case corresponds to a
microcanonical ensemble
,
[6]
the condition of maximum entropy yielding all graphs
satisfying
as equiprobable; the latter (soft) case is
canonical
,
[7]
producing an
exponential random graph model
(ERGM).
Model | Constraint type | Constraint variable | Probability distribution |
---|---|---|---|
ER
,
|
Sharp, global |
Total edge-count
|
|
ER
,
|
Soft, global |
Expected total edge-count
|
|
Configuration model | Sharp, local |
Degree of each vertex,
|
|
Soft configuration model | Soft, local |
Expected degree of each vertex,
|
|
Canonical ensemble of graphs (general framework)
Suppose we are building a random graph model consisting of a probability distribution
on the set
of
simple graphs
with
vertices. The
Gibbs entropy
of this ensemble will be given by
We would like the ensemble-averaged values
of observables
(such as average
degree
, average
clustering
, or
average shortest path length
) to be tunable, so we impose
"soft" constraints on the graph distribution:
where
label the constraints. Application of the method of Lagrange multipliers to determine the distribution
that maximizes
while satisfying
, and the normalization condition
results in the following:
[1]
where
is a normalizing constant (the
partition function
) and
are parameters (Lagrange multipliers) coupled to the correspondingly indexed graph observables, which may be tuned to yield graph samples with desired values of those properties, on average; the result is an exponential family and
canonical ensemble
; specifically yielding an
ERGM
.
The Erdős–Rényi model
In the canonical framework above, constraints were imposed on ensemble-averaged quantities
. Although these properties will on average take on values specifiable by appropriate setting of
, each specific instance
may have
, which may be undesirable. Instead, we may impose a much stricter condition: every graph with nonzero probability must satisfy
exactly. Under these "sharp" constraints, the maximum-entropy distribution is determined. We exemplify this with the Erdős–Rényi model
.
The sharp constraint in
is that of a fixed number of
edges
,
[8]
that is
, for all graphs
drawn from the ensemble (instantiated with a probability denoted
). This restricts the sample space from
(all graphs on
vertices) to the subset
. This is in direct analogy to the
microcanonical ensemble
in classical
statistical mechanics
, wherein the system is restricted to a thin manifold in the
phase space
of all states of a particular
energy
value.
Upon restricting our sample space to
, we have no external constraints (besides normalization) to satisfy, and thus we'll select
to maximize
without making use of Lagrange multipliers. It is well known that the entropy-maximizing distribution in the absence of external constraints is the
uniform distribution
over the sample space (see
maximum entropy probability distribution
), from which we obtain:
where the last expression in terms of
binomial coefficients
is the number of ways to place
edges among
possible
edges
, and thus is the
cardinality
of
.
Generalizations
A variety of maximum-entropy ensembles have been studied on generalizations of simple graphs. These include, for example, ensembles of simplicial complexes, [9] and weighted random graphs with a given expected degree sequence [10]
See also
References
- 1 2 Park, Juyong; M.E.J. Newman (2004-05-25). "The statistical mechanics of networks". arXiv : cond-mat/0405566 .
- ↑ van der Hoorn, Pim; Gabor Lippner; Dmitri Krioukov (2017-10-10). "Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution". arXiv : 1705.10261 .
- ↑ Newman, Mark (2010). Networks: An Introduction - Oxford Scholarship . doi : 10.1093/acprof:oso/9780199206650.001.0001 . ISBN 9780199206650 . Archived from the original on 2023-02-04 . Retrieved 2018-09-13 .
- ↑ Garlaschelli, Diego; den Hollander, Frank; Roccaverde, Andrea (2018-07-13). "Covariance Structure Behind Breaking of Ensemble Equivalence in Random Graphs". Journal of Statistical Physics . 173 (3–4): 644–662. arXiv : 1711.04273 . Bibcode : 2018JSP...173..644G . doi : 10.1007/s10955-018-2114-x . ISSN 0022-4715 .
- ↑ Roccaverde, Andrea (August 2018). "Is breaking of ensemble equivalence monotone in the number of constraints?". Indagationes Mathematicae . 30 : 7–25. arXiv : 1807.02791 . doi : 10.1016/j.indag.2018.08.001 . ISSN 0019-3577 .
- ↑ Bianconi, G. (2018-08-21). Multilayer Networks: Structure and Function . Oxford University Press. ISBN 9780198753919 . Archived from the original on 2023-02-04 . Retrieved 2018-09-13 .
- ↑ Anand, K.; Bianconi, G. (2009). "Entropy measures for networks: Toward an information theory of complex topologies". Physical Review E . 80 (4): 045102. arXiv : 0907.1514 . Bibcode : 2009PhRvE..80d5102A . doi : 10.1103/PhysRevE.80.045102 . PMID 19905379 .
- ↑ Erdős, P.; Rényi, A. (1959). "On Random Graphs. I" (PDF) . Publicationes Mathematicae . 6 : 290–297. Archived (PDF) from the original on 2020-08-07 . Retrieved 2018-09-13 .
- ↑ Zuev, Konstantin; Or Eisenberg; Dmitri Krioukov (2015-10-29). "Exponential Random Simplicial Complexes". arXiv : 1502.05032 .
- ↑ Hillar, Christopher; Andre Wibisono (2013-08-26). "Maximum entropy distributions on graphs". arXiv : 1301.3321 .