Source-linked AI summary
Detect overlapping and hierarchical community structure in networks
Huawei Shen, Xueqi Cheng, Kai Cai, Mao-Bin Hu
TL;DR
Community structure matters for network systems, but existing methods typically detect overlapping and hierarchical organization separately. EAGLE combines both goals using maximal cliques, agglomerative clustering, and an extended modularity measure, with applications producing a more complete picture of community structure.
Problem
Communities are usually overlapping and hierarchical, while prior methods generally detect these properties separately.
Method
EAGLE applies an agglomerative framework to maximal cliques and uses extended modularity to evaluate overlapping community covers.
Results
EAGLE identifies hierarchical and overlapping structure in word-association and scientific-collaboration networks, including 1754 communities with EQ ≈0.85 in the latter.
Takeaways & Limitations
EAGLE provides a possible way to obtain a more complete picture of community structure and analyze some very large networks.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
Community structure is important for understanding networks, yet real communities are often both overlapping and hierarchical. EAGLE addresses the gap between methods that separately detect these properties by combining both in one framework.
- Network topology influences the dynamics of complex systems, motivating efficient approaches that capture structural properties.
- Community-detection methods produce either partitions, where each vertex belongs to one community, or covers that may allow overlaps.
- Modularity-based partition methods can suffer from a resolution limit, especially when smaller modules are embedded in larger structures.
- Existing approaches generally examine hierarchy and overlap separately: partition methods reveal hierarchy, whereas cover methods reveal overlap but may neglect vertices.
- EAGLE detects hierarchical and overlapping communities together by applying an agglomerative procedure to maximal cliques.
- On a schematic network, Newman’s fast algorithm finds hierarchy without overlap, k-clique finds overlap without hierarchy, and EAGLE finds both.
II. THE ALGORITHM: EAGLE
EAGLE builds an agglomerative dendrogram from maximal cliques, then selects a cut using extended modularity EQ to identify overlapping communities and recursively expose hierarchy.
- Dendrogram construction: The algorithm repeatedly merges the most similar pair of communities until a single community remains, producing a dendrogram of agglomerations.Similarity is calculated between community pairs, with updates after each merge.
- Initialization: EAGLE begins with non-subordinate maximal cliques as initial communities, while subordinate vertices are represented as singleton communities.Maximal cliques are first enumerated; subordinate cliques can be discarded using a size threshold k.
- Cover selection: Any dendrogram cut yields a network cover, and EAGLE selects the cut with maximum EQ as the best cover.EQ extends modularity to evaluate overlapping community decompositions.
- Cover selection: EQ reduces to Q when every vertex belongs to one community and equals 0 when all nodes belong to the same community.A high EQ value indicates a significant overlapping community structure.
- Hierarchical refinement: Although EQ has a resolution limit, recursively applying EAGLE within detected communities can reveal smaller modules and produce a hierarchy of overlapping communities.The recursive procedure continues until communities can no longer be divided into smaller ones.
- Computational cost: EAGLE is more time-consuming than Newman’s fast algorithm and the k-clique algorithm.The paper leaves improving EAGLE’s speed as future work.
III. APPLICATIONS
EAGLE is applied to word-association and scientific-collaboration networks to reveal overlapping and hierarchical communities, with results illustrated through community decompositions and comparisons with Newman’s algorithm.
- EAGLE identifies 17 communities in the word-association network, including 63 overlapping pairs among 136 possible pairs.
- Recursive decomposition links word sub-communities to semantic animal families, with the overlapping word Animal bridging two communities.
- EAGLE finds 1754 scientific-collaboration communities with EQ ≈0.85; three large communities contain 23.4% of all vertices and correspond closely to subject subareas.
- Further decomposition produces 26 sub-communities whose structure appears correlated with researchers’ regional divisions.
- Figures encode community size numerically, overlap through links and red nodes or edges, colors for distinct communities, and EQ or Q values for sub-community decompositions.
- In the scientific-collaboration network, Newman’s fast algorithm yields a similar number of hierarchy levels, but partitions differ because it does not allow community overlaps.
IV. CONCLUSIONS AND DISCUSSIONS
The paper concludes that EAGLE detects hierarchical and overlapping community structure using maximal cliques and an agglomerative framework. Applications to two real-world networks demonstrate its usefulness, while the current method is limited to unweighted, undirected networks.
- EAGLE combines hierarchical and overlapping community detection through maximal cliques and an agglomerative framework.
- Applications to word-association and scientific-collaboration networks demonstrate EAGLE’s effectiveness and provide a more complete picture of network community structure.
- The method can help analyze some very large networks and illuminate topological and dynamical behavior in large technological, social, and biological systems.