Detecting the overlapping and hierarchical community structure of complex networks

Abstract

Many networks in nature, society and technology are characterized by a mesoscopic level of organization, with groups of nodes forming tightly connected units, called communities or modules, that are only weakly linked to each other. Uncovering this community structure is one of the most important problems in the field of complex networks. Networks often show a hierarchical organization, with communities embedded within other communities; moreover, nodes can be shared between different communities. Here we present the first algorithm that finds both overlapping communities and the hierarchical structure. The method is based on the local optimization of a fitness function. Community structure is revealed by peaks in the fitness histogram. The resolution can be tuned by a parameter enabling to investigate different hierarchical levels of organization. Tests on real and artificial networks give excellent results.

20 pages, 8 figures. Final version published on New Journal of Physics

References in corpus (6)

• Uncovering the overlapping community structure of complex networks in nature and society
• Comparing community structure identification
• Analysis of the structure of complex networks at different resolution levels
• Subnetwork hierarchies of biochemical pathways
• Robustness of community structure in networks
• Weighted network modules

Cited by in corpus (7)

• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Detect overlapping and hierarchical community structure in networks
• Line Graphs, Link Partitions and Overlapping Communities
• Extending the definition of modularity to directed graphs with overlapping communities
• Quantifying and identifying the overlapping community structure in networks
• Spectral tripartitioning of networks
• Fundamental statistical features and self-similar properties of tagged networks