EUVIMEDEUVIMED entdecken
Crossref

Approximating sparse graphs: The random overlapping communities model

Samantha Petti, Santosh S. Vempala

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →