The Fréchet mean of inhomogeneous random graphs (Q2086589): Difference between revisions

We are interested in what a typical graph in some family looks like. For example, suppose that we have the class \(\mathcal{G}\) of (undirected, simple) graphs on \([n]=\{1,2,\ldots n\}\) and let \(\mathcal{S}\) be the set of possible adjacency matrices \(A\) of such graphs (so all entries are 0 or 1, the matrix is symmetric with zeroes on the diagonal). We consider an inhomogeneous Erdős-Rényi graph, where a graph with adjacency matrix \(A=(a_{ij})\) has probability \(\mathbb{P}(G)=\prod_{1\leq i<j\leq n}p_{ij}^{a_{ij}}(1-p_{ij})^{1-a_{ij}}\). This is a fairly broad model covering e.g. stochastic block models. We define the Hamming distance between two graphs \(G\), \(G^{\prime}\) with respective adjacency matrices \(A\) and \(A^{\prime}\) to be \(d_{H}(G,G^{\prime})=\sum_{1\leq i<j\leq n} \vert a_{ij}-a^{\prime}_{ij}\vert\). We then say that the Fréchet mean of the probability measure \(\mathbb{P}\) is \(\mu(\mathbb{P})=\mathrm{argmin}_{G\in\mathcal{G}}d_{H}(G,G^{\prime})^{2}\mathbb{P}(G)\) where \(\mathrm{argmin}\) is the function which selects the (not necessarily unique) graph \(G\) which minimises the sum (this always exists). We also use the empirical sample Fréchet mean; if \(G^{(1)},\ldots ,G^{(N)}\) is a sample from this distribution, this is \(\hat{\mu}_{N}[\mathbb{P}]=\mathrm{argmin}_{G\in \mathcal{G}}\frac{1}{N}\sum_{1\leq i\leq N} d^{2}_{H}(G,G^{(i)})\). The first main result of the paper under review is that \(\mu(\mathbb{P})\) is the matrix whose \(ij\) entry is \(1\) if \(\mathbb{E}[A]_{ij}=p_{ij}>1/2\) and is 0 otherwise. The second main result is that for large sample size, the sample Fréchet mean graph is asymptotically equal to the sample Fréchet median graph. The proof of the latter result uses concentration inequalities. For the entire collection see [Zbl 1492.94005].