Detect overlapping and hierarchical community structure in networks

2008/10/31 by Huawei Shen, Xueqi Cheng, Kai Cai +1 · 3 citations
Computer Science · Engineering · Mathematics · Physics and Astronomy · #Advanced Clustering Algorithms Research #Artificial intelligence #Canopy clustering algorithm #Clique percolation method #Cluster analysis #Community structure #Complex Network Analysis Techniques #Complex network #Computer science #Correlation clustering #Cover (algebra) #Data mining #Engineering #Hierarchical clustering #Hierarchical clustering of networks #Hierarchical network model #Mathematics #Modularity (biology) #Opinion Dynamics and Social Influence #Set (abstract data type) #Statistics #Theoretical computer science #cs.CY #physics.soc-ph

paper · pdf · doi:10.1016/j.physa.2008.12.021

published as Physica A 388 (2009) 1706-1712 · 7 pages, 5 figures

arxiv created 2008/11/03 · openalex publication_date 2008/12/17 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

Clustering and community structure is crucial for many network systems and the related dynamic processes. It has been shown that communities are usually overlapping and hierarchical. However, previous methods investigate these two properties of community structure separately. This paper proposes an algorithm (EAGLE) to detect both the overlapping and hierarchical properties of complex community structure together. This algorithm deals with the set of maximal cliques and adopts an agglomerative framework. The quality function of modularity is extended to evaluate the goodness of a cover. The examples of application to real world networks give excellent results.

Citations

• Community structure in social and biological networks
• Community detection in complex networks using extremal optimization
• Post-processing hierarchical community structures: Quality improvements and multi-scale view
• Algorithm 457: finding all cliques of an undirected graph
• Comparing community structure identification
• Statistical mechanics of complex networks
• The Structure and Function of Complex Networks
• Uncovering the overlapping community structure of complex networks in nature and society

Cited by

• Mining and Intervention of Social Networks Information Cocoon Based on Multi-Layer Network Community Detection
• Efficiently detecting overlapping communities using seeding and semi-supervised learning
• Partitioning Breaks Communities

Related

• High-Quality Disjoint and Overlapping Community Structure in Large-Scale Complex Networks
• Complex Networks, Communities and Clustering: A survey
• A Modular Multiscale Approach to Overlapping Community Detection
• Shared Nodes of Overlapping Communities in Complex Networks
• Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach