# Sharp Threshold for the Fréchet Mean (or Median) of Inhomogeneous Erdős-
Rényi Random Graphs

François G. Meyer
Applied Mathematics, University of Colorado at Boulder, Boulder CO 80305
<EMAIL_ADDRESS>
https://francoismeyer.github.io F.G.M was supported by the National Natural
Science Foundation (CCF/CIF 1815971).

###### Abstract

We address the following foundational question: what is the population, and
sample, Frechet mean (or median) graph of an ensemble of inhomogeneous Erdős-
Rényi random graphs? We prove that if we use the Hamming distance to compute
distances between graphs, then the Frechet mean (or median) graph of the
inhomogeneous random graphs with expected adjacency matrix $\mathbf{P}$ is
obtained by thresholding $\mathbf{P}$: an edge exists between the vertices $i$
and $j$ in the mean graph if and only if $p_{ij}>1/2$. We show that the result
also holds for the sample mean (or median) when $\mathbf{P}$ is replaced with
the sample mean adjacency matrix. Consequently, the Fréchet mean (or median)
graph of inhomogeneous Erdős-Rényi random graphs exhibits a sharp threshold:
it is either the empty graph if $\max p_{ij}<1/2$, or the complete graph if
$\min p_{ij}>1/2$. This novel theoretical result has some significant
practical consequences; for instance, the Fréchet mean of an ensemble of
sparse inhomogeneous random graphs is always the empty graph.

Keywords: Fréchet mean; Fréchet median; statistical network analysis.

##  1 Introduction

The Fréchet mean (or median) graph, which extends the notion of mean to
probability measures defined on metric spaces [11], has become a standard tool
for the analysis of graph-valued data (e.g., [7, 9, 12, 17, 23, 25]). At the
same time, inhomogeneous Erdős-Rényi random graphs [24, 4] have great
practical importance since they provide tractable models that capture many of
the topological structures of real networks [13, 22].

Let $\mathcal{G}$ be the set of all simple labeled graphs with vertex set
$\left\\{1,\ldots,n\right\\}$, and let $\mathcal{S}$ be the set of $n\times n$
adjacency matrices of graphs in $\mathcal{G}$,

$\mathcal{S}=\left\\{\bm{A}\in\\{0,1\\}^{n\times
n};\text{where}\;a_{ij}=a_{ji},\text{and}\;a_{i,i}=0;\;1\leq i<j\leq
n\right\\}.$ (1)

We denote by
$\mathcal{G}\mspace{-1.0mu}\big{(}\mspace{-2.0mu}n,\bm{P}\mspace{-1.0mu}\big{)}$,
the probability space formed by inhomogeneous Erdős-Rényi random graphs [24,
4], which is defined as follows. We assign to every graph $G\in\mathcal{G}$,
with adjacency matrix $\bm{A}$, the probability

$\mspace{2.0mu}\mathbb{P}\mspace{-2.0mu}\left(\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\right)=\prod_{1\leq
1<j\leq n}\left[p_{ij}\right]^{a_{ij}}\left[1-p_{ij}\right]^{1-a_{ij}}.$ (2)

The $n\times n$ matrix $\bm{P}=\left[p_{ij}\right]$ determines the edge
probabilities $0\leq p_{ij}\leq 1$, with $p_{ii}=0$. Throughout the paper, we
identify
$\mathcal{G}\mspace{-1.0mu}\big{(}\mspace{-2.0mu}n,\bm{P}\mspace{-1.0mu}\big{)}$
with the probability space $(\mathcal{S},\operatorname{\mathbb{P}})$, where
$\operatorname{\mathbb{P}}$ is defined by (2).

The prominence of
$\mathcal{G}\mspace{-1.0mu}\big{(}\mspace{-2.0mu}n,\bm{P}\mspace{-1.0mu}\big{)}$
stems from its ability to provide tractable models of random graphs that can
capture many of the structures of real networks (e.g., stochastic block models
[1, 10] to model communities [29]). We equip $\mathcal{G}$ with the Hamming
distance defined as follows.

######  Definition 1.

The Hamming distance between $G$ and $G^{\prime}$ in $\mathcal{G}$, with
adjacency matrix $\bm{A}$ and $\bm{A}^{\prime}$ respectively, is given by

$d_{H}(G,G^{\prime})=\sum_{1\leq i<j\leq n}\lvert
a_{ij}-a^{\prime}_{ij}\rvert.$ (3)

We characterize the mean of the probability $\operatorname{\mathbb{P}}$ with
the Fréchet mean and median graphs, [11, 28], that are defined as follows.

######  Definition 2.

The Fréchet mean of the probability measure $\operatorname{\mathbb{P}}$ is the
set formed by the solutions to

$\bm{\mu}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\operatorname{\mathbb{P}}\mspace{-2.0mu}\big{]}=\underset{G\in\mathcal{G}}{\operatorname{argmin}}\mspace{4.0mu}\sum_{G^{\prime}\in\mathcal{G}}d_{H}^{2}(G,G^{\prime})\mspace{2.0mu}\mathbb{P}\mspace{-2.0mu}\left(\mspace{-2.0mu}G^{\prime}\mspace{-2.0mu}\right)$
(4)

and the Fréchet median of the probability measure $\operatorname{\mathbb{P}}$
is the set formed by the solutions to

$\bm{m}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\operatorname{\mathbb{P}}\big{]}=\underset{G\in\mathcal{G}}{\operatorname{argmin}}\mspace{4.0mu}\sum_{H\in\mathcal{G}}d_{H}(G,H)\mspace{2.0mu}\mathbb{P}\mspace{-2.0mu}\left(\mspace{-2.0mu}H\mspace{-2.0mu}\right),$
(5)

where $d_{H}$ is the Hamming distance (3).

We note that solutions to the minimization problems (4) and (5) always exist,
but need not be unique. Because all the results in this paper hold for any
graph in the set formed by the solutions to (4) and (5), and without any loss
of generality, we assume that
$\bm{\mu}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\operatorname{\mathbb{P}}\mspace{-2.0mu}\big{]}$
and
$\widehat{\bm{\mu}}_{N}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\operatorname{\mathbb{P}}\mspace{-2.0mu}\big{]}$
each contains a single element.

Because the focus of this work is not the computation of the Fréchet mean
graph, but rather a theoretical analysis of the properties that the Fréchet
mean graph inherits from the probability measure $\operatorname{\mathbb{P}}$,
defined in (2), we can assume that all the graphs are defined on the same
vertex set.

This notion of centrality is well adapted to metric spaces (since graph sets
are not Euclidean spaces (e.g., [6, 19, 16, 17, 23]). The vital role played by
the Fréchet mean as a location parameter, is exemplified in the work of [2]
and [25], who have created novel families of random graphs by generating
random perturbations around a given Fréchet mean (also called modal or central
graph in [2]). In practice, the Fréchet mean itself is computed from a
training set of graphs that display specific topological features of interest.
To take full advantage of the training set, one needs to insure that the
sample Fréchet mean inherits from the training set the desired topological
structure.

By replacing $\operatorname{\mathbb{P}}$ with the empirical measure, the
concept of Fréchet mean and median graphs can be extended to a sample of
graphs defined on the same vertex set $\left\\{1,\ldots,n\right\\}$.

######  Definition 3.

Let $\left\\{G^{(k)}\right\\}_{1\leq k\leq N}$,be independent random graphs,
sampled from $\operatorname{\mathbb{P}}$. The sample Fréchet mean is the set
composed of the solutions to

$\widehat{\bm{\mu}}_{N}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\operatorname{\mathbb{P}}\mspace{-2.0mu}\big{]}=\underset{G\in\mathcal{G}}{\operatorname{argmin}}\mspace{4.0mu}\frac{1}{N}\sum_{k=1}^{N}d^{2}(G,G^{(k)});$
(6)

the sample Fréchet median is the set composed of the solutions to

$\widehat{\bm{m}}_{N}\left[\operatorname{\mathbb{P}}\right]=\underset{G\in\mathcal{G}}{\operatorname{argmin}}\mspace{4.0mu}\frac{1}{N}\sum_{k=1}^{N}d(G,G^{(k)}).$
(7)

Several algorithms have been proposed to compute the sample Fréchet mean and
median when the distance $d$ is the edit distance (e.g., [3, 8, 20]), or the
Euclidean distance (e.g., [15, 18]).

###  1.1 Our main contributions

The prominence of the inhomogeneous Erdős-Rényi random graph model [4] prompts
the following critical question: does the Fréchet mean of
$\operatorname{\mathbb{P}}$ inherit from the probability space
$\mathcal{G}\mspace{-1.0mu}\big{(}\mspace{-2.0mu}n,\bm{P}\mspace{-1.0mu}\big{)}$
any of the edge connectivity information encoded by $\bm{P}$?

