2017/09/27 by Samantha Petti, Santosh Vempala, Petti, Samantha +1
Computer Science · Physics and Astronomy · #Advanced Clustering Algorithms Research #Combinatorics (math.CO) #Complex Network Analysis Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Opinion Dynamics and Social Influence #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1709.09477
openalex publication_date 2017/09/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A wide variety of complex networks (social, biological, information etc.) exhibit local clustering with substantial variation in the clustering coefficient (the probability of neighbors being connected). Existing models of large graphs capture power law degree distributions (Barabási-Albert) and small-world properties (Watts-Strogatz), but only limited clustering behavior. We introduce a generalization of the classical Erdős-Rényi model of random graphs which provably achieves a wide range of desired clustering coefficient, triangle-to-edge and four-cycle-to-edge ratios for any given graph size and edge density. Rather than choosing edges independently at random, in the Random Overlapping Communities model, a graph is generated by choosing a set of random, relatively dense subgraphs ("communities"). We discuss the explanatory power of the model and some of its consequences.