Source-linked AI summary
Generalized Louvain Method for Community Detection in Large Networks
Pasquale De Meo, Emilio Ferrara, Giacomo Fiumara, Alessandro Provetti
TL;DR
Community detection in large networks must balance the quality of global-information methods with the lower cost of local methods. The paper presents a κ-path-based generalization of Louvain that computes edge rankings and node proximities efficiently, then reports reliable community structures while extending naturally to unweighted networks.
Problem
Existing large-network methods often use low-cost local information but do not consider global network topology.
Method
The algorithm ranks edges with κ-path centrality, converts edge weights into pairwise node proximities, and partitions the network by optimizing modularity according to Louvain.
Results
Experiments on synthetic and real-world networks show that the strategy is efficient and robust, with both compared efficient strategies feasible on large networks using standard computing resources.
Takeaways & Limitations
The approach combines local and global information, provides good results after optimization, and can discover communities in possibly large networks.
Abstract
from arXiv · showhide
In this paper we present a novel strategy to discover the community structure of (possibly, large) networks. This approach is based on the well-know concept of network modularity optimization. To do so, our algorithm exploits a novel measure of edge centrality, based on the k-paths. This technique allows to efficiently compute a edge ranking in large networks in near linear time. Once the centrality ranking is calculated, the algorithm computes the pairwise proximity between nodes of the network. Finally, it discovers the community structure adopting a strategy inspired by the well-known state-of-the-art Louvain method (henceforth, LM), efficiently maximizing the network modularity. The experiments we carried out show that our algorithm outperforms other techniques and slightly improves results of the original LM, providing reliable results. Another advantage is that its adoption is naturally extended even to unweighted networks, differently with respect to the LM.
I. INTRODUCTION
The paper addresses community detection by combining global and local network information while retaining computational feasibility for large networks. It generalizes Louvain-style modularity optimization with κ-path edge centrality and supports unweighted networks.
- Community detection methods trade off computational cost against reliability: global approaches are costly but higher quality, whereas local approaches are cheaper but less reliable.
- The proposed strategy uses global network information to identify edges contributing to community structure and ranks them with a novel edge-centrality measure.
- κ-path edge centrality enables near-linear edge ranking, making the approach feasible for analyzing large networks.
- Modularity maximization is NP-complete, motivating heuristic methods such as Girvan–Newman and Louvain; Girvan–Newman is costly for large networks.
- The algorithm computes node pairwise proximity from globally weighted edges and obtains communities by improving Louvain modularity optimization.
- Unlike Louvain, the generalized method can be applied to unweighted networks while exploiting both global and local information.
III. DESIGN GOALS
The design treats community structure as related to information diffusion: edges are ranked by their ability to propagate messages, then proximity and modularity-based partitioning are computed efficiently.
- The motivating model assumes users exchange information through network connections, with communities having denser internal interconnections than external ones.
- The algorithm seeks a partition with optimal network modularity by ranking links according to their aptitude for information diffusion.
- Higher node ability to propagate messages corresponds to higher network centrality, and highly central edges are more likely to connect different communities.
- After efficiently ranking links, the strategy computes pairwise node distances and applies Louvain-style partitioning, evaluating the result with modularity Q.
- κ-path edge centrality uses random simple paths of length at most κ, with an implementation running in O(κ|E|).
IV. κ-PATH EDGE CENTRALITY
κ-path edge centrality measures how frequently edges carry messages along random simple paths of at most κ edges, aggregating traversal percentages over all source nodes.
- For an edge e, κ-path edge centrality Lκ(e) sums, over all source nodes, the percentage of messages from each source that traverse e.
- The measure assumes message traversals follow random simple paths containing at most κ edges.
- The formalization uses the number of κ-paths from source s traversing edge e and the total number of κ-paths originating from s.
A. Fast κ-path Edge Centrality Algorithm
WERW-Kpath efficiently computes κ-path edge centrality through weight assignment and simulated message propagation along random simple paths of length at most κ.
- WERW-Kpath first assigns weights to nodes and edges, then simulates message propagation using random simple paths of length at most κ.
1) Step 1:
Step 1 assigns node and edge weights that initialize source selection and edge-centrality estimation for the network.
- 1) Step 1:: Node weights select source nodes for simulated message propagations, while edge weights initialize and update centrality values.
- 1) Step 1:: Local effective density δ(v) measures a node’s contribution to overall graph connectivity; higher values indicate better connectivity.
- 1) Step 1:: Each edge starts with initial weight ω(e)0 = 1/|E|, equally dividing an initial |E|-point budget across all edges.
2) Step 2:
Step 2 runs bounded, non-cyclic random walks that update edge weights and produce κ-path edge-centrality values with near-linear cost.
- 2) Step 2:: The algorithm simulates ρ simple random walks of length at most κ, selecting outgoing edges with probabilities proportional to their weights.
- 2) Step 2:: Source nodes are selected according to local effective density δ(v), whose role is normalization, before untraversed edges are used in propagation.
- 2) Step 2:: Propagation stops when the path reaches length κ or the current node has no untraversed outgoing edge, preventing cycles.
- 2) Step 2:: Each selected edge receives a bonus β = 1/|E|, is marked traversed, and advances the propagation to the next node.
- 2) Step 2:: At the end of ρ simulations, each edge receives κ-path centrality Lκ(e) equal to its final weight, with time complexity O(κ|E|).
V. COMMUNITY STRUCTURE DETECTION
FKCD detects network communities through three stages: κ-path edge ranking, pairwise node-proximity calculation, and modularity-optimizing partitioning inspired by Louvain.
- V. COMMUNITY STRUCTURE DETECTION: FKCD ranks edges using WERW-Kpath, calculates pairwise proximity between connected nodes, and partitions the network to optimize modularity according to Louvain.
A. Fast κ-path Community Detection
FKCD combines κ-path edge ranking, proximity-based distances, and iterative Louvain-style partitioning to maximize modularity with near-linear computational cost.
- A. Fast κ-path Community Detection: FKCD first invokes WERW-Kpath to label edges with κ-path centrality and obtain a decreasing centrality ranking.
- A. Fast κ-path Community Detection: It then computes proximity for each connected-node pair using an L2 distance derived from the centralities of incident edges.
- A. Fast κ-path Community Detection: Although pairwise proximity theoretically requires O(|V|^2) iterations, optimization reduces its practical cost to O(d(v)|V|).
- A. Fast κ-path Community Detection: Partitioning iteratively moves nodes to communities that maximize modularity, builds a community meta-network, and stops when Q no longer improves.
- A. Fast κ-path Community Detection: High-proximity edges can split communities, while the partitioning cost is O(γ|V|), with γ usually below 5 in the authors’ experience.
- A. Fast κ-path Community Detection: The overall computational cost is near linear: O(κ|E| + d(e)|V| + γ|V|) = O(Γ|E|).
VI. EXPERIMENTAL RESULTS
Experiments were conducted on synthetic and real-world online social networks using standard personal-computer hardware.
- Experiments covered both synthetic networks and real-world online social networks whose datasets were available online.
- All experiments ran on a standard personal computer with an Intel i5 processor and 4 GB of RAM.
A. Synthetic Networks
Synthetic-network evaluation used the Lancichinetti benchmark with 1000-node graphs and varying degree, community-size, and mixing configurations. The strategy achieved fairly good normalized mutual information results while avoiding modularity's resolution-limit effect.
- Synthetic evaluation reproduced the benchmark with N = 1000 nodes and varied degree-distribution and community-size exponents.
- Each exponent pair used average degrees ⟨k⟩ = 15, 20, 25, with six networks generated for each configuration.
- The six-network sets varied the mixing parameter µ from 0.1 through 0.6.
- The strategy produced fairly good normalized mutual information results and avoided the known resolution-limit effect of modularity optimization.
- For these small synthetic networks, FKCD and Louvain Method modularity values were very similar, so a Table I-style classification was omitted.
B. Real-world Networks
Real-world network results compared FKCD with the original Louvain Method using network modularity. Louvain achieved slightly higher results, while both efficient methods remained feasible on large networks using standard computing resources.
- Real-world network experiments qualitatively compared FKCD and the original Louvain Method using network modularity.
- Louvain Method results were slightly higher than FKCD results, while FKCD combined local and global information rather than only local information.
- Using longer κ-paths slightly increased FKCD performance.
- Both efficient strategies remained feasible for large-network analysis with standard computing resources.
- This feasibility matters for Social Network Analysis tools such as NodeXL, which require optimized fast algorithms to compute network community structure.