In this paper, we answer this question. We show in Theorem 1 that the
population Fréchet mean graph
$\bm{\mu}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\operatorname{\mathbb{P}}\mspace{-2.0mu}\big{]}$
can be obtained by thresholding the mean adjacency matrix
$\mathbb{E}\left[\bm{A}\right]=\bm{P}$; an edge exists between the vertices
$i$ and $j$ in
$\bm{\mu}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\big{]}$ if
and only if $\mathbb{E}\left[\bm{A}\right]_{ij}>1/2$. We prove in Theorem 2
that this result also holds for the sample Fréchet mean graph,
$\widehat{\bm{\mu}}_{N}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\operatorname{\mathbb{P}}\mspace{-2.0mu}\big{]}$,
when $\mathbb{E}\left[\bm{A}\right]$ is replaced with the sample mean
adjacency matrix, $\widehat{\mathbb{E}}_{N}\left[\bm{A}\right]$.

##  2 Main Results

Let $\bm{P}=\left[p_{ij}\right]$ be an $n\times n$ symmetric matrix with
entries $0\leq p_{ij}\leq 1$. In the following two theorems we evaluate the
Fréchet mean (or median) graph, and the sample mean (or median) graph of
$\mathcal{G}\mspace{-1.0mu}\big{(}\mspace{-2.0mu}n,\bm{P}\mspace{-1.0mu}\big{)}$.
We first consider the Fréchet mean graph and median graph. We denote by $[n]$
the set $\\{1,\ldots,n\\}$.

###  2.1 The population Fréchet mean graph and median graph of
$\mathcal{G}(n,\mathbb{P})$

######  Theorem 1.

Let $\bm{m}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\bm{A}\big{]}$ and
$\bm{\mu}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\big{]}$ be
the adjacency matrices of the Fréchet median graph
$\bm{m}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\operatorname{\mathbb{P}}\big{]}$
and mean graph
$\bm{\mu}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\operatorname{\mathbb{P}}\mspace{-2.0mu}\big{]}$
respectively. Then $\bm{m}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\bm{A}\big{]}$
and
$\bm{\mu}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\big{]}$
are given by

$\forall
i,j\in[n],\quad\Big{[}\bm{m}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\bm{A}\big{]}\Big{]}_{ij}=\Big{[}\bm{\mu}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\big{]}\Big{]}_{ij}=\begin{cases}1&\text{if}\quad
p_{ij}>1/2,\\\ 0&\text{otherwise.}\end{cases}$ (8)

###### Proof.

The proof is given in Section 5.2. ∎

###  2.2 The sample Fréchet mean graph of a graph sample in
$\mathcal{G}(n,\mathbb{P})$

We now turn our attention to the sample Fréchet mean graph. The computation of
the sample Fréchet mean graph using the Hamming distance is NP-hard (e.g.,
[5]). For this reason, several alternatives have been proposed (e.g., [9,
12]).

Before presenting the second result, we take a short detour through the sample
Fréchet median graph (e.g., [14, 20, 27]), minimiser of (7), and which can be
computed using the majority rule [2].

######  Lemma 1 ([2]).

The adjacency matrix $\widehat{\bm{m}}_{N}\left[\bm{A}\right]$ of the sample
Fréchet mean graph
$\widehat{\bm{m}}_{N}\left[\operatorname{\mathbb{P}}\right]$ is given by

$\forall
i,j\in[n],\quad\Big{[}\widehat{\bm{m}}_{N}\left[\bm{A}\right]_{ij}\Big{]}=\begin{cases}1&\text{if}\;\sum_{k=1}^{N}a^{(k)}_{ij}\geq
N/2,\\\ 0&\text{otherwise.}\end{cases}$ (9)

We now come back to the second main contribution, where we prove that the
sample Fréchet mean graph of $N$ independent random graphs from
$\mathcal{G}\mspace{-1.0mu}\big{(}\mspace{-2.0mu}n,\bm{P}\mspace{-1.0mu}\big{)}$
is asymptotically equal (for large sample size $N$) to the sample Fréchet
median graph, with high probability.

######  Theorem 2.

$\forall\delta\in(0,1),\exists N_{\delta},\forall N\geq N_{\delta}$,
$\widehat{\bm{m}}_{N}\left[\bm{A}\right]$ and
$\widehat{\bm{\mu}}_{N}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\big{]}$
are given by

$\forall
i,j\in\left[n\right],\quad\Big{[}\widehat{\bm{\mu}}_{N}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\big{]}\Big{]}_{ij}=\Big{[}\widehat{\bm{m}}_{N}\left[\bm{A}\right]\Big{]}_{ij}=\begin{cases}1&\text{if}\quad\mathbb{E}\left[\bm{A}\right]_{ij}=p_{ij}>1/2,\\\
0&\text{otherwise,}\end{cases}$ (10)

with probability $1-\delta$ over the realizations of the graphs
$\left\\{G^{(1)},\ldots,G^{(N)}\right\\}$ in
$\mathcal{G}\mspace{-1.0mu}\big{(}\mspace{-2.0mu}n,\bm{P}\mspace{-1.0mu}\big{)}$.

###### Proof.

The proof is given in section 5.5. ∎

The practical impact of Theorem 2 is given by the following corollary, which
is an elementary consequence of theorem 2 and lemma 1.

######  Corollary 1.

$\forall\delta\in(0,1),\exists N_{\delta},\forall N\geq N_{\delta}$, the
sample Fréchet mean graph
$\widehat{\bm{\mu}}_{N}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\operatorname{\mathbb{P}}\mspace{-2.0mu}\big{]}$
is given by the majority rule

$\forall
i,j\in\left[n\right],\quad\widehat{\bm{\mu}}_{N}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\big{]}_{ij}=\begin{cases}1&\text{if}\quad\sum_{k=1}^{N}a^{(k)}_{ij}>N/2,\\\
0&\text{otherwise,}\end{cases}$ (11)

with probability $1-\delta$ over the realizations of the graphs,
$\left\\{G^{(1)},\ldots,G^{(N)}\right\\}$, in
$\mathcal{G}\mspace{-1.0mu}\big{(}\mspace{-2.0mu}n,\bm{P}\mspace{-1.0mu}\big{)}$.

This novel theoretical result has some significant practical consequences;
consider for instance sparse graphs where $\min p_{ij}<1/2$ (e.g., graphs with
${\scriptstyle\mathcal{O}}\left(n^{2}\right)$ but $\omega(n)$ edges), then the
sample Fréchet mean is the empty graph, and is pointless. More generally, the
sample Fréchet mean computed from a training set of graphs, which display
specific topological features of interest, will not inherit from the training
set the desired topological structure.

##  3 Simulation Studies

We compare our theoretical analysis to finite sample estimates that were
computed using numerical simulations. All graphs were generated using the
$\mathcal{G}\mspace{-1.0mu}\big{(}\mspace{-2.0mu}n,\bm{P}\mspace{-1.0mu}\big{)}$
model (2). The sample Fréchet mean was computed using (11). All graphs had
$n=512$ vertices. The sample size was $N=1,000$. The software used to conduct
the experiments is publicly available [26]. We explored the switching of the
mean graph from the empty graph to the complete graph, as the entries in the
probability matrix $\bm{P}$ shift from being all less than $1/2$ to being all
larger than $1/2$.

We investigate this shift over a large set of matrices $\bm{P}$ that are
generated at random. During the simulation, each $\bm{P}$ is created by
populating its entries at random using independent (up to symmetry) beta
random variables,

$p_{ij}\sim\text{beta}(\nu,\omega),$ (12)

and thus the edge probability $p_{ij}$ becomes a random variable with mean and
variance given by,

$\mathbb{E}\left[p_{ij}\right]=\frac{\nu}{(\nu+\omega)},\quad\text{and}\quad\operatorname{var}\left[p_{ij}\right]=\frac{\nu\omega}{[(\nu+\omega)^{2}(\nu+\omega+1)]}.$
(13)

In our experiments, we fix $\nu+\omega=64$, and we let $\nu$ vary over the
interval $(0,\nu+\omega)$, thereby exploring the range $[0,1]$ for
$\mathbb{E}\left[p_{ij}\right]$. This process makes it possible to probe the
behaviour of
$\widehat{\bm{\mu}}_{N}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\operatorname{\mathbb{P}}\mspace{-2.0mu}\big{]}$
over a large range of possible edge connectivity: from the very sparse to the
very dense graphs.

