Source-linked AI summary
Mixing local and global information for community detection in large networks
Pasquale De Meo, Emilio Ferrara, Giacomo Fiumara, Alessandro Provetti
TL;DR
Large-network community detection faces a trade-off: global modularity methods use whole-network topology but scale poorly, while local methods scale but can produce poorer results. CONCLUDE derives edge centralities and vertex distances from finite non-backtracking information walks, then clusters using those distances. Its analyzed worst-case time complexity is near-linear in the number of edges and comparable to local algorithms.
Problem
Global modularity methods use whole-network topology but scale poorly, whereas local methods scale to large networks but may yield poorer clustering results.
Source: §1 · p. 2, §2.1 · p. 5, §2.2 · p. 6Method
CONCLUDE estimates edge centrality through bounded information propagation, uses centrality to map vertices and compute distances, then clusters by those distances.
Source: §1 · p. 3Results
CONCLUDE's worst-case time complexity is near-linear in the number of edges, with performance comparable to local algorithms.
Source: §1 · p. 4Takeaways & Limitations
The edge-centrality-based Euclidean mapping also supports complex analysis tasks such as finding a vertex's k-nearest neighbors.
Source: §1 · p. 4Under some circumstances, modularity optimization favors merging small communities, potentially overlooking communities relevant to the graph's structure.
Source: §2.2 · p. 6
Abstract
from arXiv · showhide
The problem of clustering large complex networks plays a key role in several scientific fields ranging from Biology to Sociology and Computer Science. Many approaches to clustering complex networks are based on the idea of maximizing a network modularity function. Some of these approaches can be classified as global because they exploit knowledge about the whole network topology to find clusters. Other approaches, instead, can be interpreted as local because they require only a partial knowledge of the network topology, e.g., the neighbors of a vertex. Global approaches are able to achieve high values of modularity but they do not scale well on large networks and, therefore, they cannot be applied to analyze on-line social networks like Facebook or YouTube. In contrast, local approaches are fast and scale up to large, real-life networks, at the cost of poorer results than those achieved by local methods. In this article we propose a glocal method to maximizing modularity, i.e., our method uses information at the global level, yet its scalability on large networks is comparable to that of local methods. The proposed method is called COmplex Network CLUster DEtection (or, shortly, CONCLUDE.) It works in two stages: in the first stage it uses an information-propagation model, based on random and non-backtracking walks of finite length, to compute the importance of each edge in keeping the network connected (called edge centrality.) Then, edge centrality is used to map network vertices onto points of an Euclidean space and to compute distances between all pairs of connected vertices. In the second stage, CONCLUDE uses the distances computed in the first stage to partition the network into clusters. CONCLUDE is computationally efficient since in the average case its cost is roughly linear in the number of edges of the network.
1. Introduction
CONCLUDE combines global information with locally informed clustering to address the scalability and resolution-limit challenges of modularity-based community detection. It maps vertices using edge centrality and distances, then clusters them, with near-linear worst-case time complexity in the number of edges.
1. Introduction
- Global modularity methods use whole-network topology but scale poorly, while local methods use neighborhood information yet may become trapped in local optima.Source: §1 · p. 2
- Modularity optimization can miss small communities under topology-dependent circumstances, a limitation known as the resolution limit.Source: §1 · p. 2
- CONCLUDE maps vertices into Euclidean space using edge-centrality-based distances, then applies the Louvain Method to cluster them.Source: §1 · p. 3
- κ-path edge centrality measures the probability that an edge is selected to spread information, estimated through simulated diffusion along bounded, non-backtracking random paths.Source: §1 · p. 3
- Distances use edge centrality to express structural equivalence, mapping groups with likely information exchange to dense Euclidean regions.Source: §1 · pp. 3–4
- For large κ, non-backtracking walks can explore distant graph regions while requiring knowledge only of each visited vertex's neighbors.Source: §1 · pp. 3–4
- CONCLUDE's worst-case time complexity is near-linear in the number of edges, making its performance comparable to local algorithms.Source: §1 · p. 4
- Evaluation covers six real-world datasets, including a Facebook sample with 63,731 vertices and 1,545,684 edges, plus 72 synthetic LFR networks.Source: §1 · p. 4
2. Background
This background section introduces modularity-based community detection, reviews strategies for maximizing modularity, and describes limitations that complicate interpreting modularity scores and detecting small communities.
2.1. Finding Communities by Maximizing Network Modularity
- Modularity Q compares within-community edges with a degree-preserving random null model, treating excess internal density as evidence of community structure.The null model preserves the graph’s degree sequence and supplies the comparison for internal edge density.Source: §2.1 · pp. 4–5
- Modularity maximization is NP-hard; reported approximability is logarithmic for sparse graphs and (1 + ε)-inapproximability for dense graphs.Source: §2.1 · p. 5
- Girvan–Newman ranks edges by betweenness, removes highest-ranked edges iteratively, and treats connected components as communities, but its O(|V|^3) cost remains prohibitive on real-world graphs.Efficient approximations to betweenness or shortest paths do not make the costs practical for real-world graphs.Source: §2.1 · p. 5
- Other strategies include fast agglomerative methods and Louvain; simulated annealing avoids greedy search but can be computationally expensive.The Fast Clustering Algorithm runs in O(|V| log |V|) on sparse graphs, while extremal optimization has worst-case O(|V|^2 log |V|) complexity.Source: §2.1 · pp. 5–6
2.2. Limitations of Network Modularity
- Many partitions can have similar, near-maximum Q despite substantially different clusterings, so scores alone may not distinguish them without additional information about community organization.Source: §2.2 · p. 6
- When a community’s summed vertex degrees are below √m, where m is the graph’s edge count, maximizing Q can favor merging small communities and obscure relevant structure.Source: §2.2 · p. 6
- The resolution limit follows from the whole-graph null model; local modularity is proposed to reflect partial vertex horizons, while modularity-density variants and edge weighting explore alternatives.The cited modularity-density approach is reported to improve results but still suffer from the resolution limit; its parameter can favor small or large communities.Source: §2.2 · pp. 6–7
3. The κ-path edge centrality
κ-path edge centrality ranks edges by how often messages traverse them on random simple paths of bounded length. ERW-Kpath approximates this quantity with random walks and provides a bound on its error and running time.
3. The κ-path edge centrality
- The model allows messages to use random paths rather than requiring shortest paths, which can be unknown to users and costly to compute across large networks.The comparison is with the shortest-path information-flow model discussed for Fortunato et al..Source: §3 · p. 7
- κ-path edge centrality sums, across all source vertices, the probability that a message traverses an edge on a random simple κ-path.A simple κ-path avoids reusing an edge and has length at most κ.Source: §3 · p. 7
- Random walks approximate the centrality because directly considering all simple paths of length at most κ may require examining exponentially many paths.ERW-Kpath simulates message propagation through repeated walks.Source: §3 · p. 8
- The probability that an edge's deviation error is at least ˆϵ is bounded by e^-ρ under Theorem 3.2.The bound concerns the estimate returned by ERW-Kpath after ρ iterations.Source: §3 · p. 9
- In such a case, the ERW-Kpath algorithm has worst-case time complexity O(κα log |V|), and for each edge e ∈ E its deviation error is no larger than 1/|V|^α.Source: §3 · p. 10
4. Computing Distances and Finding Communities
CONCLUDE turns κ-path edge centralities into distances and uses those distances in a modularity-based clustering procedure. The section describes the distance construction and its computational shortcut, the Louvain-inspired partitioning stage, and a comparison with a spectral distance approach.
4.1. Computing Distances between Graph Vertices
- Vertices are close when their neighbors have comparable message-flow probabilities to them; aggregating these comparisons across vertices yields a proximity that embeds the graph in Euclidean space.A group with high-probability message flow maps to a dense region that the paper identifies as a community.Source: §4.1 · p. 11
- High-degree vertices can appear close to almost all others, so the method normalizes proximity and defines distance as d_ij = 1 − σ_ij.The probability of selecting an incident edge is described as proportional to 1/deg(i) when κ is small.Source: §4.1 · pp. 11–12
- O(d(v)^2|V|) is the reduced distance-computation cost, with d(v) denoting average vertex degree.This replaces a naive computation requiring O(|V|^2) iterations by rewriting Equation 7 and using common-neighbor sets.Source: §4.1 · p. 12
4.2. Finding Communities
- CONCLUDE partitions by modularity maximization using a Louvain-inspired procedure, iteratively moving vertices and collapsing clusters into a weighted meta-network until improvement is small.The process is described as costing O(γ|V|), with γ < 5 in the authors’ experience.Source: §4.2 · pp. 12–13
- Compared with the original Louvain Method, CONCLUDE uses global low-distance information to split clusters and can infer edge weights for unweighted networks.The authors state that this weighting strategy performs better in most cases.Source: §4.2 · p. 13
4.3. Comparison with existing definition of distances
- For symmetric graphs and after relaxing non-backtracking paths, the paper relates its distances to the largest-magnitude eigenvalues; unlike the Lanczos comparison [13], it gives its approach an O(κα log |V|) step bound.The authors note that [13] uses Lanczos on sparse matrices but that, to their knowledge, no theoretical worst-case complexity estimate is available for it.Source: §4.3 · pp. 13–14
5. Experimental Results
CONCLUDE is evaluated on synthetic networks with known communities, real-world networks, and edge-centrality distributions. The experiments report strong synthetic NMI, higher modularity than the tested competitors on real-world networks, and heavy-tailed κ-path edge-centrality distributions.
5.1. Cluster Detection
- Synthetic tests use LFR graphs varying γ, β, average degree, and µ; real-world tests compare three algorithms using modularity because ground-truth communities are unknown.The authors describe modularity-based evaluation as a best approximation, noting that robust evaluation without ground truth remains an open problem.Source: §5.1 · p. 14, §5.1.1 · p. 15, §5.1.2 · p. 16
5.1.1. Synthetic networks
- For LFR networks with µ = 0.1–0.3, CONCLUDE generally achieves high NMI, with results stable as average degree and the degree- and community-size exponents vary.The experiments compare detected partitions with the LFR ground truth; the table reports NMI values for the generated configurations.Source: §5.1.1 · p. 15, Table 1 · p. 16
5.1.2. Real-world networks
- CONCLUDE outperforms the tested competitors in real-world network modularity, averaging 5%–15% better than Louvain and up to 25% better than COPRA and OSLOM.The authors attribute the advantage partly to optimizing modularity on a weighted network whose edge weights are produced by ERW-Kpath.Source: §5.1.2 · p. 17, Table 2 · p. 18
5.2. ERW-Kpath and κ-path edge centrality
- Across κ = 5, 10, and 20, edge-centrality values have heavy-tailed distributions, and the plotted curves are described as parallel as κ increases.The figure shows distributions for the five largest networks; the accompanying analysis says each edge’s centrality increases by a constant factor as κ rises.Source: §5.2 · p. 18, Figure 1 · p. 19
- ERW-Kpath-derived weights feed distances between vertex pairs, which are then used for clustering through local modularity optimization, giving CONCLUDE its glocal character.The authors describe the edge weights as reflecting which edges are more likely to be traversed during information spreading.Source: §5.1.2 · pp. 17–18, §5.2 · p. 18
6. Conclusions
The conclusion presents CONCLUDE as a method that performs well across domains and notes that an early implementation is available for independent assessment. It also identifies overlapping communities as a current limitation and a target for future extension.
6. Conclusions
- The authors report that CONCLUDE works well in different domains and say an early implementation has been released for independent assessment.Source: §6 · p. 20
- Future work includes studying online social networks and sociological conjectures, improving other clustering algorithms with κ-path centrality, and evaluating applications in neuroinformatics and bioinformatics.Source: §6 · p. 20
- CONCLUDE produces strong partitions but does not allow communities to overlap, a limitation the authors plan to address.Overlapping membership may matter in settings such as social networks, where users can belong to multiple communities.Source: §6 · p. 20