Source-linked AI summary
Comparative Evaluation of Community Detection Algorithms: A Topological Approach
Günce Orman, Vincent Labatut, Hocine Cherifi
TL;DR
This study addresses the limits of partition-based comparisons of community detection algorithms, which overlook communities’ topological properties. It evaluates representative algorithms on realistic artificial networks using both traditional performance measures and community-oriented topology, finding that the approaches can disagree and should be used together.
Problem
Partition-based evaluations compare community structures as node sets but ignore their topological properties, even though algorithms may estimate communities with different link distributions.
Method
The study modifies the LFR model to generate realistic artificial networks and evaluates eight fast community detection algorithms using both traditional partition-based measures and community-oriented topological measures.
Results
Performances and topological properties do not always agree: MarkovCluster and WalkTrap rank near InfoMap by traditional measures but have much less similar topological features.
Takeaways & Limitations
Partition-based and topology-based evaluations are complementary and both are needed for a relevant and complete analysis of community detection results.
Takeaways & Limitations
The algorithm rankings may be specific to the benchmark and are not intended to generalize to all kinds of networks.
Abstract
from arXiv · showhide
Community detection is one of the most active fields in complex networks analysis, due to its potential value in practical applications. Many works inspired by different paradigms are devoted to the development of algorithmic solutions allowing to reveal the network structure in such cohesive subgroups. Comparative studies reported in the literature usually rely on a performance measure considering the community structure as a partition (Rand Index, Normalized Mutual information, etc.). However, this type of comparison neglects the topological properties of the communities. In this article, we present a comprehensive comparative study of a representative set of community detection methods, in which we adopt both types of evaluation. Community-oriented topological measures are used to qualify the communities and evaluate their deviation from the reference structure. In order to mimic real-world systems, we use artificially generated realistic networks. It turns out there is no equivalence between both approaches: a high performance does not necessarily correspond to correct topological properties, and vice-versa. They can therefore be considered as complementary, and we recommend applying both of them in order to perform a complete and accurate assessment.
1. Introduction
Community-detection evaluations traditionally compare estimated and reference communities as node partitions, but this ignores their topological properties. The study addresses this gap by combining partition-based measures with community-oriented topology on realistic artificial networks.
- Evaluation gap: Traditional evaluations compare estimated and reference community structures as node sets or partitions.Common measures include Normalized Mutual Information and other association scores.
- Evaluation gap: Partition-based comparisons can assign the same performance to structures with different link distributions.This motivates evaluating cohesion, separation, and other community interactions directly.
- Topological evaluation: Community-wise density, average distance, internal transitivity, hub dominance, and embeddedness describe community topology in greater detail.These measures had been used to characterize real-world community structures but not previously to compare detection algorithms in this way.
- Benchmark data: Artificial networks are used because real-world benchmarks with identified community structures require expert intervention and are often scarce or small.The generative networks are intended to reproduce properties such as power-law degrees, small-worldness, degree correlation, transitivity, and community-size heterogeneity.
- Study design: The study generates realistic undirected, unweighted networks with the LFR model and evaluates representative algorithms using both classic and topological measures.The obtained results are then compared across the two evaluation approaches.
2. Performance of Community Detection Algorithms
Traditional community-detection evaluation treats each community structure as a partition and measures agreement with a reference partition. The section reviews node-membership and node-pair measures used for this comparison.
- Partition-based evaluation: Traditional performance evaluation compares estimated and reference community structures as partitions of the node set.Links between nodes are not included in this representation.
- Node-membership measures: FCC counts nodes whose estimated community matches the majority assignment in their reference community.The normalized score ranges from 0 to 1, and fused reference communities are treated as misclassified.
- Pairwise measures: The Rand Index measures the proportion of node pairs for which estimated and reference structures agree on same-community or different-community membership.Agreement is evaluated pairwise rather than by directly comparing community topology.
- Partition similarity: Normalized Mutual Information measures how much information two partitions share.Perfect agreement receives 1, while complete disagreement receives 0.
3. Community-Oriented Topological Properties
Community-oriented topological measures evaluate cohesion, separation, and internal structure beyond node membership. The section defines measures including embeddedness, size distribution, transitivity, density, distance, and hub dominance.
- Overview: Topological properties characterize community structures by incorporating links rather than only individual node membership.They enable comparisons between partitions from a purely topological perspective.
- Embeddedness: Embeddedness is the ratio of a node’s internal degree to its total degree, ranging from 0 to 1.It reaches 1 when all neighbors belong to the node’s community and 0 when none do.
- Community size: Community sizes in real-world networks are described as heterogeneous and approximately power-law distributed, with exponent β ranging from 1 to 2.This corresponds to many small communities and relatively few very large ones.
- Internal transitivity: Internal transitivity averages local neighbor interconnection within a community.Its distribution varies by network class, increasing in Internet and communication networks and peaking before decreasing in biological and social networks.
- Density: Community density is the ratio of actual to possible internal links, while scaled density multiplies density by community size.Scaled density distinguishes tree-like communities from denser, clique-like structures and varies across network classes.
- Average distance: Average shortest-path distance assesses community cohesion and is expected to grow roughly logarithmically for small real-world communities.Small distances can reflect high density, hubs, or both, depending on network class.
- Hub dominance: Hub dominance measures the maximum internal degree relative to the maximum theoretically possible degree for a community.It equals 1 when a node connects to every other community member and generally decreases with community size in several network classes.
4. Community Detection Algorithms
The study compares representative community-detection algorithms spanning modularity optimization, similarity, compression, statistical significance, diffusion, and random-walk approaches. These methods differ in how they operationalize cohesion, separation, information structure, or statistical evidence.
- Method categories: The selected algorithms are organized by the principles used to identify communities, while some slow methods are excluded.The informal target is a densely interconnected group separated from the rest of the network.
- Modularity-based approaches: Modularity-based methods optimize cohesion and separation through intra- and inter-community links.Fast Greedy repeatedly joins communities according to modularity change, while Louvain adds iterative node moves and network aggregation.
- Similarity and random-walk approaches: WalkTrap uses distances derived from random walks and hierarchical agglomerative clustering.Its premise is that random walks tend to remain within communities.
- Compression-based approaches: Compression-based methods seek community structures that represent the network compactly while limiting information loss.InfoMod uses a community matrix and membership vector, whereas InfoMap minimizes the information needed to encode random walks with a two-level nomenclature.
- Significance-based approaches: OSLOM identifies statistically significant individual communities relative to a null model without community structure.It can detect mutually exclusive, overlapping, or hierarchical communities, but this study applies it to undirected unweighted networks.
- Diffusion-based approaches: Diffusion-based methods detect communities through information propagation, including label voting in COPRA and matrix expansion and inflation in MarkovCluster.COPRA is applied here to mutually exclusive communities in undirected, unweighted, unipartite networks.
5. Generative Model
The LFR model generates artificial networks with realistic structural properties and directly controllable network and community parameters. Generated networks were compared with real-world networks and sampled repeatedly for consistency.
- LFR model: The LFR model generates networks with realistic sizes, power-law degree distributions, and power-law community-size distributions.Its parameters include network size, average and maximal degree, degree-distribution exponent, community-size exponent, and mixing coefficient.
- LFR model: The mixing coefficient μ controls the average proportion of inter-community links, while 1−μ gives the proportion of intra-community links.For a node of degree k, the external degree is kμ and the internal degree is k(1−μ).
- Parameter selection: The study uses γ=3 and β=2 as representative exponents for the degree and community-size power laws.These values were selected from studies of real-world networks, whose sizes and degrees vary widely.
- Realism of generated networks: Generated networks were designed to match biological, Internet, and communication networks across size, degree, and community-size properties.The generated instances include 7500-, 25000-, and 250000-node networks corresponding to the real-world network classes.
- Validation: Five networks were generated for each network size to ensure consistency, and measurements confirmed that community sizes followed the expected power-law distribution.The observed minimum and maximum community sizes were similar to those in comparable real-world networks.
6. Results
The generated networks reproduce many real-world community properties, but detected algorithms diverge substantially in both traditional partition scores and topological structure. These evaluations can therefore rank methods differently and reveal structural distinctions hidden by partition-based measures.
- Generated networks: Community sizes follow a power-law distribution, while embeddedness contains more zero-valued nodes than expected because of incompatibilities between mixing coefficients and node degrees.The generated community sizes remain comparable to real-world networks of similar size.
- Generated networks: Scaled density increases with community size, indicating that the smallest communities are tree-like.The increase is reported from 2 to 14 for networks with 7,500 and 25,000 nodes, and to 8 for networks with 250,000 nodes.
- Generated networks: Average distance rises with community size until a network-dependent limit and then stabilizes, producing trends especially similar to biological, information, and communication networks.For 25,000-node networks, it increases from 1.5 to 2.5 before stabilizing beyond approximately 35 nodes.
- Generated networks: Hub dominance decreases for small communities as size increases, then rises again for medium and large communities, with greater dispersion among larger communities.The dispersion is attributed to the smaller number of large communities and their power-law-distributed sizes.
- Generated networks: Internal transitivity decreases with community size and fails to match the varied trends observed in real-world networks, likely because LFR rewiring does not explicitly form triangles.The mismatch is especially pronounced for larger generated networks, where transitivity values are very low.
- Algorithm evaluation: Traditional and topological evaluations distinguish algorithms differently: FCC and ARI give the most contrasted results, while algorithm rankings otherwise diverge only slightly.Topological inspection further shows major differences in community-size distributions, embeddedness, density, average distance, and hub dominance across algorithms.
7. Conclusion
The study combines partition-based performance measures with community-oriented topological measures to compare community detection algorithms. These evaluations can disagree, so both are needed for a complete assessment, while the benchmark’s rankings should not be generalized to all networks.
- The study evaluates eight community detection algorithms on artificial networks generated with a modified LFR model and known community structures.
- Traditional partition measures generally rank InfoMap and MarkovCluster first, followed by WalkTrap.
- Topological analysis confirms InfoMap’s similarity to the reference but finds MarkovCluster and WalkTrap less similar, especially in community sizes and embeddedness.
- Partition performance and topological similarity are not equivalent because partition measures treat community differences differently and may underweight misclassified hubs.
- The authors recommend using faster traditional measures first, then inspecting the best structures with topological measures; conclusions remain specific to the benchmark.
- Future work should improve transitivity realism and expand the tested topological properties, network classes, and algorithms.