arXiv:1701.08420v2 [math.ST] 21 Nov 2017

Random Networks, Graphical Models,
and Exchangeability
Steffen Lauritzen∗
University of Copenhagen

Alessandro Rinaldo
Carnegie Mellon University

Kayvan Sadeghi
University of Cambridge
November 22, 2017

Abstract
We study conditional independence relationships for random networks and their
interplay with exchangeability. We show that, for finitely exchangeable network
models, the empirical subgraph densities are maximum likelihood estimates of their
theoretical counterparts. We then characterize all possible Markov structures for
finitely exchangeable random graphs, thereby identifying a new class of Markov network models corresponding to bidirected Kneser graphs. In particular, we demonstrate that the fundamental property of dissociatedness corresponds to a Markov
property for exchangeable networks described by bidirected line graphs. Finally
we study those exchangeable models that are also summarized in the sense that
the probability of a network only depends on the degree distribution, and identify
a class of models that is dual to the Markov graphs of Frank and Strauss (1986).
Particular emphasis is placed on studying consistency properties of network models
under the process of forming subnetworks and we show that the only consistent
systems of Markov properties correspond to the empty graph, the bidirected line
graph of the complete graph, and the complete graph.
Keywords: bidirected Markov property, de Finetti’s theorem, exchangeable arrays,
exponential random graph model, graph limit, graphon, Kneser graph, marginal
beta model, Möbius parametrization, Petersen graph.
∗
Steffen Lauritzen, Department of Mathematical Sciences, University of Copenhagen, Universitetsparken 5, 2100, Copenhagen, Denmark. email: lauritzen@math.ku.dk

1

1

Introduction

Over the last decades, the collection and rapid diffusion of network data originating
from a wide spectrum of scientific areas have created the need for new statistical theories and methodologies for modeling and analyzing large random graphs. There now
exists a very large and rapidly growing body of literature on network analysis: see, for
example, Kolaczyk (2009), Newman (2010), and references therein. Since the seminal
contributions of Frank and Strauss (1986) and Holland and Leinhardt (1981), the field of
statistical network modeling has advanced significantly and researchers have now gained
a much broader understanding of the properties of network data and the many open
challenges associated to network modeling.
A common feature shared by many network models is that of invariance to the relabeling of the network units, or (finite) exchangeability, whereby isomorphic graphs have
the same probabilities, and are therefore regarded as statistically equivalent. Exchangeability is a basic form of probabilistic invariance, but also a natural and convenient simplifying assumption to impose when formalizing statistical models for random graphs.
Examples of popular network models which rely on exchangeability include many exponential random graph models, the stochastic block model, graphon-based models, latent
space models, to name a few.
In the probability literature, exchangeability of infinite binary arrays — which encompasses networks — is very well understood: see for example Aldous (1981, 1985);
Lauritzen (2003, 2008); and Kallenberg (2005). Of particular relevance here is the work
of Diaconis and Janson (2008) (but see also Orbantz and Roy, 2015), which details the
connections between exchangeability of random graphs and the notion of graph limits
developed in Lovász and Szegedy (2006). While the existing results provide a canonical, analytic representation of infinite exchangeable networks (see later in Section 2),
they appear to be too implicit for statistical modeling purposes. Indeed, the properties implied by such representation do not directly yield simple parametric statistical
models for finite networks. Furthermore, while an exchangeable probability distribution for an infinite networks by construction induce consistent families of exchangeable
distributions for all its finite subnetworks, there is no guarantee that an exchangeable
distribution for networks of a given size may be extendable to a probability distribution
for larger (possibly infinite) networks, or that the induced distributions share the similar
properties. Thus, a priori any statistical model for finite exchangeable networks that
does not conform to the analytic representation of infinite exchangeable networks need
not be compatible in any meaningful way with models of the same type over networks
of different sizes. These issues are of great significance, as they render very difficult
to determine the extent to which statistical inference based on a subnetwork applies
to a larger network, as argued in Crane and Dempsey (2015), and Shalizi and Rinaldo
(2013).
2

The main goal of our article is to reveal and point out similarities and connections
between seemingly unrelated concepts from different parts of the literature — in particular graphical models, network models, and notions of exchangeability — and our
analysis is attempting to enhance understanding of the models and their properties.
We rely on the theory of exponential families and, especially, of graphical models
(Lauritzen, 1996) in order to categorize Markov properties implied by the assumption
of exchangeability, and the statistical models that can be derived from it. The idea
of modeling networks as Markov random fields on binary variables is not new: it was
originally suggested by Frank and Strauss (1986), who argue that a particular class of
exponential random graph models (to be discussed below in Section 4) is able to capture
what the authors, somewhat arbitrarily, posit as a natural form of dependence structure
for networks, as well as the symmetries implied by exchangeability. In contrast, our
analysis of the Markov properties of exchangeable network models is both principled,
as it only relies on the assumption of exchangeability, and exhaustive, as it produces a
complete list of all Markov properties expressed by exchangeable network models. We
make the following specific contributions:
• We describe an exponential family representation for exchangeable network models
where the sufficient statistics are given by all subgraph counts. The subgraph
frequencies are maximum likelihood estimators of the corresponding mean value
parameters, which are the marginal probabilities of all subgraphs.
• We study the Markov properties of finitely exchangeable network models, and show
that such models are compatible only with four types of non-trivial conditional
independence structures.
• We demonstrate that statistical models for finite networks induced by extremal
exchangeable distributions on an infinite network are Markov with respect to a
distinguished bidirected graphical model for marginal independence.
• Finally, we propose a novel class of models for exchangeable networks that are
also summarized, in the sense that their properties only depend on the degree
distribution of the observed network.
We should emphasize that the scope of this paper has been strictly limited to the study
of full exchangeablity and Markov structures in the sense used for standard graphical
models and, as we show, the assumption of full exchangeabiliy, extendibility, and Markov
properties in this sense is very restrictive.
There are important types of Markov properties for random networks that we have
not considered in this paper, notably that of partial conditional independence (Snijders
et al., 2006), also used in Hunter et al. (2008). This concept allows the conditional
independence properties of specific ties in a network to depend on the configuration of
3

the remaining network. This type of Markov property is common in the analysis of
spatial point processes, where it is referred to as data dependent Markov neighbourhoods
(Baddeley and Møller, 1989); indeed, a random network can be considered as a point
process on the space of possible ties. Also in the literature on Bayesian networks and
graphical models, an analogous Markov theory has evolved and here the term contextspecific independence is often used, see e.g. Boutilier et al. (1996) or Nyman et al. (2014)
for a recent discussion.
Similarly, it is of interest but outside the scope of the present paper to discuss other
variants of exchangeability, where we in particular mention partial exchangeability or
block exchangeability as used in Schweinberger and Handcock (2015) or models derived
from exchangeable measures, as in Caron and Fox (2017).
The structure of our paper is as follows. In Section 2 we develop the necessary terminology and detail the concepts of exchangeable arrays, random networks, bidirected
Markov properties, and important parametrizations of the models. In Section 3 we
provide parametrizations for exchangeable networks and their maximum likelihood estimation. In Section 4 we investigate the consequences of exchangeability in its interplay
with associated Markov properties. In Section 5 we study the consequences of adding
the restrictions of summarizedness, and in Section 6 we study consistency properties
under subsampling of various systems of network models.

2

Preliminaries

In this section we gather some background material on graph-theoretic concepts, parametrizations of distributions of binary arrays and graphical modeling.

2.1

Graph-theoretic concepts

Following West (2001), a labeled graph is determined by an ordered pair G = (V, E)
consisting of a vertex set V , an edge set E, and a relation that with each edge associates
two vertices, called its endpoints. When vertices u and v are the endpoints of an edge,
these are adjacent and we write u ∼ v; we denote the corresponding edge as uv.
In this paper, we will restrict to simple graphs, i.e. graphs without loops (the endpoints of each edge are distinct) or multiple edges (each pair of vertices are the endpoints
of at most one edge); simple graphs are determined by the pair G = (V, E) alone. We
will distinguish three types of edge, denoted by arrows, arcs (solid lines with two-headed
arrows) and lines (solid lines). Arrows can be represented by ordered pairs of vertices,
while arcs and lines by 2-subsets of the vertex set. The graphs in the present paper only
contain one of these types, and are called, respectively, directed, bidirected, or undirected.
The labeled graphs F = (VF , EF ) and G = (VG , EG ) are considered equal if and only
if (VF , EF ) = (VG , EG ). We omit the term labeled when the context prevents ambiguity.
4

A subgraph of a graph G = (VG , EG ) is a graph F = (VF , EF ) such that VF ⊆ VG
and EF ⊆ EG and the assignment of endpoints to edges in F is the same as in G. We
will write F ⊂ G to signify that F is a subgraph of G. For a graph G = (V, E), any
non-empty subset A of the vertices generates the subgraph G(A) consisting of all and
only vertices in A and edges between two vertices in A, called the subgraph induced by
A. Similarly, a subset B ⊆ E of edges induces a subgraph that contains the edges in F
and all and only vertices that are endpoints of edges in B. We note that edge induced
subgraphs have no isolated vertices.
A complete graph is a graph where all nodes are adjacent, and a k-star is a graph
where one node (called the hub) is adjacent to all other nodes and there is no other edge
in the graph. The line graph L(G) of a graph G = (V, E) is the intersection graph of the
edge set E, i.e. its vertex set is E and e1 ∼ e2 if and only if e1 and e2 have a common
endpoint (West, 2001, p. 168). We will in particular be interested in the line graph of
the complete graph, which we will refer to as the incidence graph.

2.2

Homomorphism densities

We will rely on the notion of subgraph homomorphism density, a graph-theoretic concept
that is central to the theory of graph convergence (see, e.g., Lovász, 2012).
A map φ : VF → VG between the vertex sets of two simple graphs F = (VF , EF )
and G = (VG , EG ) is a homomorphism if it preserves edges, i.e. if uv in EF implies
φ(u)φ(v) ∈ EG . A homomorphism φ is an isomorphism if it is a bijection and its inverse
is a homomorphism, i.e. φ also preserves non-edges. If there is an isomorphism between
F and G, the graphs are isomorphic, and we write F ∼
= G. An isomorphism can also be
thought of as a relabelling of the vertex set. The isomorphism relation is an equivalence
relation among graphs with the same vertex set. Accordingly, for a graph G = (V, E)
we may identify the corresponding equivalence class as an unlabeled graph with |V |
vertices. An isomorphism φ between the graphs G and G is an automorphism. Then
aut(G) denotes the size of the automorphism group , i.e. the group of automorphisms of
G.
Following Lovász (2012, Ch. 5.2) and assuming that |VF | ≤ |VG |, we let inj(F, G)
denote the number of injective graph homomorphisms between F and G. Note that if
G is a complete graph (i.e. all the vertices are adjacent), all maps are homomorphisms,
and inj(F, G) = (|VG |)|VF | = |VG |!/(|VG |−|VF |)!. Furthermore, we have that inj(G, G) =
aut(G). The injective homomorphism density of F in G is defined to be
tinj (F, G) =

