PaperlayerView exact revision on arXiv

Source-linked AI summary

Community Detection via Maximization of Modularity and Its Variants

Mingming Chen, Konstantin Kuzmin, Boleslaw K. Szymanski

arXiv:1507.00787v1physics.soc-phcs.SI

TL;DR

The paper examines modularity's opposing tendencies to split large communities and merge smaller ones, and evaluates alternatives designed to address these issues. It proposes fine-tuned Q and Qds algorithms based on iterative splitting and merging, finding Fine-tuned Qds most effective and useful for improving other algorithms' results.

  • Problem

    Modularity optimization can split large communities or merge smaller communities below a network-dependent threshold, limiting community detection quality.

  • Method

    The paper reviews modularity methods, discusses Qds, and proposes fine-tuned algorithms that iteratively split and merge community structures to improve quality.

  • Results

    Fine-tuned Qds is the most effective of Greedy Q, Fine-tuned Q, and Fine-tuned Qds across the evaluated networks and significantly improves results from other algorithms.

  • Takeaways & Limitations

    Seven ground-truth-based quality metrics are consistent with Qds but not Q, supporting Qds as the superior community-quality metric in these evaluations.

  • Takeaways & Limitations

    The multiple-resolution approach cannot select one resolution parameter that avoids adversely affecting both smaller and larger communities.

Abstract

from arXiv · show

In this paper, we first discuss the definition of modularity (Q) used as a metric for community quality and then we review the modularity maximization approaches which were used for community detection in the last decade. Then, we discuss two opposite yet coexisting problems of modularity optimization: in some cases, it tends to favor small communities over large ones while in others, large communities over small ones (so called the resolution limit problem). Next, we overview several community quality metrics proposed to solve the resolution limit problem and discuss Modularity Density (Qds) which simultaneously avoids the two problems of modularity. Finally, we introduce two novel fine-tuned community detection algorithms that iteratively attempt to improve the community quality measurements by splitting and merging the given network community structure. The first of them, referred to as Fine-tuned Q, is based on modularity (Q) while the second one is based on Modularity Density (Qds) and denoted as Fine-tuned Qds. Then, we compare the greedy algorithm of modularity maximization (denoted as Greedy Q), Fine-tuned Q, and Fine-tuned Qds on four real networks, and also on the classical clique network and the LFR benchmark networks, each of which is instantiated by a wide range of parameters. The results indicate that Fine-tuned Qds is the most effective among the three algorithms discussed. Moreover, we show that Fine-tuned Qds can be applied to the communities detected by other algorithms to significantly improve their results.

1 INTRODUCTION

Community detection identifies densely connected groups in networks and is commonly approached by maximizing modularity. However, modularity can both split large communities and merge smaller ones, motivating Qds and fine-tuned algorithms evaluated across diverse networks.

  • Community detection seeks groups of nodes with denser internal connections than external connections across many network types.
  • Modularity compares within-community edge fractions with those expected in a randomized graph preserving node count and degree sequence.
  • Modularity optimization includes greedy, spectral, extremal-optimization, simulated-annealing, sampling, and mathematical-programming approaches.
  • Modularity can split large communities into smaller ones or merge communities below a network-dependent threshold, producing the resolution-limit problem.
  • Fine-tuned Qds repeatedly splits and merges structures, and evaluations across real, clique, and LFR networks identify it as the most effective method.

2 REVIEW OF MODULARITY RELATED LITER-

The review covers modularity's definition, optimization methods, opposing optimization problems, and quality metrics such as Modularity Density that address the resolution limit.

  • The section reviews modularity and its maximization methods before discussing two opposing problems of modularity optimization.
  • It surveys community-quality measurements proposed to solve the resolution-limit problem and discusses Modularity Density (Qds) as avoiding both problems.

2.1 Definition of Modularity

Modularity measures community strength by comparing observed internal connectivity with a randomized-network reference. The definition extends naturally to directed and weighted networks.

  • Modularity quantifies community strength by comparing within-community edge fractions with those produced by random connections between nodes.
  • The formal definition uses communities, internal edges, external edges, and the network's total edge count.
  • An equivalent matrix expression uses node degrees, adjacency-matrix entries, community labels, and the Kronecker delta.
  • Higher Q indicates stronger community structure, motivating algorithms that maximize modularity over network partitions.
  • The modularity definition can be extended from undirected, unweighted networks to directed and weighted networks.
  • For weighted networks, edge weights can be represented by parallel edges, and node degree is the sum of incident edge weights.

