Approximating sparse graphs: The random overlapping communities model
Random Structures & Algorithms · 2022-12 · 61 (4) · 844-908
DOI: 10.1002/rsa.21081 ↗Kurz gefasst
Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 26.03.2022. Verfasst von Samantha Petti und 1 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 48 Literaturangaben.
Abstract (Originalsprache)
How can we approximate sparse graphs and sequences of sparse graphs (with unbounded average degree)? We consider convergence in the first moments of the graph spectrum (equivalent to the numbers of closed ‐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 , . A graph on vertices with average degree is generated by repeatedly picking pairs from the distribution, adding an Erdős–Rényi random graph of edge density on a subset of vertices chosen by including each vertex with probability , and repeating this process so that the expected degree is . We also show that ROC graphs exhibit an inverse relationship between degree and clustering coefficient, a characteristic of many real‐world networks.
Zitieren
APA
Petti, S., & Vempala, S. S. (2022). Approximating sparse graphs: The random overlapping communities model. Random Structures & Algorithms, 61(4), 844-908. https://doi.org/10.1002/rsa.21081
Vancouver
Petti S, Vempala SS. Approximating sparse graphs: The random overlapping communities model. Random Structures & Algorithms. 2022;61(4):844-908. doi:10.1002/rsa.21081
BibTeX
@article{Petti2022,
author = {Petti, Samantha and Vempala, Santosh S.},
title = {Approximating sparse graphs: The random overlapping communities model},
journal = {Random Structures & Algorithms},
year = {2022},
volume = {61},
number = {4},
pages = {844--908},
doi = {10.1002/rsa.21081}
}
EUVIMED