inj(F, G)
,
(|VG |)|VF |

the proportion of all injective mappings from VF into VG that are homomorphisms. It is
immediate from the above definition that homomorphism densities are invariant under
5

isomorphisms, in the sense that tinj (F, G) = tinj (F 0 , G0 ), for any pairs F ∼
= F 0 and G ∼
=
0
G . Thus, density homomorphisms are also well defined over unlabeled graphs. Indeed,
the injective homomorphism density tinj (F, G) can be interpreted as the probability that
F is realized as a random subgraph of G (see, e.g. Diaconis and Janson, 2008).
Finally, we will be interested in the number sub(F, G) of (not necessarily induced)
subgraphs of G that are isomorphic to F . This is given as
sub(F, G) = inj(F, G)/inj(F, F ) = inj(F, G)/aut(F ).

(1)

Clearly, also sub(F, G) remains unchanged if F and G are replaced by isomorphic graphs
F 0 and G0 so that sub(·, ·) is well defined over unlabeled graphs.

2.3

The Möbius parametrization for binary arrays

As explained later in detail, network modeling can be considered equivalent to modeling
the joint distribution of a collection of binary random variables. For this purpose we
will find it convenient to rely on a particular parametrization of such distributions that
is based on the Möbius transform (see, e.g. Lauritzen, 1996, Appendix A3) and that
therefore, following Drton and Richardson (2008), we call the Möbius parametrization.
Let V be a finite set indexing a collection {Xv , v ∈ V } of binary random variables
taking value in {0, 1}V and for a non-empty subset B of V let XB = (Xv , v ∈ B).
The Möbius parametrization arises from taking the Möbius transform of the vector of
joint probabilities of each point in {0, 1}V . This transformation, which is linear and
invertible, in turns yields a vector of marginal, as opposed to joint, probabilities. In
detail, let B denotes the set of all subsets of V and, for each non-empty B ∈ B, set
zB = P(XB = 1B ), where 1B is the |B|-dimensional vector of all 1’s. Further, set
z∅ = 1. Then, using Möbius inversion, we have that, for each H ∈ B,
X
P(XH = 1H , XH c = 0H c ) =
(−1)|B\H| zB ,
(2)
B∈B:H⊆B

where H c = V \ H. Similarly, for each B ∈ B,
X
zB = P(XB = 1B ) =
P(XH = 1H , XH c = 0H c ).
H∈B:B⊆H

The marginal probabilities {zB , B ∈ B} are called the Möbius parameters of the distribution of XV . The above formulae show that there is a one-to-one and linear relation
between joint probabilities and their Möbius parameters and that the only restriction
on the set of feasible Möbius parameters is that all expressions of the form (2) should
be non-negative, and z∅ = 1.
6

We can represent the set of all strictly positive probabilities on {0, 1}V as an exponential family with canonical sufficient statistic given by
x ∈ {0, 1}V 7→ s(x) ∈ {0, 1}|B|−1 ,
where s(x) = (sB (x), B ∈ B \ ∅), with
sB (x) =

Y

xb ,

B ∈ B;

b∈B

see, for instance, Frank and Strauss (1986). The exponential family on {0, 1}V generated
by these sufficient statistics consists of all probability distributions of the form


 X

P(X = x) = Pν (x) = exp
νB sB (x) − ψ(ν) , x ∈ {0, 1}V ,
(3)


B∈B\∅

for any choice of canonical parameters ν = (νB , B ∈ B\∅) ∈ RB\∅ , and where ψ(ν) is the
log-partition function, ensuring that probabilities add to unity. The above exponential
family is minimal, full and regular, and the mean value parameters (Barndorff-Nielsen,
1978) for this representation are precisely the Möbius parameters corresponding to nonempty subsets of V :
E{sB (X)} = zB , B ∈ B \ ∅.

2.4

Undirected and bidirected graphical models

Graphical models (see, e.g. Lauritzen, 1996) are statistical models expressing conditional
independence clauses among a collection of random variables XV = (Xv , v ∈ V ) indexed
by a finite set V . A graphical model is determined by a graph G = (V, E) over the
indexing set V , and the edge set E (which may include edges of undirected, directed
or bidirected type) encodes conditional independence relations among the variables, or
Markov properties. A joint probability distribution P for XV is Markov with respect to
G if it satisfies the Markov properties expressed by G.
For non-empty subsets A and B of V and a (possibly empty) subset S of V , we use the
notation A⊥
⊥ B | S as shorthand for the conditional independence relation XA ⊥
⊥ XB | XS ,
thus identifying random variables with their labels. When S = ∅ the independence
relation is intended as marginal independence.
For an undirected graph G — where all edges are undirected — the (global) Markov
property expresses that A⊥
⊥ B | S when every path between A and B has a vertex in S
or, in other words, S separates A from B in G.
We shall be specifically interested in graphical models given by a bidirected graph
G where all edges are bidirected. For such graphs the (global) Markov property (Cox
7

and Wermuth, 1993; Kauermann, 1996; Richardson and Spirtes, 2002; Richardson, 2003)
expresses that
A⊥
⊥ B | S when every path between A and B has a vertex outside S ∪ A ∪ B, i.e.
V \ (A ∪ B ∪ S) separates A from B. Note the obvious duality between this and the
Markov property for undirected graphs.
For example, in the undirected graph of Figure 1(a), the global Markov property
implies that {i, l}⊥
⊥ k | j , whereas in the bidirected graph of Figure 1(b), the global
Markov property implies that {i, l}⊥
⊥ k. Notice that, for simplicity, we write k and j
instead of {k} and {j} as these are single elements.
l
i

j

l
i

k

(a)

j

k

(b)

Figure 1: (a) An undirected dependence graph. (b) a bidirected dependence graph.
For a system of random variables X we define the dependence skeleton of X, denoted
by sk(X) to be the undirected graph with vertex set V such that vertices u and v are
not adjacent if and only if there is some subset S of V so that u ⊥⊥ v | S. Thus, if X is
Markov with respect to an undirected graph G — such as the case considered by Frank
and Strauss (1986), who chose S to be the set of remaining variables — sk(X) would
be a subgraph of G; whereas if X is Markov with respect to a bidirected graph, we may
choose S = ∅ and the corresponding skeleton will be a subgraph of the graph obtained
by replacing all arcs with lines.
Bidirected graphical models for binary variables For the bidirected case, the exponential representation does not simplify. However, in the Möbius parametrization the
bidirected Markov property takes a particular simple form. Indeed Drton and Richardson (2008) showed that a distribution P is Markov with respect to the bidirected graph
G = (V, E) if and only if for any B ⊂ V that is disconnected in G, the corresponding
Möbius parameter satisfies
zB = zC1 · · · zCk ,
(4)
where C1 , . . . , Ck partitions B into inclusion maximal connected sets (with respect to
G). Thus, if we let C = C(G) be the set of all non-empty connected subsets of V
(with respect to G), the bidirected binary graphical model with graph G is completely,
injectively, and smoothly parametrized by the Möbius parameters (zC , C ∈ C). More

8

precisely we have that
X

P(XH = 1H , XH c = 0H c ) =

(−1)|B\H|

B∈B:H⊆B

Y

zC ,

(5)

C∈CB

where CB denotes the collection of inclusion maximal connected subsets of B. Further,
the Möbius parameters vary freely save for the restrictions that z∅ = 1 and the righthand expressions in (2) and (5) must be non-negative for all choices of E ⊆ V . For
example, for the bidirected graph of Figure 2 we have that
P(X1 = 1, X2 = 0, X3 = 0) = z1 − z12 − z1 z3 + z123 ,
1

2

P(X1 = 1, X3 = 1) = z1 z3 .

3

Figure 2: A dependence graph with vertex set {1, 2, 3}.
Drton and Richardson (2008) further show that the family of positive bidirected
Markov distributions becomes a curved exponential family due to the restriction (4)
which is non-linear in the canonical parameters νB and log-linear in the mean value
parameters zB (Roverato et al., 2013). Finally, the dimension of the corresponding
model is the cardinality of C, the number of connected induced subgraphs of G.

3
3.1

Network models and exchangeability
Some terminology

Given a finite or countably infinite node set N — representing individuals or actors in
a given population of interest — we define a random network over N to be a collection
X = (Xd , d ∈ D(N )) of binary random variables taking values 0 and 1 indexed by a
set D(N ) of dyads. Throughout the paper we take D(N ) to be the set of all unordered
pairs ij of nodes in N , and nodes i and j are said to have a tie if the random variable
Xij takes the value 1, and no tie otherwise. Thus, a network is a random variable taking
N
value in {0, 1}( 2 ) and can therefore be seen as a random simple, undirected, labeled
graph with node set N , whereby the ties form the random edges of the graphs. We will
write GN for the set of all simple, labeled undirected graphs on N .
We use the terms network, node, and tie rather than (random) graph, vertex, and
(random) edge to differentiate from the terminology used in the graphical model sense.
Indeed, as we shall discuss graphical models for networks, we will also consider each
dyad d as a vertex in a graph G = (D, E) representing the dependence structure of the
random variables associated with the dyads.
9

3.2

Exponential random graph models

Exponential random graph models (Frank, 1991; Wasserman and Pattison, 1996), or
ERGMs in short, are among the most important and popular statistical models for
network data and, as we will see, the set of exchangeable distributions form an ERGM.
ERGMs are exponential families of distributions (Barndorff-Nielsen, 1978) on GN
whereby the probability of observing a network x ∈ GN can be expressed as
Pθ (x) = exp

m
nX

o
sl (x)θl − ψ(θ) ,

θ ∈ Θ ⊆ Rm ,

(6)

l=1