We denote by
$\lvert\mathcal{E}(\widehat{\bm{\mu}}_{N}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\operatorname{\mathbb{P}}\mspace{-2.0mu}\big{]})\big{\rvert}$
the number of edges of the sample Fréchet mean graph
$\widehat{\bm{\mu}}_{N}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\operatorname{\mathbb{P}}\mspace{-2.0mu}\big{]}$.
Fig. 1 displays
$\lvert\mathcal{E}(\widehat{\bm{\mu}}_{N}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\operatorname{\mathbb{P}}\mspace{-2.0mu}\big{]})\big{\rvert}$
as a function of the mean edge density, $\mathbb{E}\left[p_{ij}\right]$. We
normalize
$\big{\lvert}\mathcal{E}(\widehat{\bm{\mu}}_{N}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\operatorname{\mathbb{P}}\mspace{-2.0mu}\big{]})\big{\rvert}$
by dividing the number edges of
$\widehat{\bm{\mu}}_{N}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\operatorname{\mathbb{P}}\mspace{-2.0mu}\big{]}$
by the maximum possible number of edges,

$\frac{2\big{\lvert}\mathcal{E}(\widehat{\bm{\mu}}_{N}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\operatorname{\mathbb{P}}\mspace{-2.0mu}\big{]})\big{\rvert}}{n(n+1)}.$
(14)

For each value of $\mathbb{E}\left[p_{ij}\right]$ on the $x$-axis in Fig. 1,
we generate 16 independent random realizations of the $N=1,000$ sample random
graphs in
$\mathcal{G}\mspace{-1.0mu}\big{(}\mspace{-2.0mu}n,\bm{P}\mspace{-1.0mu}\big{)}$.
We compute the average number of edges of
$\widehat{\bm{\mu}}_{N}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\operatorname{\mathbb{P}}\mspace{-2.0mu}\big{]}$
over the 16 realizations, and report this number on the $y$-axis of Fig. 1.
Each curve corresponds to a different value of $\nu$. We increase $\nu$ from
$8$ to $64$ by $8$ each time. As $\nu$ increases, the variance on the
distribution of the entries $p_{ij}$ decreases, the curve in Fig. 1 becomes
steeper, and the switch from the empty graph to the complete graph becomes
more sudden.

Figure 1: Fraction of the number of edges in
$\widehat{\bm{\mu}}_{N}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\operatorname{\mathbb{P}}\mspace{-2.0mu}\big{]}$
as a function of the location parameter
$\mathbb{E}\left[p_{ij}\right]=\nu/64$. The eight curves correspond to
$\nu=8,16,24,32,40,48,64$.

The experiment confirms that the Fréchet mean of inhomogeneous Erdős-Rényi
random graphs exhibits a sharp threshold: it rapidly switches from the empty
graph to the complete graph as the expected edge probability
$\mathbb{E}\left[p_{ij}\right]$ becomes larger than $1/2$.

##  4 Discussion and Conclusion

In this work we derived the expression for the population Fréchet mean for
inhomogeneous Erdős-Rényi random graphs. We proved that the sample Fréchet
mean was consistent, and could be estimated using a simple thresholding rule.
Our results have several practical implications.

First, our work implies that the sample Fréchet mean computed from a training
set of graphs, which display specific topological features of interest, will
not inherit from the training set the desired topological structure. Indeed,
in the context of inhomogeneous Erdős-Rényi random graphs, the (population or
sample) Fréchet mean graph no longer captures the edge density encoded by the
edge probability.

Our answer to the question of the authors in [25]: “what is the “mean” network
(rather than how do we estimate the success-probabilities of an inhomogeneous
random graph), and do we want the “mean” itself to be a network?” is therefore
disappointing in the context of the probability space
$\mathcal{G}\mspace{-1.0mu}\big{(}\mspace{-2.0mu}n,\bm{P}\mspace{-1.0mu}\big{)}$.
While the Fréchet mean is indeed an element of
$\mathcal{G}\mspace{-1.0mu}\big{(}\mspace{-2.0mu}n,\bm{P}\mspace{-1.0mu}\big{)}$,
it only provides a simplistic sketch of that probability space. Consider for
instance sparse graphs where $\min p_{ij}<1/2$ (e.g., graphs with
${\scriptstyle\mathcal{O}}\left(n^{2}\right)$ but $\omega(n)$ edges), then the
sample Fréchet mean is the empty graph, and is pointless.

On a more positive note, our analysis provides a theoretical justification for
several algorithms designed to recover a graph from noisy measurements of its
adjacency matrix. For instance, the authors in [21] devise a method to recover
a fixed network from unlabeled noisy samples. Instead of estimating the
Fréchet mean, they compute the sample mean of the noisy adjacency matrices,
and threshold the sample mean to recover an unweighted graph.

Our results offer a theoretical justification of the approach of [21], if one
assumes that the noisy graphs are aligned and are realizations of
inhomogeneous Erdős-Rényi random graphs, with an unknown edge probability
matrix $\bm{P}$, then the algorithm described in [21] recovers the sample
Fréchet mean graph.

##  5 Proofs of the main results

We give in the following the proofs of theorems 1 and 2. In the process, we
prove several technical lemmata.

###  5.1 The Fréchet functions for the Hamming distance

We define the Fréchet functions, associated with the Fréchet median and mean,
and the sample Fréchet mean and median.

######  Definition 4.

We denote by $F_{q}$ the Fréchet function associated with the Fréchet median
($q=1$) or mean ($q=2$),

$F_{q}(\bm{B})=\sum_{\bm{A}\in\mathcal{S}}d^{q}_{H}(\bm{A},\bm{B})\mspace{2.0mu}\mathbb{P}\mspace{-2.0mu}\left(\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\right).$
(15)

We denote by $\widehat{F}_{q}$ the sample Fréchet function associated with the
sample Fréchet median ($q=1$) or mean ($q=2$),

$\widehat{F}_{q}\mspace{-4.0mu}\left(\bm{B}\right)=\frac{1}{N}\sum_{k=1}^{N}d^{q}_{H}(\bm{A}^{(k)},\bm{B}).$
(16)

Let $\bm{A}$ and $\bm{B}$ be two adjacency matrices in $\mathcal{S}$. We
derive in the following lemma an expression for the Hamming distance squared,
$d^{2}_{H}(\bm{A},\bm{B})$ where the computation is split between the entries
of $\bm{A}$ along the edges of $\bm{B}$, $\mathcal{E}(\bm{B})$, and the
entries of $\bm{A}$ along the “nonedges” of $\bm{B}$,
$\overline{\mathcal{E}}(\bm{B})$. We denote by
$\mspace{-2.0mu}\left\lvert\mathcal{E}(\bm{B})\right\rvert\mspace{-2.0mu}$ the
number of edges in $\bm{B}$.

######  Lemma 2.

Let $\bm{A}$ and $\bm{B}$ two matrices in $\mathcal{S}$. Then,

$\displaystyle d^{2}_{H}(\bm{A},\bm{B})=$ $\displaystyle\bigg{[}\sum_{1\leq
i<j\leq
n}\mspace{-16.0mu}a_{ij}\bigg{]}^{2}\mspace{-8.0mu}+\mspace{-2.0mu}\left\lvert\mathcal{E}(\bm{B})\right\rvert\mspace{-2.0mu}^{2}+2\mspace{-2.0mu}\left\lvert\mathcal{E}(\bm{B})\right\rvert\mspace{-2.0mu}\bigg{[}\sum_{(i,j)\in\overline{\mathcal{E}}(\bm{B})}\mspace{-16.0mu}a_{ij}-\mspace{-16.0mu}\sum_{(i,j)\in\mathcal{E}(\bm{B})}\mspace{-16.0mu}a_{ij}\bigg{]}$
$\displaystyle-4\mspace{-8.0mu}\sum_{(i,j)\in\mathcal{E}(\bm{B})}\mspace{-2.0mu}\sum_{(i^{\prime},j^{\prime})\in\overline{\mathcal{E}}(\bm{B})}\mspace{-16.0mu}a_{ij}a_{i^{\prime}j^{\prime}}$
(17)

The proof of (17) is elementary, and is omitted. As explained in the next
lemma, the values $F_{1}(\bm{B})$ and $F_{2}(\bm{B})$ depend only on the
entries of the probability matrix $\bm{P}$ along edges of $\bm{B}$.

######  Lemma 3.

Let $\bm{B}\in\mathcal{S}$, let $\mathcal{E}(\bm{B})$ be the set of edges of
the graph associated to $\bm{B}$. Then

$F_{1}(\bm{B})=\sum_{(i,j)\in\mathcal{E}(\bm{B})}\mspace{-12.0mu}(1-2p_{ij})+\mspace{-8.0mu}\sum_{1\leq
i<j\leq n}\mspace{-12.0mu}p_{ij}.$ (18)
$F_{2}(\bm{B})=\left[\sum_{(i,j)\in\mathcal{E}(\bm{B})}\left(1-2p_{ij}\right)+\mspace{-12.0mu}\sum_{1\leq
i<j\leq n}\mspace{-8.0mu}p_{ij}\right]^{2}+\sum_{1\leq i<j\leq
n}p_{ij}(1-p_{ij}).$ (19)

