Community Structure and Scale-free Collections of Erdos-Renyi Graphs

Abstract

Community structure plays a significant role in the analysis of social networks and similar graphs, yet this structure is little understood and not well captured by most models. We formally define a community to be a subgraph that is internally highly connected and has no deeper substructure. We use tools of combinatorics to show that any such community must contain a dense Erdős-Rényi (ER) subgraph. Based on mathematical arguments, we hypothesize that any graph with a heavy-tailed degree distribution and community structure must contain a scale free collection of dense ER subgraphs. These theoretical observations corroborate well with empirical evidence. From this, we propose the Block Two-Level Erdős-Rényi (BTER) model, and demonstrate that it accurately captures the observable properties of many real-world social networks.

@article{SeKoPi12,  
author = {C. Seshadhri and Tamara G. Kolda and Ali Pinar}, 
title = {Community Structure and Scale-free Collections of {Erd\H{o}s-R\'enyi} Graphs}, 
journal = {Physical Review~E}, 
volume = {85}, 
number = {5},
eid = {056109},
pagetotal = {9} 
month = {May}, 
year = {2012},
doi = {10.1103/PhysRevE.85.056109},
}