where s(x) = (s1 (x) . . . , sm (x)) ∈ Rm are canonical sufficient statistics which capture
some important feature of x, θ ∈ Rm is a point in the canonical parameter space Θ,
and ψ : Θ → [0, ∞) is the log-partition function; in (6) we have thus chosen counting
measure as the base measure of the representation.
The choice of the canonical sufficient statistics and any restriction imposed on Θ
will determine the properties of the corresponding ERGM. The simplest ERGM is the
Erdös–Rényi model (Erdös and Rényi, 1960), where there is only one parameter θ, and
the canonical sufficient statistic is the number of ties in x. This is equivalent to ties
occurring independently with probability p and θ = log{p/(1 − p)}.
Beta models are also ERGMs and they can be considered a generalization of the
Erdös-Rényi model: in these models it is also assumed that ties occur independently;
the probability pij of a tie between nodes i and j is given as:
pij = P(Xij = 1) =

eβi +βj
, ∀ij ∈ D,
1 + eβi +βj

(7)

where (βi , i ∈ N ) can be interpreted as parameters that determine the propensity of
node i to have edges. The probability of a network x ∈ GN is thus
(
)
Y xij
Y e(βi +βj )xij
X
Pβ (x) =
pij (1 − pij )1−xij =
= exp
di (x)βi − ψ(β) , (8)
1 + e(βi +βj )
ij∈D
ij∈D
i∈N
where (di (x), i ∈ N ) is the degree sequence of x, i.e. di (x) is the number of ties in x
involving node i.
Other ERGMs include, for example, the exponential family models of Holland and
Leinhardt (1981) and their modifications (Fienberg and Wasserman, 1981), as well as
the Markov graphs of Frank and Strauss (1986).
If N 0 ⊆ N , any probability distribution PN for a network XN = (Xd , d ∈ D(N ))
induces a distribution PN 0 for the subnetwork XN 0 = (Xd , d ∈ D(N 0 )) corresponding
to the dyads in D(N 0 ). In particular, XN 0 is the subgraph of XN induced by N 0 .
10

One problem with ERGMs is that, typically, PN 0 needs not be the related to PN in
a meaningful way, and needs not be an ERGM itself. In that sense, the ERGMs are
not marginalizable; see also Snijders (2010) as well as Shalizi and Rinaldo (2013). The
Erdös–Rényi models and the beta models are marginalizable in this sense. Many other
network models suffer from this issue: see, e.g., Crane and Dempsey (2015). We shall
return to this and related issues in more detail in Section 6.

3.3

Parametrizations of random network models

