Source-linked AI summary
Identifying high betweenness centrality nodes in large social networks
Nicolas Kourtellis, Tharaka Alahakoon, Ramanuja Simha, Adriana Iamnitchi, Rahul Tripathi
TL;DR
Computing or estimating betweenness centrality becomes costly as networks grow, despite applications often needing relative importance rather than exact values. The paper introduces κ-path centrality and a randomized estimator; experiments report that it identifies high-betweenness nodes effectively and outperforms earlier approximation algorithms on top-node detection.
Problem
Exact and approximate betweenness methods become infeasible on very large networks as randomized methods lose accuracy and take longer with increasing network size.
Source: §1 · p. 3Method
The paper introduces κ-path centrality, which limits exploration to κ social hops, and a randomized algorithm to estimate it for all network nodes.
Source: §1 · pp. 3–4Results
RA-κpath outperforms AS-Brandes and RA-Brandes in identifying top–1% or top–5% nodes by exact betweenness, with near-optimal performance at α=0.2 and κ=ln(n + m).
Source: §5 · p. 25Takeaways & Limitations
Experiments support κ-path centrality as an alternative to node betweenness because it models information spread and its estimator achieves greater speedup than existing exact or approximate methods.
Source: §5 · p. 25RA-κpath performance decreases for top–5% and top–10% overlap, possibly because close low κ-path values yield arbitrary ordering.
Source: §4.3 · p. 16
Abstract
from arXiv · showhide
This paper proposes an alternative way to identify nodes with high betweenness centrality. It introduces a new metric, k-path centrality, and a randomized algorithm for estimating it, and shows empirically that nodes with high k-path centrality have high node betweenness centrality. The randomized algorithm runs in time $O(\kappa^{3}n^{2-2\alpha}\log n)$ and outputs, for each vertex v, an estimate of its k-path centrality up to additive error of $\pm n^{1/2+ \alpha}$ with probability $1-1/n^2$. Experimental evaluations on real and synthetic social networks show improved accuracy in detecting high betweenness centrality nodes and significantly reduced execution time when compared with existing randomized algorithms.
1 Introduction
Exact betweenness is costly to compute or estimate at large network sizes, though many applications need relative importance rather than exact scores. The paper introduces κ-path centrality and a randomized estimator, then evaluates their relationship to betweenness centrality.
1 Introduction
- Existing exact and randomized betweenness methods become infeasible at million-node scale because estimation accuracy falls and runtime rises with network size.Exact Brandes runs in O(nm) on unweighted graphs and O(nm + n^2 log n) on weighted graphs.Source: §1 · p. 3
- κ-path centrality focuses on nodes’ relative importance and a κ-hop neighborhood, motivated by distant nodes’ limited influence and information traveling along non-shortest paths.The paper argues that identifying important categories, such as the top 1%, can matter more than precisely ordering all nodes.Source: §1 · pp. 3–4
- The paper presents complexity and accuracy analysis for the estimator and extends earlier work with comparisons to other betweenness variants and evaluation on eight new real networks.The evaluation also includes synthetic social networks.Source: §1 · pp. 3–4
- The randomized estimator computes all nodes’ κ-path centrality within additive error n^(1/2+α), with probability at least 1 − 1/n^2, in O(κ^3 n^(2−2α) log n) time.The parameter α controls the tradeoff between accuracy and computation time.Source: §1 · p. 4
- Experiments on real and synthetic social networks found that high κ-path centrality accompanies high betweenness, with lower runtime and higher accuracy than existing algorithms, especially on very large networks.The paper reports comparisons against exact and approximate betweenness methods.Source: §1 · p. 4
2 Node Betweenness Centrality
This section defines node betweenness through shortest paths and reviews exact and randomized algorithms for computing or estimating it. The reviewed randomized methods reduce the sources considered, either by uniform sampling or adaptive sampling.
2 Node Betweenness Centrality
- The section frames betweenness centrality as a global measure of how much a vertex controls information flow between vertex pairs.Source: §2 · p. 4
2.1 Definition and Notations
- Betweenness centrality sums, over endpoint pairs, the fractional count of shortest paths passing through a vertex.The section also introduces graph, edge-weight, path-length, and shortest-path notation.Source: §2.1 · pp. 4–5
2.2 Brandes’ Algorithm
- Brandes’ algorithm computes every vertex’s betweenness in O(nm + n^2 log n) time on weighted graphs or O(nm) on unweighted graphs, using O(m + n) space.It expresses betweenness through dependency scores for each source vertex.Source: §2.2 · p. 5
2.3 RA-Brandes Algorithm
- RA-Brandes estimates all vertices’ betweenness from Θ((log n)/ϵ^2) uniformly sampled source pivots and guarantees additive error ϵn(n − 1) with high probability.Its guarantee is 1 − 1/n^Ω(1).Source: §2.3 · pp. 5–6
2.4 AS-Brandes Algorithm
- AS-Brandes adaptively samples at most T pivots, tracking each vertex until its dependency-score sum exceeds cn or the cutoff is reached.For vertices with betweenness at least n^2/t, it provides a relative-error guarantee using ϵt pivots under the stated probability condition.Source: §2.4 · p. 6
3 K-Path Centrality
The section defines κ-path centrality by modeling bounded random simple message paths and summing the probabilities that they pass through each node. It also presents a randomized estimator with a stated runtime and additive-error guarantee.
3 K-Path Centrality
- κ-path centrality sums, over all source nodes, the probabilities that a message passes through a vertex along a random simple path of at most κ edges.Traversals stop when the current node has no unvisited outgoing neighbor.Source: §3 · p. 7
3.1 Formal Analysis of K-Path Centrality
- Path probabilities are products of successive transition probabilities, and the centrality formulation sums contributions from paths containing v across sources and lengths.For weighted graphs, transition probabilities favor lower-weight edges; for unweighted graphs, forwarding is uniform over unvisited neighbors.Source: §3.1 · pp. 7–8
3.2 Comparison With Variants of Betweenness
- κ-path centrality differs from betweenness variants in its assumptions; k-betweenness restricts shortest paths by length, while random-walk and flow betweenness use different path or flow models.In the worst case, bounded-distance betweenness can have the same complexity as Brandes’ algorithm.Source: §3.2 · pp. 9–10
- RA-κpath samples a start vertex and path length, simulates message traversals, and estimates each node’s centrality from its recorded visits.The pseudocode reinitializes explored-node flags after each traversal and removes counts when a traversal ends before its sampled length.Source: §3.3 · p. 11
- O(κ^3 n^(2−2α) ln n) runtime estimates every vertex’s κ-path centrality within ±n^(1/2+α), with probability at least 1−1/n^2.The algorithm is RA-κpath; its guarantee is stated for each vertex.Source: §3.3 · pp. 11–12
4 Experimental Evaluation
The evaluation compares RA-κpath with Brandes and two randomized betweenness approximations on real and synthetic networks, measuring correlation, top-node overlap, and speedup. RA-κpath performs strongly across these measures, though its top-node overlap declines for larger selected groups.
4 Experimental Evaluation
- Experiments cover real networks from varied application domains and synthetic social networks of 1K, 10K, 50K, and 100K nodes.Ten independently generated networks were used at each synthetic size.Source: §4 · p. 13
4.1 Performance Metrics
- Accuracy is measured by correlation with Brandes’ exact scores and top–N% overlap with its highest-betweenness nodes; runtime is measured as speedup over Brandes.The overlap measure is reported for N = 1, 5, and 10.Source: §4.1 · pp. 13–14
4.2 Comparison with Brandes’ Algorithm
- Correlation rises as α decreases and κ increases, while speedup falls; α = 0.2 and κ = ln(n + m) provide near-optimal performance on both measures.The evaluation reports that the correlation pattern is similar across network sizes and types.Source: §4.2 · p. 14
- Small real networks show maximum correlation of ∼0.75 to ∼0.95 and ∼30 to ∼50× runtime speedup over Brandes; larger real networks show ∼0.70 to ∼0.90 correlation and ∼10^2 to ∼10^4× speedup.Across real and synthetic networks, maximum correlation ranges from ∼0.70 to ∼0.95 and maximum speedup from ∼10^2 to ∼10^6, depending on α, κ, and network size.Source: §4.2 · p. 14
4.3 Comparison with RA-Brandes and AS-Brandes
- For the comparisons, the authors matched the algorithms’ speedups by setting RA-Brandes ε and AS-Brandes s using heuristics based on RA-κpath speedup.The heuristic sets ε = 2 × ((RA-κpath speedup) × ln(n)/n)^1/2 and s = 2 × (RA-κpath speedup).Source: §4.3 · p. 15
- After speedup matching, RA-κpath leads correlation by 0.1 to 0.6 on most real networks, except Kohonen and Soc-Epinions1, and consistently beats both algorithms on larger synthetic networks.RA-Brandes and AS-Brandes correlations also improve during speedup matching.Source: §4.3 · p. 15
- RA-κpath’s top-node overlap declines when the evaluated group expands to the top–5% and top–10%, possibly because near-tied low κ-path scores are arbitrarily ordered.The authors identify improving the relative ranking of nodes as future work.Source: §4.3 · p. 16
- ∼10% to ∼40%: RA-κpath outperforms RA-Brandes and AS-Brandes in top–1% high-betweenness-node overlap across all tested network sizes and types.Table 2 reports the overlap after the algorithms’ speedups were matched.Source: §4.3 · p. 15, Table 2 · p. 24
5 Summary and Discussions
RA-κpath estimates relative betweenness importance with high correlation and large speedups, and the experiments report strong identification of top-ranked nodes. The authors present κ-path centrality as an alternative for assessing node influence and discuss applications in large, dynamic networks.
5 Summary and Discussions
- 0.70–0.95 correlation between exact and approximate centrality indices holds across network sizes, with speedup up to 6 orders of magnitude for networks over 10K nodes.Source: §5 · p. 25
- RA-κpath effectively and quickly identifies top–1% and top–5% nodes by exact betweenness, outperforming AS-Brandes and RA-Brandes.Near-optimal correlation and speedup are reported with α=0.2 and κ=ln(n + m).Source: §5 · p. 25
- κ-path centrality is presented as an alternative to node betweenness because it models information spread and quantifies node influence, while RA-κpath speedups surpass existing exact or approximate methods.Source: §5 · p. 25
- A parallel RA-κpath version was used to approximate betweenness and identify top central players in the Steam Community, with over 12 million players and 88.5 million social edges.Source: §5 · p. 25
- In peer-to-peer overlays, high-betweenness peers relay much traffic, making them relevant to resource provisioning, security monitoring, and traffic characterization; deterministic identification is infeasible at large scale and with high churn.Source: §5 · p. 25
- High-betweenness nodes are proposed as data-placement targets in web graphs and as individuals for propagating security patches through mobile-phone networks.Source: §5 · p. 25