2.2 Modularity Optimization Approaches

Modularity optimization methods range from greedy and spectral approaches to local-search and simulated-annealing procedures. They trade computational scalability against partitioning limitations and resolution-related concerns.

  • Exhaustive modularity maximization is computationally prohibitive, so approximate optimization algorithms are used.
  • Greedy Algorithms: Newman's greedy method starts with singleton communities and repeatedly merges the pair producing the largest modularity increase, retaining the best partition.
  • Greedy Algorithms: Sparse-matrix data structures reduce unnecessary updates, while dendrogram depth influences the resulting running time.
  • Greedy Algorithms: Unbalanced merging can make the greedy algorithm non-scalable beyond 500,000 nodes by producing very unbalanced dendrograms.
  • Greedy Algorithms: Louvain alternates node-moving and community-network phases, with complexity growing like O(|E|), but results depend on node-processing order.
  • Spectral Methods: Spectral methods use modularity-matrix or Laplacian eigenvectors, and some approaches recursively subdivide communities until no positive modularity gain remains.
  • Spectral Methods: Spectral optimization may divide communities recursively and use only the leading modularity-matrix eigenvector, while multi-eigenvector methods address these drawbacks.
  • Spectral Methods: QCUT alternates recursive Kcut partitioning with node migration and community merging, while HQUCT recursively applies QCUT to address modularity's resolution limit.

2.3 Resolution limit

Modularity optimization can fail in opposite ways: splitting large communities or merging smaller ones. The resolution threshold depends on network size and inter-community connectivity, limiting which communities can be resolved.

  • A community below a network-dependent threshold may remain undetected even when it is a complete subgraph connected by one edge.
  • The resolution limit can approach the size of the entire network, producing a few giant communities or a single community.This makes the resulting community structure difficult to interpret because smaller communities may be hidden within larger ones.
  • Modularity has a resolution limit of order √|E|, which bounds the number and size of communities it can resolve.A community with fewer than the relevant internal-edge threshold may not be resolved through modularity optimization.
  • Weighted modularity can improve resolution by adjusting inter-community edge weights, but selecting sufficiently small weights can be challenging.The cited algorithm for lowering the inter-community weight parameter requires O(m|V| log |V|) time.
  • With suitable weighting, arbitrarily small inter-community weights could yield a desired number of communities, although finding those weights is difficult in practice.

2.4 Resolving the resolution limit problem

Several methods address modularity’s resolution limit by localizing, rescaling, hierarchically repeating, or redefining the quality measure. These approaches improve resolution in different ways, but multiresolution methods can still trade off errors across community scales.

  • Localized modularity: Localized modularity evaluates each community with its neighbors, avoiding dependence on unrelated parts of the network.When every community is connected to every other, localized modularity yields the same value as traditional modularity.
  • Multiple resolution: Rescaling edge-adjacent weights changes the modularity resolution limit more slowly than the scaling parameter, enabling detection at different granularity levels.The resolution limit is proportional to √r, so an appropriate scale may make required communities visible to modularity optimization.
  • Multiple resolution: Varying the resolution parameter r produces larger communities for smaller r and smaller communities for larger r.Positive r enables more granular structures, while negative r provides a view of super communities.
  • Limitations: Multiresolution methods cannot choose one parameter that protects both small and large communities when community sizes vary substantially.Low resolution groups small communities, whereas high resolution splits large ones; sharp clustering-coefficient changes indicate susceptibility.
  • Hierarchical multiresolution: Hierarchical multiresolution applies resolution detection independently to essential network parts, including near the modularity resolution limit.It starts with one community, finds a suitable resistance value, recursively processes detected communities, and stops when further splitting is unnecessary.
  • Objective functions: A general additive objective-function result implies that combining two optimal partitions can also produce an optimal partition.For complete graphs, a resolution-limit-free additive objective has an optimum consisting either of one community or singleton communities.
  • Modularity Density: Modularity Density combines Split Penalty with internal and pair-wise community density to address modularity’s opposing size biases.Split Penalty targets favoring small communities, while community density targets favoring large communities.
  • Modularity Density: Qds avoids merging consecutive cliques or dividing a clique and can detect communities of different sizes.The paper presents it as addressing both modularity’s resolution limit and its tendency to split larger communities.