###### Proof.

We use lemma 2, and take the expectation with respect to the probability
measure $\operatorname{\mathbb{P}}$, on both sides of equation (17)

$\displaystyle\sum_{\bm{A}\in\mathcal{S}}d^{2}_{H}(\bm{A},\bm{B})\mspace{2.0mu}\mathbb{P}\mspace{-2.0mu}\left(\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\right)=$
$\displaystyle\sum_{\bm{A}\in\mathcal{S}}\left[\sum_{1\leq i<j\leq
n}a_{ij}\right]^{2}\mspace{-12.0mu}\mspace{2.0mu}\mathbb{P}\mspace{-2.0mu}\left(\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\right)+\mspace{-2.0mu}\left\lvert\mathcal{E}(\bm{B})\right\rvert\mspace{-2.0mu}^{2}$
(20)
$\displaystyle-4\mspace{-8.0mu}\sum_{(i,j)\in\mathcal{E}(\bm{B})}\sum_{(i^{\prime},j^{\prime})\in\overline{\mathcal{E}}(\bm{B})}\sum_{\bm{A}\in\mathcal{S}}a_{ij}a_{i^{\prime}j^{\prime}}\mspace{2.0mu}\mathbb{P}\mspace{-2.0mu}\left(\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\right)$
(21)
$\displaystyle+2\mspace{-2.0mu}\left\lvert\mathcal{E}(\bm{B})\right\rvert\mspace{-2.0mu}\left[\sum_{(i,j)\in\overline{\mathcal{E}}(\bm{B})}\sum_{\bm{A}\in\mathcal{S}}a_{ij}\mspace{2.0mu}\mathbb{P}\mspace{-2.0mu}\left(\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\right)-\sum_{(i,j)\in\mathcal{E}(\bm{B})}\sum_{\bm{A}\in\mathcal{S}}a_{ij}\mspace{2.0mu}\mathbb{P}\mspace{-2.0mu}\left(\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\right)\right].$
(22)

Now, the expectation of $a_{ij}$ is given by

$\mathbb{E}\left[a_{ij}\right]=\sum_{\bm{A}\in\mathcal{S}}a_{ij}\mspace{2.0mu}\mathbb{P}\mspace{-2.0mu}\left(\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\right)=p_{ij},$
(23)

and because the edges $(i,j)\in\mathcal{E}(\bm{B})$ and
$(i^{\prime},j^{\prime})\in\overline{\mathcal{E}}(\bm{B})$ are independent,

$\mathbb{E}\left[a_{ij}a_{i^{\prime}j^{\prime}}\right]=\sum_{\bm{A}\in\mathcal{S}}a_{ij}a_{i^{\prime}j^{\prime}}\mspace{2.0mu}\mathbb{P}\mspace{-2.0mu}\left(\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\right)=p_{ij}p_{i^{\prime}j^{\prime}}.$
(24)

Therefore (21) becomes

$-4\mspace{-8.0mu}\sum_{(i,j)\in\mathcal{E}(\bm{B})}\sum_{(i^{\prime},j^{\prime})\in\overline{\mathcal{E}}(\bm{B})}\sum_{\bm{A}\in\mathcal{S}}a_{ij}a_{i^{\prime}j^{\prime}}\mspace{2.0mu}\mathbb{P}\mspace{-2.0mu}\left(\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\right)=-4\left[\sum_{(i,j)\in\mathcal{E}(\bm{B})}p_{ij}\right]\left[\sum_{(i^{\prime},j^{\prime})\in\overline{\mathcal{E}}(\bm{B})}p_{i^{\prime}j^{\prime}}\right]$
(25)

Using (23) one more time, (22) is equal to,

$\displaystyle
2\mspace{-2.0mu}\left\lvert\mathcal{E}(\bm{B})\right\rvert\mspace{-2.0mu}$
$\displaystyle\left[\sum_{(i,j)\in\overline{\mathcal{E}}(\bm{B})}\sum_{\bm{A}\in\mathcal{S}}a_{ij}\mspace{2.0mu}\mathbb{P}\mspace{-2.0mu}\left(\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\right)-\sum_{(i,j)\in\mathcal{E}(\bm{B})}\sum_{\bm{A}\in\mathcal{S}}a_{ij}\mspace{2.0mu}\mathbb{P}\mspace{-2.0mu}\left(\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\right)\right]$
(26) $\displaystyle=$ $\displaystyle
2\mspace{-2.0mu}\left\lvert\mathcal{E}(\bm{B})\right\rvert\mspace{-2.0mu}\left[\sum_{(i,j)\in\overline{\mathcal{E}}(\bm{B})}p_{ij}\right]-2\mspace{-2.0mu}\left\lvert\mathcal{E}(\bm{B})\right\rvert\mspace{-2.0mu}\left[\sum_{(i,j)\in\mathcal{E}(\bm{B})}p_{ij}\right]$
(27)

The first term in the righthand side of (20) can be evaluated to give

$\sum_{\bm{A}\in\mathcal{S}}\left[\sum_{1\leq i<j\leq
n}a_{ij}\right]^{2}\mspace{2.0mu}\mathbb{P}\mspace{-2.0mu}\left(\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\right)=\sum_{1\leq
i<j\leq n}\mspace{4.0mu}\sum_{1\leq i^{\prime}<j^{\prime}\leq
n}\mspace{4.0mu}\sum_{\bm{A}\in\mathcal{S}}a_{ij}\;a_{i^{\prime}j^{\prime}}\mspace{2.0mu}\mathbb{P}\mspace{-2.0mu}\left(\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\right),$
(28)

where

$\sum_{\bm{A}\in\mathcal{S}}a_{ij}a_{i^{\prime}j^{\prime}}\mspace{2.0mu}\mathbb{P}\mspace{-2.0mu}\left(\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\right)=\mathbb{E}\left[a_{ij}a_{i^{\prime}j^{\prime}}\right]=\begin{cases}\mathbb{E}\left[a_{ij}\right]\mathbb{E}\left[a_{i^{\prime}j^{\prime}}\right]=p^{2}_{ij}&\text{if
$(i,j)\neq(i^{\prime},j^{\prime})$,}\\\
\mathbb{E}\left[a_{ij}^{2}\right]=\mathbb{E}\left[a_{ij}\right]=p_{ij}&\text{if
$(i,j)=(i^{\prime},j^{\prime})$.}\end{cases}$ (29)

We conclude that

$\sum_{\bm{A}\in\mathcal{S}}\left[\sum_{1\leq i<j\leq
n}a_{ij}\right]^{2}\mspace{-12.0mu}\mspace{2.0mu}\mathbb{P}\mspace{-2.0mu}\left(\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\right)=\mspace{-12.0mu}\sum_{1\leq
i<j\leq n}\mspace{4.0mu}\sum_{\stackrel{{\scriptstyle 1\leq
i^{\prime}<j^{\prime}\leq
n}}{{(i,j)\neq(i^{\prime},j^{\prime})}}}\mspace{-16.0mu}p^{2}_{ij}+\mspace{-8.0mu}\sum_{1\leq
i<j\leq n}\mspace{-8.0mu}p_{ij}=\left[\sum_{1\leq i<j\leq
n}\mspace{-8.0mu}p_{ij}\right]^{2}\mspace{-8.0mu}+\mspace{-12.0mu}\sum_{1\leq
i<j\leq n}\mspace{-8.0mu}p_{ij}(1-p_{ij}).$ (30)

We can substitute (25), (27), and (30) into (21), (22), and (20) respectively,
and we get

$\displaystyle\sum_{\bm{A}\in\mathcal{S}}d^{2}_{H}(\bm{A},\bm{B})\mspace{2.0mu}\mathbb{P}\mspace{-2.0mu}\left(\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\right)=$
$\displaystyle\left[\sum_{1\leq i<j\leq n}p_{ij}\right]^{2}+2\left[\sum_{1\leq
i<j\leq
n}p_{ij}\right]\left[\sum_{(i,j)\in\mathcal{E}(\bm{B})}\mspace{-12.0mu}(1-2p_{ij})\right]$
$\displaystyle+$
$\displaystyle\left[\sum_{(i,j)\in\mathcal{E}(\bm{B})}\mspace{-12.0mu}(1-2p_{ij})\right]^{2}+\sum_{1\leq
i<j\leq n}p_{ij}(1-p_{ij})$ $\displaystyle=$
$\displaystyle\left[\sum_{(i,j)\in\mathcal{E}(\bm{B})}\mspace{-12.0mu}(1-2p_{ij})+\sum_{1\leq
i<j\leq n}\mspace{-12.0mu}p_{ij}\right]^{2}+\sum_{1\leq i<j\leq
n}p_{ij}(1-p_{ij}),$ (31)