Since networks are arrays of binary variables, we may use the Möbius parametrization
and the exponential form in Section 2.3 to represent their distributions.
For a given finite node set N , we thus let B(N ) = B be the collection of all subsets of
D(N ). Now if X is a network on N and B a non-empty set in B, then XB = (Xd , d ∈ B)
is the subnetwork indexed by the dyads in B. It will be convenient to identify each nonempty set B ∈ B with the edge-induced subgraph of the complete graph on N comprised
of the edges in B. Equivalently, B \ ∅ represents all subgraphs of the complete graph on
N without isolated nodes. In particular, for a non-empty B ∈ B, we may equivalently
write the event {XB = 1B } as the event {B ⊂ X} that the graph B is a subgraph of
the random graph X.
The Möbius parameters corresponding to the distribution P of a network X are
(zB , B ∈ B), where
(
P(B ⊆ X) if B 6= ∅
zB =
1
otherwise.
Thus, the Möbius parameters for a network distribution are just the implied probabilities
of observing all subgraphs of the complete graph on N without isolated nodes. In the
exponential family parametrization (3), the canonical sufficient statistic s is defined over
graphs GN , and the coordinate indexed by any non-empty B ∈ B is simply the indicator
function
(
1 if B ⊆ x
sB (x) =
0 otherwise.
Example 1. Suppose that we observe the network x in Figure 3 (a), where N =
{1, 2, 3, 4}.
For any probability measure P on GN , we have that, under both the Möbius parametrization and the canonical parametrization in (3),
Pν (x) = z14,23,24,34 − z12,14,23,24,34 − z13,14,23,24,34 + z12,13,14,23,24,34
= exp{ν14 + ν23 + ν24 + ν34 + ν14,23 + ν14,24 + ν14,34 + ν23,24 + ν23,34 +
ν24,34 + ν14,24,23 + ν14,24,34 + ν14,34,23 + ν13,14,34 + ν14,23,24,34 − ψ(ν)},
11

(9)

2
1

2

4

1

4

3

3

(a)

(b)

Figure 3: Two observed networks with four nodes.
where ν is the unique 63-dimensional vector parametrizing the distribution of X. Notice that the Möbius parametrization is considerably simpler than the exponential family
parametrization in this instance, since x is a dense network and only parameters corresponding to supergraphs of the observed network enter into the calculation. However,
if we instead observe the sparser network y ∈ GN in Figure 3 (b), we get
Pν (y) = z14,23 − z14,23,12 − z14,23,13 − z14,23,24 − z14,23,34
+z14,23,12,13 + z14,23,12,24 + z14,23,12,34 + z14,23,13,34 + z14,23,13,24 + z14,23,24,34
−z12,14,23,24,34 − z13,14,23,24,34 + z12,13,14,23,24,34

(10)

= exp{ν14 + ν23 + ν14,23 − ψ(ν)}.
Thus the exponential form is simpler for the sparse case, save for the fact that the
log-partition function ψ(ν) is complicated.


3.4

Exchangeability

We are concerned with probability distributions on networks that are exchangeable:
invariant under relabelings of the node set N . Exchangeability is a well-known form
of probabilistic invariance, and, from a modeling perspective, also a natural simplifying
assumption to impose when formaliziing statistical models for networks. Below we
summarize well-known facts on exchangeability.
A distribution P of a random array X = (Xij )i,j∈N over a finite nodeset N is said
to be weakly exchangeable (WE) (Silverman, 1976; Eagleson and Weber, 1978) if for all
permutations π ∈ S(N ) we have that
P{(Xij = xij )i,j∈N } = P{(Xij = xπ(i)π(j) )i,j∈N }.

(11)

If the array X is symmetric — i.e. Xij = Xji , we say it is symmetric weakly exchangeable
(SWE). In the following we shall for brevity say that X is WE, SWE, etc. in the meaning
that its distribution is.
A symmetric binary array with zero diagonal can be interpreted as a matrix of ties
(adjacency matrix) of a random network and thus the above concepts can be translated
12

into networks. A random network is exchangeable if its adjacency matrix is SWE.
Then a random network is exchangeable if and only if its distribution is invariant under
relabeling of the nodes of the network. We will distinguish the case of a finite node set
from that of a (countably) infinite one, and in the former case we will speak of finite
exchangeability. A random network X over a countably infinite nodeset N is said to be
exchangeable, if every finite induced subnetwork XN 0 for N 0 ⊂ N is.
When N is infinite, exchangeability is well-understood. Indeed, any doubly infinite
random SWE array can be represented as a mixture of so-called φ-matrices (Diaconis
and Freedman, 1981) in the following way. Let P∞ be the convex set of all exchangeable
distributions for networks with a countably infinite number of nodes and let E∞ denote
the extreme points of that set. Then we have:
Proposition 1. P ∈ E∞ if and only if for every finite N 0 ⊂ N ,
Z
Y
PN 0 (x) =
φ(ui , uj )xij {1 − φ(ui , uj )}1−xij du,
[0,1]N ij∈D(N 0 )

∀x ∈ GN 0 ,

(12)

where PN 0 is the induced probability on GN 0 and φ is a measurable function from [0, 1]2
to [0, 1]. The function φ is unique up to a measure-preserving transformation of the unit
interval.
In a graph theoretic context, (equivalence classes of) φ-matrices are also known as
graphons (Lovász and Szegedy, 2006).
Elements of E∞ as given in (12) are all dissociated (Silverman, 1976) in the sense
that {Xij , i, j ∈ N 0 } are independent of {Xkl , k, l ∈ N 00 } whenever N 0 ∩ N 00 = ∅ in fact
it holds (Aldous, 1981, 1985) that
Proposition 2. P ∈ E∞ if and only if P is exchangeable and dissociated.
We emphasize that the representation of exchangeable distributions on networks by
means of φ-matrices requires an infinite node set N . If N is finite, a finitely exchangeable
network on N needs not have a representation as a mixture of φ-matrices, and need not
be extendable, i.e. the induced probability measure from a probability distribution over
networks on a larger node set. In fact, the properties of finitely exchangeable networks
are distinctively different; see for example Diaconis (1977); Diaconis and Freedman
(1980); Matúš (1995); Kerns and Székely (2006); and Konstantopoulos and Yuan (2015).
We will return to the issue of extendability later in Section 6 and focus instead on the
properties of finitely exchangeable network distributions.

3.5

Exponential representation of exchangeable networks

For exchangeable random networks on a finite nodeset N , both the Möbius and the
exponential parameters simplify. More precisely, P is an exchangeable distribution on
13

GN if and only if P (x) = P (x0 ) whenever x ∼
= x0 , i.e. whenever x and x0 are identical
save for a permutation of their labels. Thus, it follows that a random network X is
exchangeable if and only if zB = zB 0 whenever B ∼
= B 0 , where zB = P(B ⊆ X).
Next we let UN denote the set of all unlabeled graphs on N and write ∅ for the
empty graph. Each U ∈ UN can be identified with an isomorphism class in GN , which
we will denote with [U ]. Then, any exchangeable distribution P on GN is parametrized
by {zU , U ∈ UN }, with z∅ = 1, where zU = P (B ⊆ X), for any B ∈ [U ]. Collecting
identical terms in (2) we obtain
X
P(X = x) =
(−1)|U |−|x| rU (x)zU , x ∈ GN
(13)
U ∈UN

where |U | is the number of edges in U and rU (x) is the number of graphs in [U ] that
contain x as a subgraph.
Similarly, it holds for the exponential representation (3) that a probability distribution on GN is exchangeable if and only if for all B and B = B 0 in D(N ) with B ∼
= B 0 , the
corresponding canonical parameters satisfy νB = νB 0 . Thus we can represent the family
of exchangeable network distributions on N as the exponential family of probability
distributions of the form
n X
o
Pν (x) = exp
σU (x)νU − ψ(ν) , x ∈ GN ,
(14)
U ∈UN \∅

for any choice of the canonical parameters ν = (νU , U ∈ UN \ ∅) ∈ RUN \∅ , where ψ(·)
is the log-partition function and
X
σU (x) =
sB (x)
B∈[U ]

is the number of graphs in the isomorphism class corresponding to U that are subgraphs
of x. Indeed from (1) we have that
σU (x) = inj(U, x)/inj(U, U ).

(15)

Note that the set of exchangeable distributions again form a linear and regular exponential family with canonical sufficient statistics (σU , U ∈ UN \∅), canonical parameters
(νU , U ∈ UN \ ∅), and mean value parameters
X
τU = E{σU (X)} =
zU = sub(U, D)zU = inj(U, D)zU /inj(U, U )
(16)
B∈[U ]

for U ∈ UN \ ∅. In other words, the family of finitely exchangeable network distributions
is an ERGM.
14

By standard theory of exponential families (Barndorff-Nielsen, 1978), upon observing a network x ∈ GN , the maximum likelihood estimate of the Möbius parameters
(zU , U ∈ UN \ ∅) under the assumption of exchangeability is obtained by equating the
observed canonical statistic to its expectation. As a result, the MLE of zU , for any
non-empty U is
ẑU = σU (x)/sub(U, D) = inj(U, x)/inj(U, D) = tinj (U, x).

(17)

Strictly speaking, this is not the maximum likelihood estimate in the exponential family,
but rather its completion (Barndorff-Nielsen, 1978) obtained by including all limit points
of the set of mean value parameters. In fact, the canonical parameters νU are not estimable based on observation of a single network. Note that, interestingly, the maximum
likelihood estimates of the Möbius parameters are exactly the injective homomorphism
densities introduced in Section 2. For an extreme and infinitely exchangeable network
(the dissociated case), these estimates are also well known to be consistent (Lovász and
Szegedy, 2006, Theorem 2.5).
Example 2. Consider the networks x and y in Figure 3. Using the exponential representation (14) we see — with a notation that hopefully is transparent — that the
probability of observing x is
n
o
Pν (x) = exp 4ν + 5ν
+ν +ν
+ν
+ 2ν
+ν
− ψ(ν) .
(18)
In terms of the Möbius parametrization the expression simplifies to
Pν (x) = z

− 2z

+z

.

(19)

If x is observed, the non-zero estimates of Möbius parameters for U 6= ∅ are
ẑ = 2/3, ẑ
ẑ

= 5/12, ẑ
= 1/4, ẑ

= 1/3, ẑ
= 1/6, ẑ

= 1/4,
= 1/12;

(20)

These numbers are obtained from (17) by calculating, for example, as
inj(

, x) = 3! = 6,

inj(

, D) = 4 × 3 × 2 = 24.

Note that the canonical parameters in (18) are not estimable in this case as the set of
sufficient statistics (σU (X), U ∈ UN \ ∅) are at the boundary of their convex support.


4

Independence structures for exchangeable networks

In this section we will investigate the Markov properties of exchangeable network distributions on a finite node set.
15

4.1

Possible independence structures

Recall that we use the term incidence graph L(N ) for the line graph of a complete graph
on N , whereby L(N ) has edges between dyads which are incident i.e. dyads having a
node in common. Figure 4 displays the incidence undirected graph for N = {1, 2, 3, 4}
and a bidirected version L↔ (N ) of the same. In fact, we show next that the skeleton
X23

X24

X12

X23

X34

X13

X24

X12

X14

X34

X13

X14

Figure 4: (a) The incidence graph for N {1, 2, 3, 4}. (b) The bidirected incidence graph with 4
nodes.

graph of a finitely exchangeable network distribution can only be one of four possible
types.
Proposition 3. The dependence skeleton sk(X) of an exchangeable random network X
is one of the following:
(a) the empty graph;
(b) the incidence graph L(N ) ;
(c) the complement of the incidence graph Lc (N ) ;
(d) the complete graph.

Proof. Let |N | = n. Exchangeability implies that one can relabel the n2 vertices of the
dependence skeleton corresponding to every permutation of (1, . . . , n) without changing
independence statements of form i⊥
⊥ j | S for some S ⊂ D. If the dependence skeleton
is empty or complete it is clear that relabeling would not change such independence
statements.
If there is an edge ij, kl, for mutually non-equal i, j, k, l, and a missing edge i0 j 0 , k 0 l0 ,
for mutually non-equal i0 , j 0 , k 0 , l0 , in the dependence skeleton, then by the relabeling
corresponding to sending (i0 , j 0 , k 0 , l0 ) to (i, j, k, l) we obtain a missing edge between ij
and kl. However, in the latter labeling, there is an independence of form ij ⊥
⊥ kl | S
whereas in the former labeling there is no independence of form ij ⊥
⊥ kl | S. Hence, such
a graph cannot be the dependence skeleton of an exchangeable random network.
Similarly, if there is an edge ij, il, for mutually non-equal i, j, l, and a missing edge
0
0
i j , i0 l0 , for mutually non-equal i0 , j 0 , l0 , in the dependence skeleton, then by the relabeling
16

corresponding to sending (i0 , j 0 , l0 ) to (i, j, l) we obtain a missing edge between ij and il.
With the same argument as in the previous case, such a graph cannot be the dependence
skeleton of an exchangeable random network.
The remaining cases are when either all the pairs of vertices ij, il are adjacent and
all the pairs of vertices ij, kl are not adjacent, which leads to the L(N ) ; or all the pairs
of vertices ij, kl are adjacent and all the pairs of vertices ij, il are not adjacent, which
leads to Lc (N ) .

To give a complete characterization of all possible graphical Markov structures with
these skeletons, we need to give a precise definition of a generic graphical Markov structure. We abstain from doing so but just mention that it is clear that directed edges are
not relevant for exchangeable random networks. If we vary the type of edge so that edges
are either all bidirected or undirected, this leads to six different dependence structures
since the undirected and bidirected graphs in cases (a) and (d) are Markov equivalent.
If an exchangeable random network X satisfies the Markov property associated with an
undirected or bidirected dependence graph G with vertex set {Xij , ij ∈ D(N )} then G
is one of these cases. Dependence structures corresponding to the complete graph in
(d) are uninteresting. The case (a) corresponds to the Erdös–Renyi model. Structures
corresponding to the other four dependence graphs are classified below, where our main
focus is on the bidirected incidence graph case as it corresponds to the dissociated model
and has certain desired properties concerning extendability; see Section 6.
Undirected incidence graph – the Frank-Strauss model.
(1986) showed the result below:

Frank and Strauss

Proposition 4. Every clique C of the incidence graph L(N ) of the complete network
base (N , D) corresponds exactly to a subnetwork (NC , C) of (N , D) that is either a
triangle or a k-star.
Based on this, they show that a random network X is Markov with respect to L(N )
if and only if the canonical parameters νB are zero unless B is a k-star or a triangle.
Assuming also exchangeability, this model is known as the Frank-Strauss model and
studied extensively in Frank and Strauss (1986).
Example 3. Consider again the network x in Figure 3 and any choice of the canonical
parameters ν ∈ RUN \∅ . Following Example 2, the probability of observing x under the
Frank–Strauss model becomes
n
o
Pν (x) = exp 4ν + 5ν
+ν
+ν
− ψ(ν) ,
(21)
whereas no further simplification appears in terms of the mean-value parameters {zU , U ∈
UN }.

17

Undirected complement of the incidence graph. Cliques in the complement of
the incidence graph Lc (N ) correspond to collections of disjoint dyads. Therefore, the
corresponding model is an ERGM with sufficient statistics corresponding to collections of
disjoint dyads (including the subnetwork that is a single dyad). For the case of a network
with five nodes, the dependence graph is the famous Petersen graph (Petersen, 1898)
and for n vertices, the graph is known as the Kneser graph KGn,2 (Godsil and Royle,
2001, Ch. 7); for this reason we shall refer to the model determined by all exchangeable
random networks that are Markov w.r.t. the Kneser graph as the Kneser model.
Example 4. Consider again the network x in Figure 3. Still following Example 2 we get
using the exponential representation (14) and the Markov property w.r.t. Lc (N ) that in
the Kneser model, the probability of observing x is
n
o
Pν (x) = exp 4ν + ν − ψ(ν) ,
(22)
for any ν ∈ RUN \∅ .



Bidirected complement of the incidence graph. Every connected subset of the
complement of the incidence graph Lc↔ (N ) corresponds to a disconnected subnetwork of
the of size N or the subnetwork that is a single tie (which corresponds to a single vertex
in Lc↔ (N )). Therefore, the corresponding model has Möbius parameters corresponding
to these. This model satisfies a property that is dual to dissociatedness so that, for
example Xij ⊥
⊥ Xjk .
Example 5. If the random network X is Markov w.r.t. the complement of the bidirected
incidence graph Lc↔ (N ), the Möbius parametrization of the probability of the network
x in Figure 3 is
P (X = x) = (z )2 z − 2z (z )2 + (z )3 .
(23)
This has been obtained, for example, as z
= (z )2 z since, for an arbitrary labeling
of , two of the three disconnected induced subgraphs Lc↔ (N )[12, 34], Lc↔ (N )[13, 24],
and Lc↔ (N )[14, 23] of Lc↔ (N ) correspond to the subnetwork and one to .

Later in Section 6 we will argue that the only Markov structures that are also
extendable to arbitrarily large networks are the complete graph, the empty graph, and
the bidirected incidence graph; hence the latter of these structures is the main focus of
the present paper.

4.2

Bidirected incidence graph – the dissociated model

We now consider in detail the class of finitely exchangeable network distributions that are
Markov with respect to the bidirected incidence graph G = L↔ (N ), where N is finite.
18

This is equivalent to requiring an exchangeable network X on N to be dissociated:
{Xij , i, j ∈ N 0 } are independent of {Xkl , k, l ∈ N 00 } for each pair disjoint subsets N 0
and N 00 of N .
We begin by stating a simple yet useful property of the incidence graph. For a given
finite node set N , let C(N ) ⊂ D(N ) denote the subsets of dyads corresponding to
connected subgraphs of the complete graph on N .
Lemma 1. A random network X is dissociated if and only if for any non-empty subnetwork B it holds that
Y
zB =
zCi ,
i

where the Ci are the connected components of B.
Proof. The proof follows directly from (4) and the fact that there is a one-to-one correspondence between the set of all connected subgraphs of L↔ (N ) and C(N ).

˙ for
With some abuse of notation, for any non-empty U ∈ UN , we will write U = ∪C
the decomposition of one arbitrary graph in the isomorphism class [U ] into the disjoint
union of its connected components in C(N ). Note that each graph in [U ] has the same
number of isomorphic connected components. By exchangeability and dissociatedness,
for any U ∈ UN ,
Y
zU =
zC ,
˙
C∈C(N ):U =∪C

regardless of the choice of the representing graph in [U ]. From (4) and (13) we thus
arrive at the following result.
Proposition 5. A network X on N is exchangeable and dissociated if and only if
X
Y
P(X = x) =
(−1)|U |−|x| rU (x)
zC , ∀x ∈ GN ,
(24)
U ∈UN

˙
C∈C(N ):U =∪C

It is worth noting that the model combining dissociatedness and exhangeability
remains a log-mean linear model in the sense of Roverato et al. (2013).
Example 6. The additional restriction of dissociatedness does not yield any helpful
simplification of the exponential representations in (18) from Example 2, since the dissociatedness conditions entails restriction on the possible values of the canonical parameters and not on the form of the probabilities. For the observed network x, no further
simplification of its Möbius parametrization in (19) is possible.
Continuing with Example 2, under dissociatedness, the likelihood function in (19)
should now be maximized not only under the constraints that all expressions in (2) be
19

non-negative, but also under the non-linear constraints described in (4), which in this
case reduces to just one constraint z = z 2 . Thus, although the likelihood function is
linear in z, numerical maximization is in general necessary. In this particular case we
find that
ẑ = 1/2, ẑ
ẑ

= 5/16, ẑ
= 3/16, ẑ

= 1/4 ẑ

= 3/16,

= 1/8, ẑ

= 1/16,

and the remaining parameter estimates are zero, which should be compared to the
results in the non-dissociated case. In fact, this estimate represents a mixture of the
uniform distribution of all networks isomorphic to the observed network x, and the
empty network, with weights 3/4 and 1/4, respectively.

We emphasize that when dissociatedness is assumed, the maximum likelihood estimator may no longer be unique, as the example below shows.
1

2

3

4

Figure 5: An observed networks with four nodes.
Example 7. Suppose that we observe the network in Figure 5. Then the likelihood
function assuming dissociatedness is maximized at any value of λ satisfying 0 ≤ λ ≤ 1/16
by the quantities
ẑ = 1/2, ẑ

= 3/16, ẑ

= 1/16 − λ, ẑ

= 1/4, ẑ

= λ, ẑ

= 1/16,

and all other ẑ equal to zero. Indeed this corresponds to a random network that has
probability 3/4 of being isomorphic to the observation and the remaining probability
mass of 1/4 is distributed arbitrarily between a triangle plus an isolated point, and a
3-star.


5

Exchangeable and summarized random networks

An assumption commonly used in network modeling is that the probability of a network
configuration x in GN be a function of its degree distribution {nj (x), j ∈ N }, where
X
nj (x) =
δj {di (x)}, j ∈ N ,
i∈N (x)

P

with di (x) = j∈N Xij the degree of node i and δj (k) = 1 if k = j and 0 otherwise.
Note that here the degree distribution is not normalized and nj (x) is the number of
nodes in x with degree j.
20

Lauritzen (2008) defines a random binary array X = (Xij )i,j∈N to be weakly summarized (WS) if there is a function ϕ such that it holds that
P{(Xij = xij )i,j∈N } = ϕ(Ri + Ci , i ∈ N ),
(25)
P
P
where Ri = j Xij and Cj = i Xij are the row and column sums. For symmetric
arrays, it holds that Ri = Ci , and a distribution with the above property may be called
symmetric weakly summarized (SWS). Again, this can be translated into statements
about networks: A random network X on N is summarized if, for any x ∈ GN , P(X =
x) = ϕ(di (x), i ∈ N ), where di (x) = Ri = Ci is the degree of node i. SWE distributions
are generally not SWS or vice versa (Lauritzen, 2008). If a distribution is both SWE
and SWS then we write that the distribution is SWES. When N is infinite and X is a
SWES array whose distribution is in E∞ , Lauritzen (2008) showed that Proposition 1
holds with φ having a specific form: φ(u, v) = a(u)a(v)/{1 + a(u)a(v)} (Lauritzen,
2008). The beta model in (7) then emerges when further conditioning on u and letting
βi = log a(ui ).

5.1

Characterizing summarizing statistics

We now study exchangeable and summarized distributions on a finite node set N . Isomorphic graphs have the same degree distribution; but, as shown for instance in Example
8 below, the opposite is not true and thus the set of summarized and exchangeable network distributions on N is a subfamily of the set of exchangeable distribution on N . In
order to characterize the types of restriction that summarizedness entails, we begin with
some preliminary lemmas which identify which subgraph counts are functions of the
degree distribution only. Recall that subgraph counts are canonical sufficient statistics
for the exponential family of exchangeable network distributions: see Section 3.5.
Lemma 2. Given an unlabeled graph U ∈ UN , it holds that σU (x) is a function of the
degree distribution of x, for all x ∈ GN , if
(a) U = Sk , a k-star for any size k ≥ 0 or U =
edges, or

, the disjoint union of two independent

(b) U = K|N |−1 , the complete graph of size |N | − 1, or U = K|N |−1 \ {e}, the complete
graph of size |N | − 1 with one edge removed.
Proof. To prove (a), note that a 0-star is simply a vertex and a 1-star is an edge. If
U = Sk for k 6= 1 then
∞  
X
j
σSk (x) =
nj (x),
k
j=0

21

where the sum only effectively extends at most from j = k to |N | − 1 as all other terms
are zero. If U = S1 we have to divide by two, and obtain
σS1 (x) =

∞
X

jnj (x)/2 = |E(x)|

(26)

j=0

where |E(x)| is the number of edges in x. The formula (26) is also known as Euler’s
handshaking lemma; see e.g. (Wilson, 1996, p.12). Finally, if U =
we have


|E(x)|
σ =
− σS2 (x).
2
For (b), we have that


|N |,



 2,
σK|N |−1 (x) =

1,



 0,

if n(x) = (0, . . . , 0, |N |);
if n(x) = (0, . . . , 0, 2, |N | − 2);
if n(x) = (0, . . . , 0, 1r , 0, . . . , 0, |N | − r − 1, r);
otherwise,

where 1r is 1 at the rth entry. The top row corresponds to the complete graph, the
second row to the complete graph with one edge removed, and the third row to a
complete graph with a vertex from which |N | − r − 1 edge is removed.
A similar function can be provided for the case of K|N |−1 \ {e}, but we abstain from
giving the somewhat cumbersome details.

The converse to the statement in Lemma 2 only holds with some modification:
Lemma 3. Given an unlabeled graph U ∈ UN , if σU (x) is a function of the degree
distribution of x, for all x ∈ GN , then
(a) if U has at most |N | − 2 vertices, U is a k-star or U =
two independent edges;

, the disjoint union of

(b) if U has at most |N |−1 vertices, U is a k-star, or U = , or K|N |−1 , or K|N |−1 \e,
a complete graph on |N | − 1 vertices with one edge removed.
Proof. It is enough to show that for any U that is not one of the above graphs, there
exist two graphs x1 and x2 with the same degree sequence (and hence the same degree
distribution) such that σU (x1 ) 6= σU (x2 ).

22

(a): For U with at most |N | − 2 vertices, if U contains two adjacent vertices i and
j with degrees more then 1 then define x1 and x2 as follows: Let x1 contain U and
a disjoint edge kl. Let x2 contain U with the ij edge removed and two non-adjacent
vertices k and l adjacent to i and j respectively. These two graphs obviously have the
same degree sequence and σU (x1 ) = 1 whereas σU (x2 ) = 2.
Hence, the cases remaining to be considered are such where U is a forest of stars. If
there are at least two stars in U that are 2-stars or larger then call these S and T . Let
x1 be U and define x2 as follows. Connect the hubs of S and T . In addition, take a
leaf from each of S and T , connect them and remove the edge between them and their
respective hubs. Now x1 and x2 have the same degree sequence but σU (x1 ) = 1 and
σU (x2 ) = 0.
If U contains only one star S with hub s that is not an edge and some disjoint edges
then take an edge ij in U which is disjoint from S. Define x1 by adding a vertex l to
U and connecting it to i and to a leaf k of S. Define x2 by taking x1 , removing the sk
edge and the ij edge, and adding the ki edge and the sj edge. Both graphs have the
same degree sequence, but if S is a 3-star or larger we have σU (x1 ) = 2 and σU (x2 ) = 3;
if S is a 2-star we have σU (x1 ) = 6 and σU (x2 ) = 9.
Finally, the only case that is left is when U is collection of three or more disjoint edges:
ij, kl, hr, and a set E of disjoint edges. Let x1 be the union of the cycle i ∼ k ∼ l ∼ j ∼ i,
the hr edge, and E; let x2 be the union of the path h ∼ i ∼ j ∼ l ∼ k ∼ r and E. Both
graphs have the same degree sequence but σU (x1 ) = 2 whereas σU (x2 ) = 1.
(b): By (a) it is enough to work with U with n − 1 vertices that is not one of those
mentioned. Collections of disjoint edges and stars (including forest of edges) have been
covered in the proof of (a). If U is disconnected and not one of these, then take two
connected components with edges ij and kl in each component. Let x1 be U , and define
x2 by removing ij and kl and connecting i to k and j to l. We have that σU (x1 ) = 1
whereas σU (x2 ) = 0.
Hence, henceforth, assume that U is connected. If there is an induced P4 or C4
(i, j, k, l) in U , i.e., an induced path or cycle with 4 nodes, then define x1 and x2 as
follows: For x1 , add a vertex h and connect it to i. For x2 , add h and connect it to
l, remove kl, and add ik. The graphs have the same degree sequence, but σU (x1 ) > 0
whereas σU (x2 ) = 0.
If there are no induced P4 or C4 the graph is trivially perfect (see Brandstadt et al.
(1999) Section 7.1.2) and there is a vertex i that is adjacent to all other vertices in U .
If among the neighbours of i, there are two non-adjacent pairs of vertices and an
edge we have the following two cases:
1) Among the neighbours of i, suppose that there are two non-adjacent pairs of
vertices (j, k) and (k, l) and a pair of adjacent vertices (l, h), where h may be the same
as j. In this case, define x1 by adding u and connecting it to k, and define x2 by adding

23

u and connecting it to h, removing lh, and connecting kl. The graphs have the same
degree sequence, but σU (x1 ) > 0 whereas σU (x2 ) = 0.
2): Among the neighbours of i, suppose that there are two non-adjacent pairs of
vertices (j, k) and (l, h) and a pair of adjacent vertices (k, l), where h may be the same
as j. In this case, define x1 by adding u and connecting it to h, and define x2 by adding
u and connecting it to k, adding lh, and removing kl. The graphs have the same degree
sequence, but σU (x1 ) > 0 whereas σU (x2 ) = 0.
Therefore, the only cases that are left are stars, the complete graph, or the complete
graph with one edge removed. This completes the proof.