3 FINE-TUNED ALGORITHM

The paper develops Fine-tuned Q and Fine-tuned Qds, which alternate quality-improving split and merge operations; Fine-tuned Qds addresses modularity-density optimization where greedy agglomeration fails.

  • Qds simultaneously addresses modularity’s tendency to favor small communities and its resolution limit favoring excessively large communities.
  • 3.1 Greedy Algorithm Fails to Optimize Qds: Greedy Qds can merge nodes from different true communities because singleton-node Qds values favor connected pairs with the largest degree sums.In the clique example, it merges nodes 3 and 5, although they belong to different cliques.
  • 3.1 Greedy Algorithm Fails to Optimize Qds: The two-clique structure has Qds 0.4183, exceeding 0.2487 for one merged community, demonstrating why Qds optimization should preserve the true structure.
  • 3.2 Fine-tuned Algorithm: Fine-tuned Q and Fine-tuned Qds iteratively alternate split and merging stages to improve the selected quality metric.The algorithm can start from one community containing all nodes or refine communities produced by another detector.
  • 3.2 Fine-tuned Algorithm: During splitting, ratio-cut-inspired spectral bisection divides a community when the quality metric improves, using the Fiedler vector of the Laplacian.The ratio-cut objective favors balanced divisions, while Laplacian spectral bisection approximates the NP-complete partitioning problem.
  • 3.2 Fine-tuned Algorithm: The algorithm stops when neither splitting nor merging improves the metric or when the community count remains unchanged after a full iteration.The split-stage complexity is O(|E| + |V|log|V|) for Fine-tuned Q and O(|E| + |V|log|V| + |C||V|) for Fine-tuned Qds.

4 EXPERIMENTAL RESULTS

The experiments compare Greedy Q, Fine-tuned Q, and Fine-tuned Qds across real, clique, and LFR benchmark networks. Fine-tuned Qds is reported as the most effective and can improve results from other algorithms.

  • The comparison covers four real networks, a classical clique network, and LFR benchmark instances spanning wide parameter ranges.
  • Fine-tuned Qds is the most effective method among the three, followed by Fine-tuned Q.
  • Fine-tuned Qds can be applied to communities detected by other algorithms to significantly improve their detection results.
  • The Fine-tuned Q split stage is equivalent to spectral methods, while its additional merge operation gives it better performance than those spectral algorithms.

4.1 Evaluation Metrics

The evaluation uses information-theoretic, cluster-matching, and pair-counting metrics to compare detected partitions with ground-truth or reference partitions. The section also presents metric values and karate-club visualizations for the three algorithms.

  • Evaluation metrics comprise VI and NMI, F-measure and NVD, and RI, ARI, and JI across three methodological categories.
  • Information-Theoretic Metrics: VI measures partition distance, whereas NMI measures partition similarity using entropy and mutual information.
  • Cluster-Matching Metrics: F-measure evaluates partition similarity through community matching, while NVD quantifies partition distance using the same matching perspective.
  • Pair-Counting Metrics: Pair-counting metrics evaluate how node pairs are classified across two partitions; RI, ARI, and JI quantify their agreement or overlap.
  • Zachary’s Karate Club Network: Table 1 reports metric values for Greedy Q, Fine-tuned Q, and Fine-tuned Qds on Zachary’s karate club network.
  • Zachary’s Karate Club Network: Figure 2 compares the ground-truth karate-club partition with communities detected by Greedy Q, Fine-tuned Q, and Fine-tuned Qds.

4.2 Real Networks

