Source-linked AI summary
LinkRank: Finding communities in directed networks
Youngdo Kim, Seung-Woo Son, Hawoong Jeong
TL;DR
The paper addresses community identification when directed links encode information such as asymmetric influence or flow. It introduces LinkRank-based modularity to account for direction and evaluates it on a directed model network. The method correctly and robustly detects the embedded communities across the tested model settings, unlike a direction-ignoring method.
Problem
Community detection in directed networks requires accounting for link direction because direction can encode asymmetric influence or information flow.
Method
The paper generalizes modularity using LinkRank, a quantity indicating link importance in directed networks, with PageRank-based modeling and a directed model-network evaluation.
Results
The method correctly and robustly detects the model network’s embedded communities, while the direction-ignoring method cannot; this pattern remains qualitatively the same across tested m and n values.
Takeaways & Limitations
The results support using direction-aware modularity for community detection in directed networks rather than ignoring link direction.
Abstract
from arXiv · showhide
To identify communities in directed networks, we propose a generalized form of modularity in directed networks by introducing a new quantity LinkRank, which can be considered as the PageRank of links. This generalization is consistent with the original modularity in undirected networks and the modularity optimization methods developed for undirected networks can be directly applied to directed networks by optimizing our new modularity. Also, a model network, which can be used as a benchmark network in further community studies, is proposed to verify our method. Our method is supposed to find communities effectively in citation- or reference-based directed networks.
I. INTRODUCTION
Community structure is important for understanding complex networks, but existing modularity-based methods are limited when links are directed. The paper motivates a LinkRank-based modularity that preserves link direction while extending established community-detection methods to directed networks.
- Community structure captures groups of densely interconnected nodes and is linked to the dynamics and functions of complex networks.
- Modularity is widely used to evaluate community assignments, despite reported resolution-limit and balanced-partition biases.
- Existing modularity-optimization methods are designed for undirected networks, whereas many real-world networks, including citation and email networks, are directed.
- Link direction can encode asymmetric influence or information flow, so ignoring it may misrepresent network dynamics and community assignments.
- Prior directed-network methods do not share a common community definition, and one generalized modularity is reported to have limitations in its stated interpretation.
- The paper proposes LinkRank-based directed modularity, changes the community definition accordingly, and reports effective community detection on a model network.
II. GENERALIZED MODULARITY
The section reviews modularity for undirected networks and Arenas et al.’s directional generalization, then shows why the latter may not distinguish link direction as intended.
- Undirected modularity: Modularity compares within-community link fraction with its expected value under random connections preserving community divisions and node strengths.A high modularity indicates stronger-than-random community structure, although random fluctuations can also produce high maximized values.
- Directional generalization: Arenas et al. generalized modularity by replacing undirected strength terms with out-strength and in-strength terms for directed links.The total strength becomes M = Σ_i,j w_ij, where w_ij is the weight from node i to node j.
- Directional limitation: In the illustrated directed binary network, q_AB and q_A′B′ are equal even though A and A′ have higher out-degree while B and B′ have higher in-degree.The figure gives q_AB = q_A′B′ = 1 − 5/M.
- Directional limitation: The generalized modularity treats links between the same community pair with the same community indicator regardless of direction.Because δ_ci,cj equals δ_cj,ci, contributions from opposite directional configurations can become equal.
- Interpretation: The generalized modularity’s additional term groups nodes with positive net-strength together and nodes with negative net-strength together.In an extreme case lacking community structure after ignoring directions, maximizing Q_d divides the network according to net-strength sign.
III. LINKRANK AND A NEW GENERALIZATION OF MODULARITY
The paper introduces LinkRank, a PageRank-like measure of link importance, and uses it to define directed-network modularity through random-walk behavior. The resulting formulation preserves the undirected interpretation, supports established optimization methods, and is scoped to directed networks whose link directions represent meaningful flow or influence.
- LinkRank: LinkRank is the stationary-state probability that a random walker follows a directed link from node i to node j.It combines the PageRank probability of visiting node i with the transition probability from i to j.
- Community definition: Under Qlr, a community is a group in which a random walker is more likely to remain, rather than simply a group with many internal links.The paper states that this definition is consistent with the traditional undirected-network definition.
- New modularity: The new modularity measures time spent walking within communities minus the expected fraction under a PageRank-preserving randomized network.The null model conserves the PageRank sequence while randomly rewiring links, rather than conserving only node strengths.
- Consistency: In undirected networks, the LinkRank formulation becomes consistent with the original modularity because stationary visitation probabilities reduce to local strength-based quantities.The paper connects the random-walk formulation to the standard fraction-of-internal-links interpretation.
- Optimization: Established optimization techniques for undirected modularity can generally be applied directly to the new directed-network modularity.The eigenvector-based method requires a symmetry-restoring adjustment.
- Scope: The method is intended for directed networks where link direction represents citation, reference, information flow, or related asymmetric relations.The paper cautions that direction does not have a universal meaning across all directed networks and discusses sensitivity to the PageRank parameter α.
IV. RELATION WITH OTHER COMMUNITY IDENTIFICATION WORKS IN DIRECTED NETWORKS
The paper relates LinkRank modularity to prior directed-network community methods by emphasizing random-walk retention and directional asymmetry. On the cited sixteen-node model network, LinkRank produces the same communities as Rosvall and Bergstrom’s map-equation method.
- Relation to Leicht–Newman: LinkRank and Leicht–Newman modularity both account for the asymmetry of oppositely directed links, but LinkRank does so through random-walk theory.The paper states that the two approaches treat direction information in a similar way.
- Relation to Rosvall–Bergstrom: Rosvall and Bergstrom’s map equation and LinkRank share a community definition based on a random walker being more likely to remain within a group than leave it.The comparison is made on a directed network originally proposed by Rosvall and Bergstrom.
V. APPLICATION TO A MODEL NETWORK
The authors test LinkRank-based directed modularity on a ring of small directed subnetworks and compare it with a direction-ignoring method. Across the model network, VOI and modularity show that the proposed method preserves the embedded communities more effectively.
- Model network: The test network contains n directed small rings of m nodes arranged on a larger ring, with inter-ring link weight w and intra-ring link weight 1.The small rings are treated as embedded communities, and w controls coupling between them.
- Evaluation: VOI compares detected community assignments with the embedded structure, with larger values indicating greater disagreement.The study uses VOI as a metric for differences between community assignments.
- Results: For m = n = 8, both methods match the embedded communities when w is small, but the direction-ignoring method diverges once w exceeds 1.9.The direction-ignoring method’s VOI increases and eventually reaches a stationary value, whereas the proposed method remains identical to the embedded structure across the illustrated range.
- Results: When w exceeds 4.3, the direction-ignoring method produces a stationary assignment that groups nodes connected by inter-ring links into the same communities.This assignment is favored because large inter-ring weights make those connected nodes more likely to be assigned together.
- Modularity comparison: The proposed modularity Qlr decreases continuously as w increases, while Qud changes behavior and favors a different assignment after w exceeds 1.9.In the transitional range w ∈(1.9, 4.3), simulated annealing finds modularity values slightly above the analytical expression because transitional assignments exist.
- Robustness: Across varied m and n, the VOI and modularity results remain qualitatively consistent: the proposed method detects the model communities robustly, unlike the direction-ignoring method.The reported qualitative pattern is not limited to m = n = 8.
VI. SUMMARY
The paper introduces LinkRank-based modularity for directed networks and defines communities through random-walk retention. The formulation is consistent with undirected modularity, supports existing optimization methods, and is validated with a reusable model benchmark.
- Contribution: LinkRank-based modularity measures directed-network community structure through link importance and random-walk behavior.Globally, it compares time spent moving within communities with the expected fraction; locally, higher-LinkRank links are more likely to be intra-community links.
- Contribution: Under the new definition, a community is a group of nodes in which a random walker is more likely to stay.This changes the community definition in accordance with the new modularity.
- Consistency: The new modularity is consistent with Newman and Girvan’s original modularity for undirected networks.The paper reports this consistency as a proven property of the formulation.
- Benchmark: The model network is proposed as a benchmark for future studies of community identification.The paper uses this network to verify the proposed method.
- Practical use: Most modularity optimization methods developed for undirected networks can be applied to directed networks by optimizing the new modularity.This is presented as a practical advantage of the method.