In general, if x1 and x2 have the same degree distributions, the fact that their
probabilities should be identical induces a linear restriction on the parameters (νU , U ∈
UN ) and hence the set of exchangeable and summarized distributions on a nodeset N is
again a linear exponential family with dimension equal to the number of distinct degree
distributions for simple graphs on |N | nodes; however, the restrictions induced on the
parameters in (14) may be complicated, as illustrated in the example below.
Similarly, if x1 and x2 have the same degree distributions, a linear restriction is
induced on the parameters (zU , U ∈ UN ) in (13). This is also illustrated in the example
below.
Example 8. For networks with at most four nodes, the isomorphism class of a network
is uniquely determined by the degree distribution, so we consider networks with five
nodes. For most such networks, the isomorphism class is also identified by the degree
distribution, the six exceptions being displayed in Fig. 6, where the node degrees of x1
and x2 both are (2, 2, 2, 1, 1), those of y1 and y2 (3, 2, 2, 2, 1), and those of z1 and z2
(3, 3, 2, 2, 2).

x2

y2

z2

x1

y1

z1

Figure 6: Three pairs of non-isomorphic graphs with identical degree distributions.
It thus follows that for any choice of canonical parameters ν ∈ RUN \∅ , the distribution Pν
of an exchangeable network on five nodes is summarized if and only if Pν (x1 ) = Pν (x2 ),