The algorithms are evaluated on four real networks, with ground-truth comparisons available for the karate club and American college football networks. Fine-tuned Qds performs best on the football network and yields large Qds improvements when refining other partitions.

  • Zachary’s Karate Club Network: On the karate club network, Fine-tuned Q and Fine-tuned Qds maximize Q and Qds respectively, while most ground-truth metrics favor Greedy Q.NMI and NVD instead identify Fine-tuned Qds as best, illustrating disagreement between modularity-based and ground-truth measures.
  • Zachary’s Karate Club Network: Fine-tuned Q and Fine-tuned Qds recover the ground-truth communities at their first iteration, unlike Greedy Q.The authors interpret these intermediate partitions as evidence of superiority over Greedy Q.
  • American College Football Network: On the American college football network, Fine-tuned Qds achieves the best values for all nine metrics, followed by Fine-tuned Q.The detected community counts are seven for Greedy Q, nine for Fine-tuned Q, and twelve for Fine-tuned Qds, matching the twelve ground-truth communities only for Fine-tuned Qds.
  • American College Football Network: Applying Fine-tuned Qds to Greedy Q and Fine-tuned Q partitions significantly improves their metric values and produces twelve communities in both cases.The improved structures therefore contain the same number of communities as the football network’s ground truth.
  • PGP Network: On the PGP network without ground truth, Greedy Q maximizes Q, whereas Fine-tuned Qds maximizes Qds and has a much larger Qds value than the alternatives.The network contains 10,680 nodes and 24,316 edges.
  • AS Level Internet: On AS level Internet, Fine-tuned Q and Fine-tuned Qds maximize Q and Qds respectively, with Fine-tuned Qds having a much larger Qds value than the alternatives.This network also lacks ground-truth communities, so only Q and Qds are calculated.

4.3 Synthetic Networks

Synthetic-network experiments show that Fine-tuned Qds avoids modularity's resolution-limit behavior and generally aligns better with ground-truth community quality than Q-based methods.

  • Clique Network: The ring network contains thirty five-node cliques linked by single edges, with each clique intuitively forming one community.Greedy Q and Fine-tuned Q instead detect sixteen communities, merging fourteen pairs of cliques.
  • Clique Network: Fine-tuned Qds finds exactly thirty communities in the ring, whereas Greedy Q and Fine-tuned Q merge cliques into larger communities.Fine-tuned Qds achieves about twice their Qds value, although Greedy Q and Fine-tuned Q obtain the highest Q.
  • LFR Benchmark Networks: On LFR networks, Greedy Q performs best across all nine measurements at µ = 0.05, while Fine-tuned Qds performs best on almost all ground-truth metrics for µ = 0.1–0.5.Fine-tuned Q remains second-best for Qds and nearly all ground-truth metrics in that range.
  • LFR Benchmark Networks: For modularity Q on LFR networks, Greedy Q ranks first, Fine-tuned Q second, and Fine-tuned Qds last.This contrasts with Fine-tuned Qds's stronger performance on Qds and ground-truth-based measurements.
  • LFR Benchmark Networks: The seven ground-truth measurements are consistent with Qds but not Q, and Fine-tuned Qds performs best among the three algorithms for µ > 0.05.These results support Qds as a community-quality metric and Fine-tuned Qds as an effective Qds optimizer.
  • LFR Benchmark Networks: Applying Fine-tuned Qds to Greedy Q or Fine-tuned Q outputs significantly improves nearly all measurements, sometimes exceeding Fine-tuned Qds applied directly.Exceptions occur in some cases for Q.

5 CONCLUSION

The paper reviews modularity optimization's opposing community-size biases and evaluates Qds-based fine-tuning as an alternative. Across real and synthetic networks, Fine-tuned Qds performs best and improves results from other algorithms.

  • Modularity and Qds: Modularity optimization can split large communities or merge smaller communities because of the resolution-limit problem.The paper reviews quality metrics intended to address these two issues, including Modularity Density Qds.
  • Algorithms and Evaluation: The paper proposes Fine-tuned Qds, an efficient algorithm for maximizing Qds that can also optimize any community-quality metric.It compares Greedy Q, Fine-tuned Q, and Fine-tuned Qds using seven ground-truth metrics across real, clique, and LFR networks.
  • Findings: Fine-tuned Qds performs best among the three algorithms, followed by Fine-tuned Q, and can dramatically improve community-detection results from other algorithms.The experiments also find that all seven ground-truth metrics agree with Qds but not Q.
Loading 1507.00787v1…