which matches the expression (19). ∎

###  5.2 The Fréchet mean and median of
$\mathcal{G}\big{(}n,\mathbf{P}\big{)}$: proof of Theorem 1

We prove theorem 1 for the mean. The proof for the median is very similar; it
is in fact simpler and is therefore omitted. By lemma 3, we seek the matrix
$\bm{B}$, with edge set $\mathcal{E}(\bm{B})$, that minimizes the Fréchet
function defined by (19). Let us denote

$x\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\mspace{-12.0mu}\sum_{(i,j)\in\mathcal{E}(\bm{B})}\left(1-2p_{ij}\right).$
(32)

The variable $x$ is clearly a function of $\bm{B}$, and $\bm{P}$. To avoid
unnecessary complicated notations, we keep these dependencies implicit in our
exposition. Since $0\leq p_{ij}\leq 1$, $x$ is confined to the following
interval,

$-\mspace{-12.0mu}\sum_{1\leq i<j\leq
n}p_{ij}\leq-\mspace{-12.0mu}\sum_{(i,j)\in\mathcal{E}(\bm{B})}p_{ij}\leq
x\leq\sum_{(i,j)\in\mathcal{E}(\bm{B})}\mspace{-16.0mu}1\mspace{8.0mu}\leq
n(n-1)/2.$ (33)

In fact, $x=-\sum_{1\leq i<j\leq n}p_{ij}$, only if $\forall
i,j\in[n],\;p_{ij}=1$, and the graph associated to $\bm{B}$ in (32) is the
complete graph. This case is of no interest to us, and thus we can assume that
$\bm{P}$ is always chosen such that

$-\mspace{-16.0mu}\sum_{1\leq i<j\leq n}p_{ij}<x.$ (34)

We define,

$f(x)\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}\left[x+\sum_{1\leq i<j\leq
n}p_{ij}\right]^{2},$

and we have

$f(x)=F_{2}(\bm{B})-\sum_{1\leq i<j\leq n}p_{ij}(1-p_{ij}).$

Minimizing $F_{2}$ is therefore equivalent to minimizing $f$. Clearly, $f(x)$
is convex, has a global minimum at $x_{\min{}}=-\sum_{1\leq i<j\leq n}p_{ij}$,
and is increasing for $x\geq-\sum_{1\leq i<j\leq n}p_{ij}$. We seek $x^{*}$
that minimizes $f(x)$ over the interval wherein $x$ is enclosed,

$\bigg{(}-\sum_{1\leq i<j\leq n}p_{ij},\;n(n-1)/2\bigg{]}.$

We note that because of (34), $x_{\min{}}<x^{\ast}$. Also, $x^{*}$ cannot be
positive; otherwise, we would get $f(x^{*})>f(0)$. The optimal value $x^{*}$
is obtained by minimizing the distance from $x^{*}$ to $-\sum_{1\leq i<j\leq
n}p_{ij}$,

$x^{\ast}-(-\mspace{-16.0mu}\sum_{1\leq i<j\leq
n}p_{ij})=\mspace{-24.0mu}\sum_{(i,j)\in\mathcal{E}(\bm{B})}\mspace{-16.0mu}(1-2p_{ij})+\mspace{-16.0mu}\sum_{1\leq
i<j\leq
n}\mspace{-8.0mu}p_{ij}\geq\mspace{-24.0mu}\sum_{(i,j);1-2p_{ij}<0}\mspace{-24.0mu}\left(1-2p_{ij}\right)+\mspace{-16.0mu}\sum_{1\leq
i<j\leq n}p_{ij}.$ (35)

The lower bound (35) is independent of $\bm{B}$, and can be obtained by
choosing,

$\bm{\mu}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\bm{A}\mspace{-2.0mu}\big{]}_{ij}=\begin{cases}1&\text{if}\quad
p_{ij}>1/2,\\\ 0&\text{otherwise,}\end{cases}$ (36)

as advertised in the theorem. ∎

###  5.3 The sample Fréchet functions for the Hamming distance

We now consider $N$ independent random graphs,
$\left\\{G^{(k)}\right\\}_{1\leq k\leq N}$, sampled from
$\mathcal{G}\mspace{-1.0mu}\big{(}\mspace{-2.0mu}n,\bm{P}\mspace{-1.0mu}\big{)}$,
with adjacency matrices $\bm{A}^{(k)}$. The sample Fréchet functions
associated with the sample Fréchet mean and median graph are given by the next
lemma, which corresponds to the sample version of lemma 3.

######  Lemma 4.

Let $\bm{B}\in\mathcal{S}$, let $\mathcal{E}(\bm{B})$ be the set of edges of
the graph associated to $\bm{B}$. Then

$\widehat{F}_{1}\mspace{-4.0mu}\left(\bm{B}\right)=\sum_{(i,j)\in\mathcal{E}(\bm{B})}\left(1-2\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\right)+\mspace{-12.0mu}\sum_{1\leq
i<j\leq n}\mspace{-8.0mu}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]$ (37)
$\displaystyle\widehat{F}_{2}\mspace{-4.0mu}\left(\bm{B}\right)=$
$\displaystyle\left[\sum_{(i,j)\in\mathcal{E}(\bm{B})}\mspace{-8.0mu}\left(1-2\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\right)+\mspace{-8.0mu}\sum_{1\leq
i<j\leq
n}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\right]^{2}\mspace{-12.0mu}+\mspace{-12.0mu}\sum_{1\leq
i<j\leq
n}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\left(1-\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\right)$
$\displaystyle\mspace{16.0mu}-\sum_{1\leq i<j\leq
n}\mspace{8.0mu}\sum_{\stackrel{{\scriptstyle 1\leq i^{\prime}<j^{\prime}\leq
n}}{{(i,j)\neq(i^{\prime},j^{\prime})}}}\left(\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\widehat{\mathbb{E}}_{N}\left[a_{i^{\prime}j^{\prime}}\right]-\widehat{\mathbb{E}}_{N}\left[\rho_{ij,i^{\prime}j^{\prime}}\right]\right)$
$\displaystyle+4\sum_{(i,j)\in\mathcal{E}(\bm{B})}\sum_{(i^{\prime},j^{\prime})\in\overline{\mathcal{E}}(\bm{B})}\left(\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\widehat{\mathbb{E}}_{N}\left[a_{i^{\prime}j^{\prime}}\right]-\widehat{\mathbb{E}}_{N}\left[\rho_{ij,i^{\prime}j^{\prime}}\right]\right)$
(38)

where the sample mean and sample correlation are defined by

$\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]=\frac{1}{N}\sum_{k=1}^{N}a^{(k)}_{ij}\quad\text{and}\quad\widehat{\mathbb{E}}_{N}\left[\rho_{ij,i^{\prime}j^{\prime}}\right]=\frac{1}{N}\sum_{k=1}^{N}a^{(k)}_{ij}a^{(k)}_{i^{\prime}j^{\prime}}$
(39)

###### Proof.

We prove (38), the proof of (37) is much simpler and is omitted. The proof of
(38) is similar to the proof of lemma 3. For each graph $G^{(k)}$, we apply
equation (17), we sum over all the graphs in the sample, and divide by $N$ to
get

$\displaystyle\widehat{F}_{2}\mspace{-4.0mu}\left(\bm{B}\right)=$
$\displaystyle\mspace{-2.0mu}\left\lvert\mathcal{E}(\bm{B})\right\rvert\mspace{-2.0mu}^{2}+2\mspace{-2.0mu}\left\lvert\mathcal{E}(\bm{B})\right\rvert\mspace{-2.0mu}\left[\sum_{(i,j)\in\overline{\mathcal{E}}(\bm{B})}\frac{1}{N}\sum_{k=1}^{N}a^{(k)}_{ij}-\sum_{(i,j)\in\mathcal{E}(\bm{B})}\frac{1}{N}\sum_{k=1}^{N}a^{(k)}_{ij}\right]$
(40) $\displaystyle+$ $\displaystyle\frac{1}{N}\sum_{k=1}^{N}\left[\sum_{1\leq
i<j\leq
n}a^{(k)}_{ij}\right]^{2}-4\sum_{(i,j)\in\overline{\mathcal{E}}(\bm{B})}\sum_{(i^{\prime},j^{\prime})\in\mathcal{E}(\bm{B})}\left[\frac{1}{N}\sum_{k=1}^{N}a^{(k)}_{ij}a^{(k)}_{i^{\prime}j^{\prime}}\right]$
(41)

Using the expressions for the sample mean and correlation, in (39), we get