24

Pν (y1 ) = Pν (y2 ), and Pν (z1 ) = Pν (z2 ). Using the exponential representation (14) we
obtain that the canonical parameters must satisfy three linear relations. From the
relation Pν (x1 ) = Pν (x2 ) we get
log{Pν (x2 )/Pν (x1 )} = ν

−ν

+ 2ν

−ν

−ν

= 0,

where we have used Lemma 2 to infer that all terms of the form νU σU (·) must cancel if
U is a k-star or U = . Similarly, we get from Pν (y1 ) = Pν (y2 ) that
log{Pν (y2 )/Pν (y1 )} = ν

−ν

+ν

+ν

−ν

−ν

−ν

= 0,

and a somewhat more involved linear relation appears from the fact that Pν (z1 ) =
Pν (z2 ). Similarly using (13) we obtain that the Möbius parameters must satisfy three
linear relations. The simplest of the three relations with Möbius parameters for Pν (z1 ) =
Pν (z2 ) is
Pν (z2 ) − Pν (z1 ) = z
−z
−z
+z
= 0.
We refrain from giving details of the corresponding constraints with Möbius parameters obtained from Pν (x1 ) = Pν (x2 ) and Pν (y1 ) = Pν (y2 ) as well as with canonical
parameters obtained from Pν (z1 ) = Pν (z2 ).

Corollary 1. Let U be a finite unlabelled graph without isolated nodes. If there is a
function ϕU so that σU (x) = ϕU {nj (x), j = 0, 1, 2, . . .} for all networks x of any size,
then U = Sk , a k-star, or U = , the disjoint union of two independent edges.
Proof. If this is true for all networks, we can always choose N sufficiently large for
Lemma 3, (a) to apply.


5.2

The SE* model

Motivated by the results from the previous section, we can now simplify the exchangeable
ERGM (14) and define an ERGM by the expression
Pν (x) = exp

|−1
n |NX

σk (x)νk + σ

ν

o
− ψ(ν) ,

x ∈ GN ,

(27)

k=1

where σk (x) is the number of k-stars in x, 1 ≤ k ≤ |N | − 1, and each of the |N |
parameters ν , ν1 , . . . , ν|N |−1 vary independently on the real line.
We shall refer to this ERGM as the SE*-model, reflecting that all distributions within
the model are both summarized and exchangeable, the star indicating that the model
is not containing all such distributions. This is because neither the number of complete
25

sub-graphs on |N | − 1 nor the number of complete sub-graphs on |N | − 1 nodes with one
edge removed are sufficient statistics for the SE* model, so that, in virtue of Lemma 2
and Lemma 3, there exist summarized exchangeable network distributions that are not in
the SE* model. The distributions implied by the marginal beta model, discussed below,
are such an example. We reserve the term SE-model for the set of all distributions that
are exchangeable and summarized and DE-model for the set of all distributions that are
exchangeable and dissociated.
We note the similarities between the SE*-model (27) and the exchangeable Markov
model (EM-model) of Frank and Strauss (1986), exponential family of the form


|−1
|NX

σk (x)νk + σ ν
Pν (x) = exp
− ψ(ν) , x ∈ GN , ν ∈ R|N | ,


k=1

which differs from SE*-model only by σ ν
replacing σ ν . Though nearly identical, the justifications behind the EM and the SE* models are quite different. The
EM model results from postulating certain symmetric Markov properties for the edges,
covered by case (b) in Proposition 3. On the other hand, the SE* model arises as a
convenient sub-model of the class of summarized and exchangeable network distributions. The intersection of the SE*-model and the EM-model only contains the counts
for k-stars in the exponent, and so does the intersection of the SE-model and the EM
model. The resulting SEM-model is the ERGM with sufficient statistics given by the
entries degree distribution, studied in Sadeghi and Rinaldo (2014). This is because there
is a one-to-one linear transformation between the number of k-stars of x and the degree
distribution of x, as demonstrated in the proof of Lemma 2.
From the computational standpoint, parameter estimation in the SE* model and in
the EM model can be carried out by the same procedures, such as pseudo-maximum
likelihood estimation and MCMCMLE methods – see, e.g., Strauss and Ikeda (1990),
Geyer and Thompson (1992) and Hunter et al. (2008) – and is likely to be just as
problematic.

5.3

The marginal beta model

Here we consider the marginal beta model, an example of a family of network distributions
that are dissociated, exchangeable, and summarized, and consequently satisfy all the
conditions discussed above.
Consider the beta model defined in (7). Suppose that (Bi , i ∈ N ) are independent
and identically distributed real-valued random variables with distribution FB . Then the
expression (7) can be understood as the conditional distribution
of Xij given Bi and Bj
Q
and thus the density satisfies the factorization f (y) = i f (yi | pa(yi )) for the directed
26

acyclic graph (DAG) Dn that consists of (Bi , i ∈ N ) and (Xij , ij ∈ D(N )) as vertices
and arrows from each Bi to all the Xij , j ∈ N .
Figure 7 illustrates the case for N = {1, 2, 3, 4}. Indeed the exact same graph also

X12

B1

B3

B2

B4

X13

X23

X14

X24

X34

Figure 7: Directed acyclic graph D4 .
illustrates the Markov structure for a general φ-matrix, where just Bi should be replaced
by uniformly distributed Ui and the arrows represent the φs.
By marginalization over and conditioning on the variables in the DAG model the
resulting dependence structure can in general be captured by mixed graphs; for further
details see, for example, Richardson and Spirtes (2002) and Sadeghi (2013). For example,
by conditioning on the Bi we obtain the empty graph with all the Xij as vertices. This
implies the complete independence of Xij , corresponding to the dyadic independence in
the beta model (7). By marginalizing over Bi , the bidirected incidence graph appears,
as studied extensively in this paper and exemplified in Figure 4. As discussed before,
this implies that after marginalization over Bi , the network is dissociated. We refer
to this model as the marginal beta model ; the dissociatedness also follows immediately
from the following “de Finetti type” representation for the distribution of X:
Z
P(X = x) =

Y

Rn ij∈D(N )

e(βi +βj )xij
dFBN (β),
(β
+β
)
i
j
1+e

x ∈ GN ,

(28)

where FBN denotes the |N |-fold product distribution from FB . The function φ in Proposition 1 is in fact pij as described in (7). It clearly follows from (28) that the marginal
beta distribution is exchangeable; in addition, (8) implies that the marginal beta model
is summarized.

6

Consistent systems of network models

In this section we shall consider systems of network models and their relation to each
other. We let N be the basic set of network nodes and consider models for finite subsets
N 0 ⊆ N . The basic set N may be finite or countably infinite. If PN 0 is a distribution
00
of a random network XN 0 with nodeset N 0 and N 00 ⊆ N 0 we let ΠN
N 0 PN 0 denote the
distribution of the induced subnetwork XN 00 under PN 0 . Thus the marginalization op0
erator ΠN
N 00 takes as input a probability distribution on GN 0 and returns the induced or
27

marginal probability distribution over GN 00 corresponding to the dyads with endpoints
in N 00 . By constructions, marginalization operators satisfy the property
0

00

0

N
N
ΠN
N 000 = ΠN 000 ◦ ΠN 00 .

for any N 000 ⊂ N 00 ⊂ N 0 , so they form a projective system. A collection {PN 0 , N 0 ⊆ N }
of random network models for all finite subsets N 0 of N is said to be (strongly) consistent
if for every N 00 ⊆ N 0 in the collection it holds that
0

PN 00 = ΠN
N 00 (PN 0 ),
in other words it holds that the marginal to a subnetwork of any network model is
identical to the corresponding network model for the subnetwork. Thus a strongly
consistent system forms a projective statistical field in the sense of Lauritzen (1988). We
say the system is weakly consistent if
0

