The Fréchet mean of inhomogeneous random graphs
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].
- Averages of unlabeled networks: geometric characterization and asymptotic behavior
- Change-Point Methods on a Sequence of Graphs
- Fréchet change-point detection
- Generalized median graph computation by means of graph embedding in vector spaces
- Generalized median graphs and applications
- scientific article; zbMATH DE number 3051441 (Why is no real title available?)
- Hypothesis testing for network data in functional neuroimaging
- Metric models for random graphs
- On computing centroids according to the p-norms of Hamming distance vectors
- Persistent path homology of directed networks
- Sparse median graphs estimation in a high-dimensional semiparametric model
- Statistical graph space analysis
- The phase transition in inhomogeneous random graphs
This page was built for publication: The Fréchet mean of inhomogeneous random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2086589)
