Approximating sparse graphs: The random overlapping communities model. Issue 4 (26th March 2022) - Petti, Samantha; Vempala, Santosh S.
Abstract: How can we approximate sparse graphs and sequences of sparse graphs (with unbounded average degree)? We consider convergence in the first k moments of the graph spectrum (equivalent to the numbers of closed k ‐walks) appropriately normalized. We introduce a simple random graph model that captures the limiting spectra of many sequences of interest, including the sequence of hypercube graphs. The random overlapping communities (ROC) model is specified by a distribution on pairs ( s, q ), s ∈ ℤ +, q ∈ ( 0, 1 ] . A graph on n vertices with average degree d is generated by repeatedly picking pairs ( s, q ) from the distribution, adding an Erdős–Rényi random graph of edge density q on a subset of vertices chosen by including each vertex with probability s / n, and repeating this process so that the expected degree is d . We also show that ROC graphs exhibit an inverse relationship between degree and clustering coefficient, a characteristic of many real‐world networks.