ΠN
N 00 (PN 0 ) ⊆ PN 00
i.e. marginalization of any network model for a larger nodeset is not in conflict with the
network model for the subnetwork.
We first note that the bidirected Markov property itself is always marginalizable in
the sense that if X is bidirected Markov w.r.t. a graph G, then the marginal distribution
of XA is automatically Markov w.r.t. the induced subgraph GA , whereas the similar
statement is generally not true for the undirected Markov property.
This holds in particular for the random network models when G(N 0 ) = L↔ (N 0 )
is the bidirected incidence graph. In other words, the system of dissociated random
network models is weakly consistent. The same holds for the system of exchangeable
random networks {EN 0 , N 0 ⊆ N }, and when both exchangeability and dissociatedness
are combined to form the system of exchangeable and dissociated
random networks
c
L↔
0 ⊆ N }, or when considering the system of models {E L↔ , N 0 ⊆ N }, which are
,
N
{EN
0
N0
all Markov w.r.t. the bidirected complements of the line graphs.
Correspondingly, the Möbius parametrization is marginalizable in the sense that if
N 0 for
X is a random network with nodeset N and N 0 ⊆ N , the Möbius parameters zB
N for X:
the induced subnetwork are identical to the corresponding parameters zB
0

N
N
zB
= zB
= zB , for all B ∈ B(N 0 ).

(29)

From any weakly consistent system {PN 0 , N 0 ⊆ N } we can construct a strongly
∗ , N 0 ⊆ N }, by letting
consistent system {PN
0
\
00
∗
PN
ΠN
0 =
N 0 (PN 00 )
N 00 :N 00 ⊃N 0

28

provided that the intersection is non-empty. Thus each family in the system consists
exactly of those distributions that can be obtained as marginals of distributions from
models on arbitrarily large nodesets. We shall thus say that the elements in the strongly
consistent variant of a weakly consistent system are completely extendable.
We note that, for example, the system of exchangeable random networks is not
strongly consistent. In Example 2, the estimated distributions are easily seen not to be
extendable to a network with more than four nodes. In general it is a difficult issue to
N 0 , B ∈ B(N 0 )} is extendable
determine whether a given system of Möbius parameters {zB
to a larger network with nodeset N , i.e. if there exists a system of Möbius parameters
N , B ∈ B(N )}, such that (29) holds.
{zB
Nevertheless, we can characterize the strongly consistent sequences of exchangeable
random networks as follows. Below, if N is infinite, we let B(N ) be the set of all finite
subsets of D(N ), which, as before, we represent as finite edge-induced subgraphs of the
complete graph on N .
Proposition 6. All strongly consistent and infinitely extendable systems of exchangeable
Möbius parameters (zB , B ∈ B(N )) are those which satisfy the conditions
(a) z∅ = 1;
(b) zB = zB 0 = zU if B and B 0 are in [U ];
(c) for all non-negative integers n and all N 0 ⊂ N with |N 0 | = n
X
(−1)|U |−|x| rU (x)zU ≥ 0, ∀x ∈ GN 0 ,
U ∈UN 0

where we recall that rU (x) is the number of graphs in [U ] that contain x as a subgraph. In
addition, the sequences of Möbius parameters corresponding to the extremal distribution
E∞ are those satisfying the dissociated property that if B has connected components
C1 , . . . , Ck then zB = zC1 · · · zCk .
Proof. From (29) it follows that any system of valid Möbius parameters is consistent
and as previously argued, these are valid if and only if they satisfy z∅ = 1 and the nonnegativity restriction in equation (13) above. We have also previously argued that the
additional product condition characterizes dissociated networks which are the extreme
points according to de Finetti’s theorem (Proposition 1).

It is worth pointing out that, when |N | = ∞, if X is a random network on N whose
distribution is extremal (and therefore dissociated), then, for each non-empty U ∈ UN 0

29

with |N 0 | < ∞,
Z
zU =

Y
0

[0,1]N ij∈E(U )

φ(ui , uj )du,

(30)

where E(U ) denotes the set of edges in U and φ is some measurable, symmetric function
from [0, 1]2 into [0, 1].
Using the arguments in Chapter 14 of Aldous (1985) (see also Kallenberg, 2005,
for a generalization), de Finetti’s theorem (Proposition 1) and Proposition 6 yields the
following result.
Corollary 2. The convex set of feasible Möbius parameters are those which can be
represented as


Z

Z
Y
zB =
φ(ui , uj , λ) du dλ, B ∈ B(N ),
(31)

[0,1]  [0,1]n
ij∈B

where n = |B| and φ is a (not necessarily unique) measurable function from [0, 1]3 to
[0, 1]. The extreme points of this convex set correspond to the cases in which the function
φ(ui , uj , λ) is a constant function of λ, for almost all λ ∈ [0, 1].
Still, these characterizations are quite implicit. It seems difficult to obtain more explicit characterizations. For example, Figure 16.1 on page 288 of Lovász (2012) displays
the area of variation of (z , z ) as given in (30) for all exchangeable and dissociated
infnite networks, and this is a very complicated region. The set of infinitely extendable
pairs is given by the convex hull of the region (Bollobás, 1976).
Using Corollary 2 we can show that strongly consistent systems of exchangeable
models which are Markov w.r.t. bidirected complement of the incidence graph must be
Erdös–Renyi models. First, we need a preliminary lemma. The lemma and proof are
analogues of Theorem 10 in Diaconis and Freedman (1981).
Lemma 4. Assume X is an exchangeable random network with an infinitely extendable
set of Möbius parameters satisfying, for some η ∈ (0, 1),
z = η,

z

= η2,

z

= η4.

Then, the edges in X are independent and identically distributed with P (Xij = 1) = η,
i.e. X is Erdös–Renyi.
Proof. Since all elements are exchangeable, we have from (31) that
Z
η=z =
φ(u, v, λ) du dv dλ.
[0,1]3

30

But also
z

= η2 =

Z

φ(u, v, λ)φ(u0 , v, λ) du du0 dv dλ =

[0,1]4

)2

(Z

Z

φ(u, v, λ) du
[0,1]2

dv dλ.

[0,1]

Thus,
)2

