title: Community structure and scale-free collections of Erdős-Rényi 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.
authors.affiliation: Sandia National Laboratories, Livermore, California 94551, USA. scomand@sandia.gov
authors.forename: C
authors.initials: C
authors.lastname: Seshadhri
authors.forename: Tamara G
authors.initials: TG
authors.lastname: Kolda
authors.forename: Ali
authors.initials: A
authors.lastname: Pinar