$\displaystyle\widehat{F}_{2}\mspace{-4.0mu}\left(\bm{B}\right)=$
$\displaystyle\mspace{-2.0mu}\left\lvert\mathcal{E}(\bm{B})\right\rvert\mspace{-2.0mu}^{2}+2\mspace{-2.0mu}\left\lvert\mathcal{E}(\bm{B})\right\rvert\mspace{-2.0mu}\Big{[}\mspace{-16.0mu}\sum_{(i,j)\in\overline{\mathcal{E}}(\bm{B})}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]-\sum_{(i,j)\in\mathcal{E}(\bm{B})}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\Big{]}+\frac{1}{N}\sum_{k=1}^{N}\Big{[}\mspace{-8.0mu}\sum_{1\leq
i<j\leq n}a^{(k)}_{ij}\Big{]}^{2}$ $\displaystyle-$ $\displaystyle
4\sum_{(i,j)\in\overline{\mathcal{E}}(\bm{B})}\sum_{(i^{\prime},j^{\prime})\in\mathcal{E}(\bm{B})}\mspace{-16.0mu}\widehat{\mathbb{E}}_{N}\left[\rho_{ij,i^{\prime}j^{\prime}}\right]$
(43)

We note that

$\frac{1}{N}\sum_{k=1}^{N}\Big{[}\mspace{-8.0mu}\sum_{1\leq i<j\leq
n}a^{(k)}_{ij}\Big{]}^{2}=\mspace{-12.0mu}\sum_{1\leq i<j\leq n}\;\sum_{1\leq
i^{\prime}<j^{\prime}\leq
n}\frac{1}{N}\sum_{k=1}^{N}a^{(k)}_{ij}a^{(k)}_{i^{\prime}j^{\prime}}=\mspace{-12.0mu}\sum_{1\leq
i<j\leq n}\;\sum_{1\leq i^{\prime}<j^{\prime}\leq
n}\mspace{-16.0mu}\widehat{\mathbb{E}}_{N}\left[\rho_{ij,i^{\prime}j^{\prime}}\right]$
(44)

Also, we have

$\displaystyle\mspace{-2.0mu}\left\lvert\mathcal{E}(\bm{B})\right\rvert\mspace{-2.0mu}^{2}$
$\displaystyle+2\mspace{-2.0mu}\left\lvert\mathcal{E}(\bm{B})\right\rvert\mspace{-2.0mu}\bigg{[}\mspace{-4.0mu}\sum_{(i,j)\in\overline{\mathcal{E}}(\bm{B})}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]-\sum_{(i,j)\in\mathcal{E}(\bm{B})}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\bigg{]}$
$\displaystyle=$
$\displaystyle\bigg{[}\mspace{-2.0mu}\left\lvert\mathcal{E}(\bm{B})\right\rvert\mspace{-2.0mu}-2\mspace{-12.0mu}\sum_{(i,j)\in\mathcal{E}(\bm{B})}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\bigg{]}^{2}-\mspace{-12.0mu}\sum_{1\leq
i<j\leq n}\;\sum_{1\leq i^{\prime}<j^{\prime}\leq
n}\mspace{-16.0mu}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\widehat{\mathbb{E}}_{N}\left[a_{i^{\prime}j^{\prime}}\right]$
$\displaystyle+4\mspace{-12.0mu}\sum_{(i,j)\in\overline{\mathcal{E}}(\bm{B})}\sum_{(i^{\prime},j^{\prime})\in\mathcal{E}(\bm{B})}\mspace{-16.0mu}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\widehat{\mathbb{E}}_{N}\left[a_{i^{\prime}j^{\prime}}\right]$
(45)

We can then substitute (44) and (45) into (43), and we get

$\displaystyle\widehat{F}_{2}\mspace{-4.0mu}\left(\bm{B}\right)$
$\displaystyle=\bigg{[}\mspace{-2.0mu}\left\lvert\mathcal{E}(\bm{B})\right\rvert\mspace{-2.0mu}-2\mspace{-12.0mu}\sum_{(i,j)\in\mathcal{E}(\bm{B})}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\bigg{]}^{2}\mspace{-8.0mu}-\mspace{-16.0mu}\sum_{1\leq
i<j\leq n}\;\sum_{1\leq i^{\prime}<j^{\prime}\leq
n}\mspace{-8.0mu}\Big{[}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\widehat{\mathbb{E}}_{N}\left[a_{i^{\prime}j^{\prime}}\right]-\widehat{\mathbb{E}}_{N}\left[\rho_{ij,i^{\prime}j^{\prime}}\right]\Big{]}$
$\displaystyle+4\mspace{-12.0mu}\sum_{(i,j)\in\overline{\mathcal{E}}(\bm{B})}\sum_{(i^{\prime},j^{\prime})\in\mathcal{E}(\bm{B})}\mspace{-16.0mu}\Big{[}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\widehat{\mathbb{E}}_{N}\left[a_{i^{\prime}j^{\prime}}\right]-\widehat{\mathbb{E}}_{N}\left[\rho_{ij,i^{\prime}j^{\prime}}\right]\Big{]}$
(46)

Finally, we can extract from the second term in the first line of (46) the
term that corresponds to $(i,j)=(i^{\prime},j^{\prime})$,

$\displaystyle\sum_{1\leq i<j\leq n}\sum_{1\leq i^{\prime}<j^{\prime}\leq
n}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\widehat{\mathbb{E}}_{N}\left[a_{i^{\prime}j^{\prime}}\right]-\widehat{\mathbb{E}}_{N}\left[\rho_{ij,i^{\prime}j^{\prime}}\right]$
$\displaystyle=\mspace{-8.0mu}\sum_{1\leq i<j\leq
n}\sum_{\stackrel{{\scriptstyle 1\leq i^{\prime}<j^{\prime}\leq
n}}{{(i^{\prime},j^{\prime})\neq(i,j)}}}\mspace{-8.0mu}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\widehat{\mathbb{E}}_{N}\left[a_{i^{\prime}j^{\prime}}\right]-\widehat{\mathbb{E}}_{N}\left[\rho_{ij,i^{\prime}j^{\prime}}\right]+\mspace{-16.0mu}\sum_{1\leq
i<j\leq
n}\mspace{-16.0mu}\widehat{\mathbb{E}}_{N}\left[a_{a_{ij}}\right]\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]-\widehat{\mathbb{E}}_{N}\left[\rho_{ij,ij}\right],$
(47)

Now if $(i,j)=(i^{\prime},j^{\prime})$ we have

$\widehat{\mathbb{E}}_{N}\left[\rho_{ij,ij}\right]=\sum_{k=1}^{N}a^{(k)}_{ij}a^{(k)}_{ij}=\sum_{k=1}^{N}a^{(k)}_{ij}=\widehat{\mathbb{E}}_{N}\left[a_{ij}\right],$
(48)

and therefore

$\displaystyle\sum_{1\leq i<j\leq n}\sum_{1\leq i^{\prime}<j^{\prime}\leq
n}\left[\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\widehat{\mathbb{E}}_{N}\left[a_{i^{\prime}j^{\prime}}\right]-\widehat{\mathbb{E}}_{N}\left[\rho_{ij,i^{\prime}j^{\prime}}\right]\right]$
$\displaystyle=\sum_{1\leq i<j\leq n}\;\sum_{\stackrel{{\scriptstyle 1\leq
i^{\prime}<j^{\prime}\leq
n}}{{(i^{\prime},j^{\prime})\neq(i,j)}}}\mspace{-12.0mu}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\widehat{\mathbb{E}}_{N}\left[a_{i^{\prime}j^{\prime}}\right]-\widehat{\mathbb{E}}_{N}\left[\rho_{ij,i^{\prime}j^{\prime}}\right]+\mspace{-12.0mu}\sum_{1\leq
i<j\leq
n}\mspace{-12.0mu}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\left(\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]-1\right)$
(49)

Substituting (49) into (46), we obtain the result advertised in the lemma. ∎

###  5.4 Concentration of the sample Fréchet functions for large sample size

In the following two lemmata, we show that for large $N$, the sample Fréchet
functions $\widehat{F}_{1}$ and $\widehat{F}_{2}$ concentrate around their
population counterparts, $F_{1}$ and $F_{2}$.

######  Lemma 5.

For all $\delta\in(0,1)$, there exists $N_{\delta}$, such that for all $N\geq
N_{\delta}$,

$\widehat{F}_{1}\mspace{-4.0mu}\left(\bm{B}\right)=\sum_{(i,j)\in\mathcal{E}(\bm{B})}\mspace{-8.0mu}\left(1-2p_{ij}\right)+\mspace{-8.0mu}\sum_{1\leq
i<j\leq n}p_{ij}+{\mathcal{O}}\mspace{-4.0mu}\left(\frac{1}{\sqrt{N}}\right),$
(50)

