Structure and Overlaps of Communities in Networks

Abstract

One of the main organizing principles in real-world social, information and technological networks is that of network communities, where sets of nodes organize into densely linked clusters. Even though detection of such communities is of great interest, understanding the structure communities in large networks remains relatively limited. Due to unavailability of labeled ground-truth data it is practically impossible to evaluate and compare different models and notions of communities on a large scale. In this paper we identify 6 large social, collaboration, and information networks where nodes explicitly state their community memberships. We define ground-truth communities by using these explicit memberships. We then empirically study how such ground-truth communities emerge in networks and how they overlap. We observe some surprising phenomena. First, ground-truth communities contain high-degree hub nodes that reside in community overlaps and link to most of the members of the community. Second, the overlaps of communities are more densely connected than the non-overlapping parts of communities, in contrast to the conventional wisdom that community overlaps are more sparsely connected than the communities themselves. Existing models of network communities do not capture dense community overlaps. We present the Community-Affiliation Graph Model (AGM), a conceptual model of network community structure, which reliably captures the overall structure of networks as well as the overlapping nature of network communities.

References in corpus (7)

• Emergence of scaling in random networks
• Community detection in graphs
• Uncovering the overlapping community structure of complex networks in nature and society
• Resolution limit in community detection
• The Dynamics of Viral Marketing
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Robustness of community structure in networks

Cited by in corpus (5)

• Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
• Core-Periphery Structure in Directed Networks
• Community Detection in Partially Observable Social Networks
• Benchmarking community detection methods on social media data
• Bayesian Overlapping Community Detection in Dynamic Networks