Sharp Threshold for the Frechet Mean (or Median) of Inhomogeneous Erdos-Renyi Random Graphs
This foundational result addresses a theoretical problem in graph statistics, with implications for analyzing random graph ensembles, though it is incremental in extending known concepts to inhomogeneous cases.
The paper tackles the problem of determining the Fréchet mean or median graph for ensembles of inhomogeneous Erdős-Rényi random graphs using Hamming distance, proving that it is obtained by thresholding the expected adjacency matrix and exhibits a sharp threshold, resulting in either the empty or complete graph, with practical consequences such as the mean of sparse ensembles always being the empty graph.
We address the following foundational question: what is the population, and sample, Frechet mean (or median) graph of an ensemble of inhomogeneous Erdos-Renyi random graphs? We prove that if we use the Hamming distance to compute distances between graphs, then the Frechet mean (or median) graph of an ensemble of inhomogeneous random graphs is obtained by thresholding the expected adjacency matrix of the ensemble. We show that the result also holds for the sample mean (or median) when the population expected adjacency matrix is replaced with the sample mean adjacency matrix. Consequently, the Frechet mean (or median) graph of inhomogeneous Erdos-Renyi random graphs exhibits a sharp threshold: it is either the empty graph, or the complete graph. This novel theoretical result has some significant practical consequences; for instance, the Frechet mean of an ensemble of sparse inhomogeneous random graphs is always the empty graph.