Structure and Overlaps of Communities in Networks

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.


About Giorgio Bertini

Research Professor. Founder Director at Learning Change Project - Research on society, culture, art, neuroscience, cognition, critical thinking, intelligence, creativity, autopoiesis, self-organization, rhizomes, complexity, systems, networks, leadership, sustainability, thinkers, futures ++
This entry was posted in Community, Networks and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.