Source-linked AI summary
Detecting the overlapping and hierarchical community structure of complex networks
Andrea Lancichinetti, Santo Fortunato, Janos Kertesz
TL;DR
The paper addresses the challenge of detecting community structures that are both hierarchically organized and overlapping. It uses local optimization of a fitness function with tunable resolution, and reports excellent results on constructed and empirical networks, including higher normalized mutual information than CPM on three tested networks.
Problem
Community detection must account for nested modules and nodes belonging to multiple communities, which complicate recovery of a network’s mesoscopic organization.
Method
The method locally optimizes a fitness function to find natural communities, allowing nodes in multiple modules and varying resolution parameter α to probe different hierarchical scales.
Results
0.690 versus 0.170 normalized mutual information for karate, 0.781 versus 0.254 for dolphins, and 0.754 versus 0.697 for American college football, comparing our method with CPM.
Takeaways & Limitations
The framework simultaneously uncovers overlapping and hierarchical community structure and can be applied across different network scales and constructed or empirical networks.
Takeaways & Limitations
The tested setup is reliable, but alternative fitness functions, cover criteria, or optimization procedures may produce better results.
Abstract
from arXiv · showhide
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.
1. Introduction
Complex networks contain communities that may be hierarchically nested and overlapping, making their mesoscopic organization difficult to recover. The paper introduces a framework that detects both structures while exploring different hierarchical levels.
- Community structure: Communities are groups of nodes more densely connected internally than to the rest of the network, representing functional entities in many systems.Examples include social groups, topical Web pages, food-web categories, and metabolic pathways.
- Hierarchical structure: Hierarchical organization embeds small communities within progressively larger modules, so detecting only one modular level is insufficient.The paper describes nested communities as a central challenge for community detection.
- Overlapping structure: Nodes can belong to multiple modules through families, professions, hobbies, or other relationships, creating overlapping communities that standard methods may misclassify.Overlaps can conceal information and lower the quality of detected modules.
- Combined challenge: Hierarchical and overlapping organization often occur simultaneously, as illustrated by networks with nested clusters and nodes related to multiple groups.Figure 1 contrasts hierarchical structure with overlapping communities while emphasizing that the features can coexist.
- Proposed approach: The proposed framework locally explores each node’s natural community, permits repeated node visits for overlaps, and tunes a resolution parameter to examine hierarchical levels.These design choices target both demands in a single method.
2. The method
The method detects each node’s natural community by locally optimizing a fitness function, while allowing overlaps through repeated node exploration. Varying the resolution parameter reveals hierarchical covers, which are ranked using fitness stability.
- Local fitness optimization: Communities are subgraphs whose node fitness is maximized, with the natural community of node A chosen so adding or removing a node lowers the subgraph fitness.The fitness depends on internal and external degrees, while α controls community size.
- Local fitness optimization: The algorithm greedily adds the neighboring node with highest fitness, recalculates all node fitnesses, removes negative-fitness nodes, and repeats until no examined neighbor improves the group.This local exploration starts from a single node and iteratively expands and backtracks the candidate subgraph.
- Overlapping covers: A graph cover assigns every node to at least one cluster; exploring nodes regardless of existing memberships recovers overlapping communities while avoiding repeated discovery of identical natural communities.The procedure samples an unassigned node, detects its natural community, and continues until all nodes belong to at least one group.
- Resolution and hierarchy: Large α values produce smaller communities, small α values produce larger modules, and varying α explores covers across the hierarchy from the whole network to individual nodes.The authors report that α < 0.5 usually yields one community, whereas α > 2 usually recovers the smallest communities.
- Resolution and hierarchy: Stable covers are identified as pronounced peaks in a fitness histogram and ranked by the average fitness of their communities across covers obtained at different α values.Each cover persists over a range of α; higher histogram peaks indicate greater stability.
- Computational complexity: For a fixed α, approximate complexity is O(n_c⟨s^2⟩), while the reported worst-case complexity for hierarchical networks is n^2 log n.Community construction scales approximately as O(s^2), and complexity depends on community sizes and overlap extent.
3. Results
Tests on hierarchical benchmarks and real networks show that the method recovers community structure across levels, including overlapping and nested groups, while random graphs yield unstable covers.
- Hierarchical benchmarks: 100 realizations of hierarchical benchmark networks show very good recovery at both macro- and micro-community levels using normalized mutual information.The benchmark contains 16 groups of 32 nodes organized into four supergroups; micro-communities are deliberately fuzzy with k1 = k2 = 16.
- Hierarchical benchmarks: The four macro-communities are correctly identified for k3 < 24, with failure beginning near k3 ∼32 when internal and external macro-community links are equal.The lower-level modules remain well recovered despite strong mixing between micro-communities.
- Real networks: Fitness-histogram peaks identify natural covers in dolphins and American football networks, while Zachary’s karate club yields a topologically meaningful four-cluster cover.The karate-club two-community social split appears as a higher hierarchical level formed by merging the four main communities.
- Real networks: The method recovers overlapping two-community structures in Zachary’s karate club and the dolphins’ network, including nodes shared between groups.In the karate club, nodes 3, 9, 10, 14 and 31 are shared; in the dolphins’ network, nodes 8, 20, 29, 31 and 40 are shared.
- Comparison with CPM: Normalized mutual information is 0.690 versus 0.170 for CPM on karate, 0.781 versus 0.254 on dolphins, and 0.754 versus 0.697 on American football.The method is superior to CPM in these instances, whereas CPM performs better for networks with many cliques such as the word association network.
- Additional analyses: Random graphs show no visible community structure because their covers are unstable, whereas the .gov Web graph has a skewed community-size distribution with a power-law tail exponent 2.2(1).The Web-graph distribution was obtained at α = 1 without a complete multi-resolution analysis, so it may not represent the most significant cover.
4. Conclusions
The paper presents a flexible local-fitness framework that detects overlapping and hierarchical community structure, with extensions to large, weighted, and directed networks. Its applications to constructed and empirical networks produced excellent results, while the framework can be adapted to system-specific community topology.
- 4. Conclusions: The method simultaneously uncovers hierarchical and overlapping community structure through local, iterative optimization of a fitness function.Nodes may belong to multiple modules, while tuning α probes different organizational scales.
- 4. Conclusions: Applications to constructed and empirical networks gave excellent results.The conclusion reports this outcome without specifying a single aggregate metric.
- 4. Conclusions: The framework supports alternative fitness functions, cover criteria, and optimization procedures tailored to the topology of a specific system.The tested setup is reliable, but the authors cannot exclude that other choices may yield better results.
- 4. Conclusions: The analysis can be distributed across many computers, pushing the tractable graph size upward and enabling community-size studies of networks up to millions of nodes.The method also quantifies overlapping-node participation through node fitness values for each community.
- 4. Conclusions: The method extends naturally to weighted networks by replacing degree with strength and can also be adapted to directed networks using suitable fitness functions.The weighted-network extension requires no thresholding.
Appendix A. Dependence on the random seeds
Random starting seeds can alter cover rankings at a fixed α, although the most relevant covers remain consistent across seeds. Additional runs near meaningful α-regions improve ranking reliability at negligible comparative cost.
- Appendix A. Dependence on the random seeds: Different random seeds may change the covers obtained for the same α-value and therefore affect the fitness-histogram ranking.The authors report that the most relevant covers are the same across seed choices, while their ranking may differ.
- Appendix A. Dependence on the random seeds: Additional runs with different seeds near meaningful α-regions produce more reliable cover rankings.Because the number of relevant peaks is much smaller than the number of nodes, these runs add negligible cost relative to the total runs.
Appendix B. Comparing partitions
The appendix develops an information-theoretic comparison of overlapping covers using normalized conditional entropy and mutual information. It represents overlapping membership with binary variables, excludes complementary cluster matches, and establishes equality at the normalized measure's maximum.
- Appendix B. Comparing partitions: The appendix addresses comparison of overlapping covers using information-theoretic criteria.The comparison is framed in terms of the information needed to infer one cover from another.
- Appendix B. Comparing partitions: Normalized mutual information combines the two normalized conditional entropies to compare covers.The appendix also describes entropy and joint entropy for the random variables associated with the two covers.
- Appendix B. Comparing partitions: Overlapping membership is represented by a binary array with one entry per cluster, enabling each cluster-membership indicator to be treated as a random variable.For cluster C′_k, membership probabilities are P(X_k = 1) = n_k/N and P(X_k = 0) = 1 − n_k/N.
- Appendix B. Comparing partitions: Normalized conditional entropy measures the average relative lack of information needed to infer one cover from the other.The procedure computes H(X_k|Y), normalizes by H(X_k), averages over k, and repeats the calculation in the reverse direction.
- Appendix B. Comparing partitions: The comparison constrains candidate cluster matches to exclude clusters close to complements of the target cluster.The constraint requires positive-case information to exceed mixing-term information.
- Appendix B. Comparing partitions: With the complement constraint, the normalized measure equals one if and only if the two covers are equal.The procedure computes conditional entropies in both directions before combining them in the normalized mutual-information expression.