In:
Random Structures & Algorithms, Wiley, Vol. 61, No. 4 ( 2022-12), p. 844-908
Abstract:
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.
Type of Medium:
Online Resource
ISSN:
1042-9832
,
1098-2418
Language:
English
Publisher:
Wiley
Publication Date:
2022
detail.hit.zdb_id:
1500812-5
SSG:
17,1
Bookmarklink
