Source-linked AI summary
Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
Andrea Lancichinetti, Santo Fortunato
TL;DR
Community-detection algorithms lack sufficiently reliable testing benchmarks, especially for networks with directed, weighted, heterogeneous, or overlapping structure. The paper develops benchmark graphs covering these features and tests modularity optimization, revealing performance effects and failure modes tied to network structure and link weights.
Problem
Community-detection methods lack thoroughly tested benchmarks, while real networks often have directed, weighted, heterogeneous, and overlapping structure.
Method
The paper extends benchmark graphs with fat-tailed degree and community-size distributions, directed and weighted links, and optional overlapping memberships.
Results
Modularity optimization can merge small communities when inter-community links carry more weight, producing partitions unlike the planted structure.
Takeaways & Limitations
The resulting benchmark suite provides tools for stringent, objective testing of community-detection algorithms across directed, weighted, and overlapping networks.
Abstract
from arXiv · showhide
Many complex networks display a mesoscopic structure with groups of nodes sharing many links with the other nodes in their group and comparatively few with nodes of different groups. This feature is known as community structure and encodes precious information about the organization and the function of the nodes. Many algorithms have been proposed but it is not yet clear how they should be tested. Recently we have proposed a general class of undirected and unweighted benchmark graphs, with heterogenous distributions of node degree and community size. An increasing attention has been recently devoted to develop algorithms able to consider the direction and the weight of the links, which require suitable benchmark graphs for testing. In this paper we extend the basic ideas behind our previous benchmark to generate directed and weighted networks with built-in community structure. We also consider the possibility that nodes belong to more communities, a feature occurring in real systems, like, e. g., social networks. As a practical application, we show how modularity optimization performs on our new benchmark.
I. INTRODUCTION
Community detection is fundamental, but existing benchmarks have not thoroughly tested algorithms and often use overly simple, unrealistic structures. The paper extends benchmarking to directed, weighted, and overlapping communities while retaining heterogeneous network features.
- Community detection lacks an agreed set of reliable algorithms because current techniques have not been thoroughly tested.
- The commonly used Girvan–Newman benchmark has equal expected node degrees and equal-sized communities, unlike heterogeneous real networks.
- A newer benchmark introduces power-law distributions of node degree and community size, creating a harder test that can expose algorithmic limits.
- Real networks often contain directed, weighted, and overlapping communities, but detecting such structures is highly non-trivial.
- The paper extends benchmarking to directed and weighted networks and allows nodes to belong to multiple communities.
- The benchmark-generation algorithms scale linearly with the number of links and reduce fluctuations between graph realizations.
II. THE BENCHMARK
The benchmark construction begins with overlapping communities in undirected graphs and then extends the procedure to weighted and directed graphs.
- The benchmark algorithm first constructs undirected graphs with overlapping communities, then extends the construction to weighted and directed networks.
A. Unweighted benchmark with overlapping nodes
The benchmark assigns heterogeneous node memberships, degrees, and community sizes, then combines community subgraphs with rewired external links. Its rewiring preserves node degrees, drives external internal links toward zero, and yields near-linear construction when few iterations suffice.
- Benchmark construction: The algorithm assigns each node a membership count and degree, while community sizes are drawn separately from power-law distributions.The membership and degree distributions can be heterogeneous, and the community-size distribution is constrained to match total memberships.
- Benchmark construction: A bipartite configuration model matches node membership stubs to community-size stubs, thereby assigning nodes to communities.Each community has sξ stubs and each node has νi stubs.
- Internal links: Community subgraphs are generated with prescribed degree sequences, while equipartition distributes each node’s internal degree across its communities.The construction uses configuration-model subgraphs and rewiring to avoid multiple links.
- External links: External links are generated with degree sequence k_i^(ext)=µ_tk_i and rewired whenever endpoints share a community, without changing node degrees.The rewiring replaces A−B and C−D with A−C and B−D, reducing or preserving the number of internal external-graph links.
- External links: After a few sweeps, G(ext) reaches a steady state with internal links very close to zero, provided no node has degree approximately N.The number of internal links cannot increase during rewiring and typically decreases rapidly.
- Properties and validation: The construction has complexity O(m) when rewiring takes only a few iterations, and the resulting mixing-parameter distribution is limited mainly by integer round-off.For the illustrated network, fewer than 2100 rewiring steps were needed; the approximation assumes communities are small relative to the network.
B. Weighted networks
The weighted benchmark first generates an unweighted network, then assigns positive link weights to match prescribed node strengths and internal-strength mixing. A greedy iterative procedure minimizes the resulting variance, with exponential convergence and overall O(m) complexity.
- The construction starts from an unweighted network with topological mixing parameter µt and assigns a positive real weight to every link.
- Node strengths follow si = kβ, while µw sets each node’s internal strength to s(in)_i = (1−µw)si.Internal strength sums weights on links to neighbors sharing at least one community membership.
- Weight assignment is formulated as minimizing Var({wij}) subject to target total, internal, and external strengths.The target strengths are defined through the weighted links and the membership indicator κ(i, j).
- A greedy algorithm repeatedly updates link weights across node sweeps until Var({wij}) reaches a steady state while maintaining positive weights.Each update adjusts weights using the difference between target strength and the current weighted degree, then updates neighboring contributions.
- Var({wij}) decreases at least exponentially with iteration sweeps, so convergence depends slowly on network size and total complexity remains O(m).Figure 5 tracks the variance after each update, with each point representing one sweep over all nodes.
C. Directed networks
The benchmark generation procedure extends to directed and directed-weighted networks by sampling separate in- and outdegree sequences, preserving them during rewiring, and assigning strengths from total degree. It can also encode directed flows through constraints on community-level incoming and outgoing links, although modularity optimization may miss such structures.
- Directed benchmark construction: Directed benchmarks use indegree and outdegree sequences, with separate internal in- and out-degrees controlled by mixing parameters.The two mixing parameters may be set equal for simplicity.
- Directed benchmark construction: The directed configuration model replaces the undirected parity condition, while rewiring preserves both indegree and outdegree distributions.Internal degree constraints may require modifying the internal outdegree sequence.
- Weights: Directed and weighted networks assign node strength as s_i = (y_i + z_i)^β while considering neighbors regardless of link direction.A neighbor may be counted twice when links run in both directions.
- Flows and detection: Community-level constraints can generate directed flows, but balance-based modularity may fail when flow cycles separate groups.For a three-group cycle, the planted partition has directed modularity Q = 0 while the graph maximum is positive for another partition.
III. TESTS
The tests evaluate modularity optimization on directed and weighted benchmarks and CPM on overlapping benchmarks using normalized mutual information. Results show degradation for directed graphs as size increases or average degree decreases, weight-induced community mergers, and CPM dependence on clique size, community size, and network size.
- Experimental design: The experiments test modularity optimization on directed and weighted graphs and CPM on overlapping graphs, measuring similarity with normalized mutual information.Modularity optimization uses simulated annealing; normalized mutual information is chosen because it is common in community-detection studies.
- Directed networks: Directed modularity optimization performs worse as the number of nodes increases or the average degree decreases.The pattern is similar to the earlier undirected benchmark results.
- Weighted networks: When µt < µw, heavier intercommunity links produce more mergers between small communities and can make the recovered partition differ from the planted one.This causes the µt = 0.5 setting to outperform the µt = µw setting in the range 0 ≤ µw < 0.5, contrary to the expected ordering.
- Overlapping communities: For overlapping benchmarks, CPM performs worst with triangles, better with 4- and 5-cliques, and better when communities are smaller.The tests vary the fraction of overlapping nodes and use networks of 1000 and 5000 nodes.
- Overlapping communities: CPM performs better on the 5000-node networks than on the 1000-node networks in these tests.The comparison uses the same other benchmark parameters as the corresponding figures.
IV. SUMMARY
The paper introduces benchmark graphs for directed and weighted networks with heterogeneous degree and community-size distributions and optional overlapping communities. It provides generation software and uses the benchmarks to test community-detection methods.
- Contributions: The new benchmarks extend earlier graphs to directed and weighted networks while retaining fat-tailed node-degree and community-size distributions.They also support overlapping communities, a feature observed in real networks.
- Contributions: The benchmark suite provides tools for stringent objective tests of community-detection algorithms.The authors developed and tested freely downloadable software for generating each benchmark class.