Approximating sparse graphs: The random overlapping communities model. Issue 4 (26th March 2022)

• Record Type: Journal Article
• Authors: Petti, Samantha; Vempala, Santosh S.
• Is Part Of: Random structures & algorithms. Volume 61:Issue 4(2022)
• Page Start: 844
• Page End: 908
• Publication Date: 2022-03-26
• Subjects: clustering coefficient -- graph spectrum -- regularity lemma -- sparse graph limits -- Stieltjes moment problem; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21081
• Languages: English
• ISSNs: 1042-9832

Abstract

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.