Community structure and scale-free collections of Erdős-Rényi graphs

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\"os-R\'enyi (ER) subgraph. Based on mathematical arguments, we...