with probability $1-\delta$ over the realization of the sample
$\left\\{G^{(k)}\right\\}_{1\leq k\leq N}$ .

###### Proof.

The sample mean $\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]$, defined in
(39), is the sum of Bernoulli random variables, and it concentrates around its
mean $p_{ij}$. We use Hoeffding inequality to bound the variation of
$\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]$ around $p_{ij}$. For each $1\leq
i<j\leq n$, we have,

$\mspace{2.0mu}\mathbb{P}\mspace{-2.0mu}\left(\mspace{-2.0mu}\mspace{-4.0mu}\bm{A}^{(k)}\sim\mathcal{G}\mspace{-1.0mu}\big{(}\mspace{-2.0mu}n,\bm{P}\mspace{-1.0mu}\big{)};\left\lvert\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]-p_{ij}\right\rvert\geq\varepsilon\mspace{-2.0mu}\right)\leq\exp{\displaystyle\left(-2N\varepsilon^{2}\right)}.$
(51)

To control $\sum_{k=1}^{N}a^{(k)}_{ij}$ for all $1\leq i<j<n$, we use a union
bound, and we get,

$\forall 1\leq
i<j<n,\quad\left\lvert\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]-p_{ij}\right\rvert\leq\frac{\alpha}{\sqrt{N}},$
(52)

with probability $1-\delta$, and where $\alpha=\sqrt{\log(n/\sqrt{2\delta})}$.
From (52), and for $N$ large enough we obtain the result announced in the
lemma,

$\sum_{(i,j)\in\mathcal{E}(\bm{B})}\mspace{-12.0mu}\left(1-2\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\right)+\mspace{-16.0mu}\sum_{1\leq
i<j\leq
n}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]=\mspace{-24.0mu}\sum_{(i,j)\in\mathcal{E}(\bm{B})}\mspace{-8.0mu}\left(1-2p_{ij}\right)+\mspace{-16.0mu}\sum_{1\leq
i<j\leq
n}\mspace{-8.0mu}p_{ij}+{\mathcal{O}}\mspace{-4.0mu}\left(\frac{1}{\sqrt{N}}\right),$
(53)

with probability $1-\delta$. ∎

Similarly, we show in the following lemma that for large sample size $N$, the
sample Fréchet function $\widehat{F}_{2}\mspace{-4.0mu}\left(\bm{B}\right)$
concentrates around its population counterpart, $F_{2}(\bm{B})$.

######  Lemma 6.

For all $\delta\in(0,1)$, there exists $N_{\delta}$, such that for all $N\geq
N_{\delta}$,

$\widehat{F}_{2}\mspace{-4.0mu}\left(\bm{B}\right)=\left[\sum_{(i,j)\in\mathcal{E}(\bm{B})}\mspace{-8.0mu}\left(1-2p_{ij}\right)+\mspace{-8.0mu}\sum_{1\leq
i<j\leq n}p_{ij}\right]^{2}\mspace{-12.0mu}+\mspace{-12.0mu}\sum_{1\leq
i<j\leq
n}p_{ij}\left(1-p_{ij}\right)+{\mathcal{O}}\mspace{-4.0mu}\left(\frac{1}{\sqrt{N}}\right),$
(54)

with probability $1-\delta$ over the realization of the sample
$\left\\{G^{(k)}\right\\}_{1\leq k\leq N}$ .

###### Proof.

We have seen in the proof of lemma 5 that the sample mean concentrates around
its population mean. From (52) we have,

$\forall 1\leq
i<j<n,\quad\left\lvert\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]-p_{ij}\right\rvert\leq\frac{\alpha}{\sqrt{N}}.$
(55)

with probability $1-\delta/8$, and where
$\alpha=\sqrt{\log{(2n/\sqrt{\delta}})}$. We now study the concentration of
the sample correlation,

$\widehat{\mathbb{E}}_{N}\left[\rho_{ij,i^{\prime}j^{\prime}}\right]=\frac{1}{N}\sum_{k=1}^{N}a^{(k)}_{ij}a^{(k)}_{i^{\prime}j^{\prime}},$
(56)

when the pair of edges are distinct. Because
$(i,j)\neq(i^{\prime},j^{\prime})$, the terms $a^{(k)}_{ij}$ and
$a^{(k)}_{i^{\prime}j^{\prime}}$ are always independent, and the product
$a^{(k)}_{ij}a^{(k)}_{i^{\prime}j^{\prime}}$ is a Bernoulli random variable
with parameter $p_{ij}p_{i^{\prime}j^{\prime}}$. We conclude that the sample
correlation is the sum of Bernoullli random variables, and thus it
concentrates around its mean, $p_{ij}p_{i^{\prime}j^{\prime}}$.

$\forall\;1\leq i<j\leq n,\mspace{4.0mu}\forall\;1\leq
i^{\prime}<j^{\prime}\leq
n,\;\left\lvert\widehat{\mathbb{E}}_{N}\left[\rho_{ij,i^{\prime}j^{\prime}}\right]-p_{ij}p_{i^{\prime}j^{\prime}}\right\rvert\leq\frac{\beta}{\sqrt{N}}$
(57)

with probability $1-\delta/8$, where
$\beta=\sqrt{\log{(n^{2}/\sqrt{\delta/2})}}$. In summary, we have

$\displaystyle\forall\;1\leq i<j\leq n,\quad\forall\;1\leq
i^{\prime}<j^{\prime}\leq n,$
$\displaystyle\quad\text{with}\quad(i,j)\neq(i^{\prime},j^{\prime}),$
$\displaystyle\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]=p_{ij}+{\mathcal{O}}\mspace{-4.0mu}\left(\frac{1}{\sqrt{N}}\right)\mspace{-4.0mu},\;$
$\displaystyle\text{and}\;\widehat{\mathbb{E}}_{N}\left[\rho_{ij,i^{\prime}j^{\prime}}\right]=p_{i^{\prime}j^{\prime}}+{\mathcal{O}}\mspace{-4.0mu}\left(\frac{1}{\sqrt{N}}\right),$
(58)

with probability $1-\delta/4$. We are now in position to substitute
$\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]$ and
$\widehat{\mathbb{E}}_{N}\left[\rho_{ij,i^{\prime}j^{\prime}}\right]$ with the
expressions given by (58), in
$\widehat{F}_{2}\mspace{-4.0mu}\left(\bm{B}\right)$ given by (38) in lemma 4.
Using (58), the first term in (38) becomes

$\displaystyle\bigg{[}\sum_{(i,j)\in\mathcal{E}(\bm{B})}\left(1-2\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\right)+\mspace{-16.0mu}\sum_{1\leq
i<j\leq n}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\bigg{]}^{2}$
$\displaystyle=\left[\sum_{(i,j)\in\mathcal{E}(\bm{B})}\mspace{-8.0mu}\left(1-2p_{ij}\right)+\mspace{-8.0mu}\sum_{1\leq
i<j\leq n}p_{ij}\right]^{2}$
$\displaystyle+{\mathcal{O}}\mspace{-4.0mu}\left(\frac{1}{\sqrt{N}}\right).$
(59)

with probability $1-\delta/4$. Also, we have

$\sum_{1\leq i<j\leq
n}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\left(1-\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\right)=\sum_{1\leq
i<j\leq
n}p_{ij}\left(1-p_{ij}\right)+{\mathcal{O}}\mspace{-4.0mu}\left(\frac{1}{\sqrt{N}}\right).$
(60)

with probability $1-\delta/4$. The last two terms in (38) can be neglected
since,

$\displaystyle\sum_{1\leq i<j\leq n}$
$\displaystyle\sum_{\stackrel{{\scriptstyle 1\leq i^{\prime}<j^{\prime}\leq
n}}{{(i,j)\neq(i^{\prime},j^{\prime})}}}\Big{[}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\widehat{\mathbb{E}}_{N}\left[a_{i^{\prime}j^{\prime}}\right]-\widehat{\mathbb{E}}_{N}\left[\rho_{ij,i^{\prime}j^{\prime}}\right]\Big{]}$
$\displaystyle=\sum_{1\leq i<j\leq n}\sum_{\stackrel{{\scriptstyle 1\leq
i^{\prime}<j^{\prime}\leq
n}}{{(i,j)\neq(i^{\prime},j^{\prime})}}}\mspace{-12.0mu}\Big{[}p_{ij}p_{i^{\prime}j^{\prime}}-p_{ij}p_{i^{\prime}j^{\prime}}\Big{]}+{\mathcal{O}}\mspace{-4.0mu}\left(\frac{1}{\sqrt{N}}\right)={\mathcal{O}}\mspace{-4.0mu}\left(\frac{1}{\sqrt{N}}\right),$
(61)