(Z

Z

φ(u, v, λ) du − η
[0,1]2

and hence

dv dλ = 0,

[0,1]

Z
φ(u, v, λ) du = η

for almost all (v, λ),

which in turn implies that, if we assume N = {1, 2, 3, . . .},
Z
φ(u, v, λ)φ(u0 , v 0 , λ) du du0 dv dv 0 dλ = η 2 .
z = P (X12 = 1, X34 = 1) =
[0,1]5

Next, we have that
4

η =z

Z
=

φ(u, v, λ)φ(u0 , v, λ)φ(u, v 0 , λ)φ(u0 , v 0 , λ) du du0 dv dv 0 dλ

[0,1]5

Z

(Z

=
[0,1]3

)2
φ(u, v, λ)φ(u0 , v, λ) dv

du du0 dλ,

[0,1]

and hence we conclude as above that, for almost all (u, u0 , λ),
Z
φ(u, v, λ)φ(u0 , v, λ) dv = η 2 .

(32)

[0,1]

We would now wish to let u = u0 in the above equation but this might just be the
exceptional set. However, we may extend φ periodically to be defined on (−∞, ∞) ×
[0, 1]2 by letting
φ(u, v, λ) = φ(u mod 1, v, λ)
so that (32) still holds almost surely. Then, using Lebesgue’s theorem, we can write
Z Z 
Z
Z
1
2
φ(u, v, λ) dv =
lim 2
φ(u + s, v, λ)φ(u + t, v, λ) ds dt dv
[0,1]
[0,1] →0 4
− −
Z Z Z
1
= lim 2
φ(u + s, v, λ)φ(u + t, v, λ) dv ds dt = η 2 .
→0 4
− − [0,1]
As above, we conclude, for almost all λ, u, v, that φ(u, v, λ) = η and hence we have
zD = η |D| , implying that all edges are independent. Hence, the model is Erdös–Renyi.


31

Proposition 7. Consider a countable nodeset N and a strongly consistent family {PN 0 , N 0 ⊆
N } of random network models; if all elements of PN 0 are exchangeable and Markov w.r.t.
the complement of the bidirected line graph Lc↔ (N 0 ), then they are all Erdös–Renyi models.
Proof. We assume that N = {1, 2, 3, . . .}. By exchangeability, we have that, for some
η ∈ [0, 1], z = P(X12 = 1) = η. Since X12 ⊥⊥ X23 , we also have that
z

= P(X12 = X23 = 1) = P(X12 = 1)P(X23 = 1) = η 2 = z

,

where the last equality is obtained as in the proof of Lemma 4. The bidirected complement of the incidence graph for N 0 = {1, 2, 3, 4} contains the edges
{12 ↔ 34, 13 ↔ 24, 14 ↔ 23}.
Since all the distributions are Markov w.r.t. this graph we have
z

= P (X12 = 1, X34 = 1)P (X14 = 1, X23 = 1) = (z

and the conclusion now follows from Lemma 4.

)2 = η 4 .


Analogous results hold true if the Markov assumption in Proposition 7 is replaced
with Markov properties with respect to the undirected incidence graph as in the Frank–
Strauss models or the undirected complement of the line graph, as in the Kneser models.
The proof of these facts are quite elementary and we abstain from giving the details. In
fact these sequences are not even weakly consistent, as marginals of undirected Markov
distributions are not Markov with respect to the corresponding induced subgraph.
Finally we hasten to point out that indeed the system of marginal beta models is
strongly consistent by construction and that this clearly remains true if the mixing
distribution F is assumed to belong to any specific subset of distributions F.

7

Discussion

We have derived a complete characterization of possible Markov properties of exchangeable network models, and studied some of the implied models. We also consider summarized exchangeable network models in which the probability of a network is only a
function of its degree distributions, and relate them to the other models we discuss in the
paper. Overall, our findings have unveiled several interesting properties of exchangeable
network models and established connections among seemingly disparate concepts used
in network analysis, the probability literature on exchangeable arrays and the discrete
mathematics literature on graph limits.
32

While we have focused on exchangeable and extendable network models, we point
out that these are by no means the only interesting network models. In fact, many other
parametric models, not fulfilling those properties, can also be successfully deployed to
represent and study networks. Examples include the beta model (Chatterjee et al., 2011;
Yan and Xu, 2013; Rinaldo et al., 2013) and the sparse Bernoulli model considered in
Krivitsky and Kolaczyk (2015); see also the remarks in the introduction on partial
conditional independence and on weakened forms of exchangeability.
We conclude with a final remark on the computational difficulties associated with
fitting the various models discussed in the paper. As it is very often the case with
ERGMs, model fitting can be rather challenging, and our models are no exception. For
the DE and DSE models, one could in principle rely on the algorithms proposed in
Drton and Richardson (2008), appropriately modified to allow for zero counts and for
the fact that the MLE of the model parameters is nearly all cases on the boundary of
the parameter space. However such algorithms may not scale well with the network
size. As for the model given in (14), and its submodels, the SE and SE* and the EM
models, parameter estimation can be carried out using pseudo-maximum likelihood and
MCMC-based methods, (see, e.g. Strauss and Ikeda, 1990; Geyer and Thompson, 1992),
implemented, for instance, in the R package ergm (Hunter et al., 2008). In all these cases,
however, we expect that fitting could be problematic, as these procedures do not scale
well with the network size and MCMC convergence can be very slow or hard to assess.
In particular, we expect that the issues of degeneracy (see Schweinberger, 2011; Rinaldo
et al., 2009) plaguing many ERGMs will also impact estimation of these models.

Acknowledgements
The authors are grateful to Éva Czabarka for proving an earlier version of Lemma 3.
Alessandro Rinaldo and Kayvan Sadeghi were partially supported by AFOSR grant
FA9550-14-1-0141.

References
Aldous, D. (1981). Representations for partially exchangeable random variables. Journal of
Multivariate Analysis 11, 581–598.
Aldous, D. (1985). Exchangeability and related topics. In P. Hennequin (Ed.), École d’Été de
Probabilités de Saint–Flour XIII — 1983, pp. 1–198. Heidelberg: Springer-Verlag. Lecture
Notes in Mathematics 1117.
Baddeley, A. and J. Møller (1989). Nearest-neighbour Markov point processes and random sets.
International Statistical Review 57, 89–121.

33

Barndorff-Nielsen, O. E. (1978). Information and Exponential Families in Statistical Theory.
Chichester, UK: John Wiley and Sons.
Bollobás, B. (1976). Relations between sets of complete subgraphs. In C. S. J. A. Nash-Williams
and J. Sheehan (Eds.), Proceedings of the 5th British Combinatorics Conference.
Boutilier, C., N. Friedman, M. Goldszmidt, and D. Koller (1996). Context-specific independence
in Bayesian networks. In Proceedings of the Twelfth International Conference on Uncertainty
in Artificial Intelligence, UAI’96, San Francisco, CA, USA, pp. 115–123. Morgan Kaufmann
Publishers Inc.
Brandstadt, A., V. B. Le, and J. Spinrad (1999). Graph Classes: A Survey. SIAM Monographs
on Discrete Mathematics and Applications. Philadelphia: Society of Industrial and Applied
Mathematics.
Caron, F. and E. Fox (2017). Sparse graphs using exchangeable random measures. Journal of
Royal Statistical Society, Series B 79, 1295–1366.
Chatterjee, S., P. Diaconis, and A. Sly (2011). Random graphs with a given degree sequence.
Annals of Applied Probability 21, 1400–1435.
Cox, D. R. and N. Wermuth (1993). Linear dependencies represented by chain graphs (with
discussion). Statistical Science 8, 204–218; 247–277.
Crane, H. and W. Dempsey (2015). A framework for statistical network modeling. Available at
https://arxiv.org/abs/1509.08185.
Diaconis, P. (1977). Finite forms of de Finetti’s theorem on exchangeability. Synthese 36,
271–281.
Diaconis, P. and D. Freedman (1980). Finite exchangeable sequences. Annals of Probability 8,
745–764.
Diaconis, P. and D. Freedman (1981). On the statistics of vision: the Julesz conjecture. Journal
of Mathematical Psychology 24, 112–138.
Diaconis, P. and S. Janson (2008). Graph limits and exchangeable random graphs. Rendiconti
di Matematica, Serie VII 28, 33–61.
Drton, M. and T. S. Richardson (2008). Binary models for marginal independence. Journal of
the Royal Statistical Society Series B 70, 287–309.
Eagleson, G. K. and N. C. Weber (1978). Limit theorems for weakly exchangeable arrays.
Mathematical Proceedings of the Cambridge Philosophical Society 84, 123–130.
Erdös, P. and A. Rényi (1960). On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5, 17–61.

34

Fienberg, S. E. and S. Wasserman (1981). Discussion of an exponential family of probability
distributions for directed graphs by Holland and Leinhardt. Journal of the American Statistical
Association 76, 54–57.
Frank, O. (1991). Statistical analysis of change in networks. Statistica Neerlandica 45, 283–293.
Frank, O. and D. Strauss (1986). Markov graphs. Journal of the American Statistical Association 81, 832–842.
Geyer, C. J. and E. A. Thompson (1992). Constrained Monte Carlo maximum likelihood for
dependent data. Journal of the Royal Statistical Society. Series B (Methodological) 54, 657–
699.
Godsil, C. and G. Royle (2001). Algebraic Graph Theory. New York: Springer.
Holland, P. and S. Leinhardt (1981). An exponential family of probability distributions for
directed graphs. Journal of the American Statistical Association 76, 33–50.
Hunter, D. R., S. M. Goodreau, and M. S. Handcock (2008). Goodness of fit of social network
models. Journal of the American Statistical Association 103, 248–258.
Hunter, D. R., M. S. Handcock, C. T. Butts, S. M. Goodreau, Morris, and Martina (2008). ergm:
A package to fit, simulate and diagnose exponential family models for networks. Journal of
Statistical Software 24, 1–29.
Kallenberg, O. (2005). Probabilistic Symmetries and Invariance Principles. New York: Springer–
Verlag.
Kauermann, G. (1996). On a dualization of graphical Gaussian models. Scandinavian Journal
of Statistics 23, 105–116.
Kerns, G. J. and G. J. Székely (2006). DeFinettis theorem for abstract finite exchangeable
sequences. Journal of Theoretical Probability 19, 589–608.
Kolaczyk, E. D. (2009). Statistical Analysis of Network Data: Methods and Models. Springer
Publishing Company, Incorporated.
Konstantopoulos, T. and L. Yuan (2015). On the extendibility of finitely exchangeable probability measures. Preprint, Department of Mathematics, Uppsala University. Available at
https://arxiv.org/abs/1501.06188.
Krivitsky, P. N. and E. D. Kolaczyk (2015). On the question of effective sample size in network
modeling: An asymptotic inquiry. Statistical Science 30, 184–198.
Lauritzen, S. L. (1988). Extremal Families and Systems of Sufficient Statistics. Heidelberg:
Springer-Verlag. Lecture Notes in Statistics 49.
Lauritzen, S. L. (1996). Graphical Models. Oxford, United Kingdom: Clarendon Press.

35

Lauritzen, S. L. (2003). Rasch models with exchangeable rows and columns. In J. M. Bernardo,
M. J. Bayarri, J. O. Berger, A. P. Dawid, D. Heckerman, A. F. M. Smith, and M. West (Eds.),
Bayesian Statistics, Volume 7, Oxford, UK, pp. 215–232. Oxford University Press.
Lauritzen, S. L. (2008). Exchangeable Rasch matrices. Rendiconti di Matematica, Serie VII 28,
83–95.
Lovász, L. (2012). Large Networks and Graph Limits, Volume 60 of Colloquium Publications.
American Mathematical Society.
Lovász, L. and B. Szegedy (2006). Limits of dense graph sequences. Journal of Combinatorial
Theory, Series B 96, 933–957.
Matúš, F. (1995). Finite partially exchangeable arrays. Technical Report 1856, Inst. of Inf.
Theory and Autom., http://staff.utia.cas.cz/matus/CsiMaGSI13.pdf.
Newman, M. (2010). Networks: An Introduction. Oxford University Press, Inc.
Nyman, H., J. Pensar, T. Koski, and J. Corander (2014). Stratified graphical models — contextspecific independence in graphical models. Bayesian Analysis 9, 883–908.
Orbantz, P. and D. M. Roy (2015). Bayesian models of graphs, arrays, and other exchangeable
structures. IEEE Transactions on Pattern Analysis and Machine Intelligence 37, 437–461.
Petersen, J. (1898). Sur le théorème de Tait. L’Intermédiaire des Mathématiciens 5, 225–227.
Richardson, T. (2003). Markov properties for acyclic directed mixed graphs. Scandinavian
Journal of Statistics 30, 145–157.
Richardson, T. S. and P. Spirtes (2002). Ancestral graph Markov models. Annals of Statistics 30,
962–1030.
Rinaldo, A., S. E. Fienberg, and Y. Zhou (2009). On the geometry of discrete exponential
families with application to exponential random graph models. Electr. J. Statist. 3, 446–484.
Rinaldo, A., S. Petrović, and S. E. Fienberg (2013). Maximum lilkelihood estimation in the beta
model. Annals of Statistics 41, 1085–1110.
Roverato, A., M. Lupparelli, and L. La Rocca (2013). Log-mean linear models for binary data.
Biometrika 100, 485–494.
Sadeghi, K. (2013). Stable mixed graphs. Bernoulli 19, 2330–2358.
Sadeghi, K. and A. Rinaldo (2014). Statistical models for degree distributions of networks. In
NIPS Workshop: From Graphs to Rich Data. arXiv:1411.3825.
Schweinberger, M. (2011). Instability, sensitivity, and degeneracy of discrete exponential families.
Journal of the American Statistical Association 106, 1361–1370.

36

Schweinberger, M. and M. S. Handcock (2015). Local dependence in random graph models:
characterization, properties and statistical inference. Journal of Royal Statistical Society,
Series B 77, 647–676.
Shalizi, C. and A. Rinaldo (2013). Consistency under sampling of exponential random graph
models. Annals of Statistics 41, 508–535.
Silverman, B. W. (1976). Limit theorems for dissociated random variables. Advances in Applied
Probability 8, 806–819.
Snijders, T. A. B. (2010). Conditional marginalization for exponential random graph models.
The Journal of Mathematical Sociology 34, 239–252.
Snijders, T. A. B., P. E. Pattison, G. L. Robins, and M. S. Handcock (2006). New specifications
for exponential random graph models. Sociological Methodology 36, 99–153.
Strauss, D. and M. Ikeda (1990). Pseudolikelihood estimation for social networks. Journal of
the American Statistical Association 85, 204–212.
Wasserman, S. and P. Pattison (1996). Logit models and logistic regressions for social networks:
I. an introduction to Markov graphs and p∗ . Psychometrika 61, 401–425.
West, D. B. (2001). Introduction to Graph Theory (2nd ed.). Upper Saddle River, NJ, USA:
Prentice Hall.
Wilson, R. J. (1996). Introduction to Graph Theory (4th ed.). Essex, UK: Longman.
Yan, T. and J. Xu (2013). A central limit theorem in the β-model for undirected random graphs
with a diverging number of vertices. Biometrika 100, 519–524.

37