with probability $1-\delta/4$. Similarly

$\sum_{(i,j)\in\mathcal{E}(\bm{B})}\sum_{(i^{\prime},j^{\prime})\in\overline{\mathcal{E}}(\bm{B})}\widehat{\mathbb{E}}_{N}\left[a_{ij}\right]\widehat{\mathbb{E}}_{N}\left[a_{i^{\prime}j^{\prime}}\right]-\widehat{\mathbb{E}}_{N}\left[\rho_{ij,i^{\prime}j^{\prime}}\right]={\mathcal{O}}\mspace{-4.0mu}\left(\frac{1}{\sqrt{N}}\right),$
(62)

with probability $1-\delta/4$. Substituting (59), (60), (61), and (62) into
(38) yields the following estimate

$\widehat{F}_{2}\mspace{-4.0mu}\left(\bm{B}\right)=\bigg{[}\sum_{(i,j)\in\mathcal{E}(\bm{B})}\mspace{-16.0mu}\left(1-2p_{ij}\right)+\mspace{-16.0mu}\sum_{1\leq
i<j\leq
n}\mspace{-8.0mu}p_{ij}\bigg{]}^{2}\mspace{-8.0mu}+\mspace{-12.0mu}\sum_{1\leq
i<j\leq
n}\mspace{-16.0mu}p_{ij}\left(1-p_{ij}\right)+{\mathcal{O}}\mspace{-4.0mu}\left(\frac{1}{\sqrt{N}}\right),$

which holds with with probability $1-\delta$. ∎

###  5.5 Proof of Theorem 2

We prove (10), in theorem 2, for the sample Fréchet mean. The proof for the
sample Fréchet median is completely similar (it also uses a concentration of
measure argument for the Fréchet function defined in (7)) and is therefore
omitted. Because of lemma 6, (54) implies that

$\forall\delta\in(0,1),\exists N_{\delta},\forall N\geq
N_{\delta},\forall\bm{B}\in\mathcal{S},\mspace{32.0mu}\widehat{F}_{2}\mspace{-4.0mu}\left(\bm{B}\right)=F_{2}(\bm{B})+{\mathcal{O}}\mspace{-4.0mu}\left(\frac{1}{\sqrt{N}}\right),$

with probability $1-\delta$ over the realization of the sample
$\left\\{G^{(k)}\right\\}_{1\leq k\leq N}$. For $N$ large enough, the main
term dominates the expression of
$\widehat{F}_{2}\mspace{-4.0mu}\left(\bm{B}\right)$, and we can neglect the
${\mathcal{O}}\mspace{-4.0mu}\left(1/\sqrt{N}\right)$ term. We are left with
$F_{2}(\bm{B})$, the Fréchet function for the population mean, given by (19),
in lemma 3. The minimum of $\widehat{F}_{2}\mspace{-4.0mu}\left(\bm{B}\right)$
is thus achieved for the adjacency matrix given by the population Fréchet
mean,
$\bm{\mu}\mspace{-2.0mu}\big{[}\mspace{-2.0mu}\operatorname{\mathbb{P}}\mspace{-2.0mu}\big{]}$,
defined by (8), as advertised in (10), in theorem 2. ∎

## References

  * [1] Emmanuel Abbe, _Community detection and stochastic block models: recent developments_ , The Journal of Machine Learning Research 18 (2017), no. 1, 6446–6531.
  * [2] David Banks and GM Constantine, _Metric models for random graphs_ , Journal of Classification 15 (1998), no. 2, 199–223.
  * [3] Itziar Bardaji, Miquel Ferrer, and Alberto Sanfeliu, _Computing the barycenter graph by means of the graph edit distance_ , 2010 20th International Conference on Pattern Recognition, IEEE, 2010, pp. 962–965.
  * [4] Béla Bollobás, Svante Janson, and Oliver Riordan, _The phase transition in inhomogeneous random graphs_ , Random Structures & Algorithms 31 (2007), no. 1, 3–122.
  * [5] Jiehua Chen, Danny Hermelin, and Manuel Sorge, _On Computing Centroids According to the p-Norms of Hamming Distance Vectors_ , 27th Annual European Symposium on Algorithms (ESA 2019) (Dagstuhl, Germany), vol. 144, 2019, pp. 28:1–28:16.
  * [6] Samir Chowdhury and Facundo Mémoli, _The metric space of networks_ , 2018\.
  * [7] Paromita Dubey and Hans-Georg Müller, _Fréchet change-point detection_ , The Annals of Statistics 48 (2020), no. 6, 3312–3335.
  * [8] Miquel Ferrer, Ernest Valveny, and Francesc Serratosa, _Median graph: A new exact algorithm using a distance based on the maximum common subgraph_ , Pattern Recognition Letters 30 (2009), no. 5, 579–588.
  * [9] Miquel Ferrer, Ernest Valveny, Francesc Serratosa, Kaspar Riesen, and Horst Bunke, _Generalized median graph computation by means of graph embedding in vector spaces_ , Pattern Recognition 43 (2010), no. 4, 1642–1655.
  * [10] Santo Fortunato and Darko Hric, _Community detection in networks: A user guide_ , Physics reports 659 (2016), 1–44.
  * [11] Maurice Fréchet, _Les espaces abstraits et leur utilité en statistique théorique et même en statistique appliquée_ , Journal de la Société Française de Statistique 88 (1947), 410–421.
  * [12] Cedric E. Ginestet, Jun Li, Prakash Balachandran, Steven Rosenberg, and Eric D. Kolaczyk, _Hypothesis testing for network data in functional neuroimaging_ , The Annals of Applied Statistics 11 (2017), no. 2, 725–750.
  * [13] Anna Goldenberg, Alice X Zheng, Stephen E Fienberg, Edoardo M Airoldi, et al., _A survey of statistical network models_ , Foundations and Trends® in Machine Learning 2 (2010), no. 2, 129–233.
  * [14] Fang Han, Xiaoyan Han, Han Liu, Brian Caffo, et al., _Sparse median graphs estimation in a high-dimensional semiparametric model_ , The Annals of Applied Statistics 10 (2016), no. 3, 1397–1426.
  * [15] Brijnesh Jain and Klaus Obermayer, _On the sample mean of graphs_ , 2008 IEEE International Joint Conference on Neural Networks (IEEE World Congress on Computational Intelligence), IEEE, 2008, pp. 993–1000.
  * [16] Brijnesh J Jain, _On the geometry of graph spaces_ , Discrete Applied Mathematics 214 (2016), 126–144.
  * [17] , _Statistical graph space analysis_ , Pattern Recognition 60 (2016), 802–812.
  * [18] Brijnesh J Jain and Klaus Obermayer, _Algorithms for the sample mean of graphs_ , International Conference on Computer Analysis of Images and Patterns, Springer, 2009, pp. 351–359.
  * [19] , _Learning in Riemannian orbifolds_, 2012.
  * [20] Xiaoyi Jiang, Andreas Munger, and Horst Bunke, _On median graphs: properties, algorithms, and applications_ , IEEE Transactions on Pattern Analysis and Machine Intelligence 23 (2001), no. 10, 1144–1151.
  * [21] Nathaniel Josephs, Wenrui Li, and Eric D Kolaczyk, _Network recovery from unlabeled noisy samples_ , 2021.
  * [22] Eric D Kolaczyk, _Topics at the frontier of statistics and network analysis:(re) visiting the foundations_ , Cambridge University Press, 2017.
  * [23] Eric D Kolaczyk, Lizhen Lin, Steven Rosenberg, Jackson Walters, Jie Xu, et al., _Averages of unlabeled networks: Geometric characterization and asymptotic behavior_ , The Annals of Statistics 48 (2020), no. 1, 514–538.
  * [24] I.N. Kovalenko, _Theory of random graphs_ , Cybernetics 7 (1971), no. 4, 575–579.
  * [25] Simón Lunagómez, Sofia C Olhede, and Patrick J Wolfe, _Modeling network populations via graph distances_ , Journal of the American Statistical Association (2020), 1–18.
  * [26] François G. Meyer, _The fréchet mean of inhomogeneous random graphs_ , Complex Networks and Their Applications X, Springer, 2021, pp. 1–12.
  * [27] Lopamudra Mukherjee, Vikas Singh, Jiming Peng, Jinhui Xu, Michael J Zeitz, and Ronald Berezney, _Generalized median graphs and applications_ , Journal of Combinatorial Optimization 17 (2009), no. 1, 21–44.
  * [28] Berthold Schweizer, Abe Sklar, et al., _Statistical metric spaces_ , Pacific J. Math 10 (1960), no. 1, 313–334.
  * [29] Tom AB Snijders, _Statistical models for social networks_ , Annual review of sociology 37 (2011), 131–153.