Identifying high betweenness centrality nodes in large social networks

Nicolas Kourtellis, Tharaka Alahakoon, Ramanuja Simha, Adriana Iamnitchi, Rahul TripathiSoc. Netw. Anal. Min 2013 · DOI · OpenReview

TL;DR

This paper introduces "κ-path centrality," a novel metric for identifying influential nodes in large social networks. They also present a randomized algorithm, RA-κpath, that efficiently estimates this centrality, achieving significant speedups over existing methods while maintaining high accuracy in identifying top central nodes.

What Problem Does This Paper Address?

Identifying "central" or "influential" nodes is crucial in understanding and managing large-scale networks, from social media to communication systems. Betweenness centrality is a key metric for this, quantifying how often a node lies on the shortest paths between other nodes. However, calculating exact betweenness centrality is computationally prohibitive for massive networks (millions of nodes and edges). Existing approximation algorithms often sacrifice accuracy for speed, especially as network size grows. This paper aims to bridge this gap by proposing a new centrality measure and a highly efficient randomized algorithm for its estimation.

Methods

The core contribution is the introduction of κ-path centrality. Unlike traditional betweenness centrality that considers all shortest paths, κ-path centrality limits its scope to "random simple paths" of at most κ edges. This is motivated by the observation that in social networks, influence often diminishes with distance, and information might not always travel along the shortest path.

To estimate κ-path centrality efficiently, the authors developed the RA-κpath algorithm. This randomized algorithm works by simulating a large number of random walks (paths) of length up to κ starting from random nodes. It then counts how many of these paths pass through each node. The algorithm is designed to provide an estimate with a guaranteed additive error and high probability, running in time complexity of $O(\kappa^3 n^{2-2\alpha} \log n)$, where $\alpha$ is a parameter controlling the accuracy-runtime trade-off.

Datasets

The authors evaluated their approach on a variety of real-world social networks, including:

  • File sharing networks: Kazaa, P2P-Gnutella31
  • Citation networks: SciMet, Cit-HepPh
  • Co-authorship networks: Geom, CA-CondMat, Cond-Mat-2005
  • Collaboration networks: CA-AstroPh
  • Communication networks: Email-Enron
  • Social networks: Soc-Epinions1, Soc-Slashdot0902

They also generated synthetic social networks with sizes ranging from 1K to 100K nodes to test scalability.

Key Insights and Ideas

  • Influence decays with distance: The paper leverages the intuition that nodes far apart in a network are less likely to influence each other, making very long shortest paths less relevant for identifying key influencers.
  • Random paths capture real-world dynamics: Information and influence don't always follow the absolute shortest path. Considering random simple paths of a limited length (κ) can better model real-world diffusion processes.
  • Accuracy-Speedup Trade-off is tunable: The RA-κpath algorithm's parameters (α and κ) allow users to explicitly balance the desired accuracy with computational speed.
  • RA-κpath excels at identifying top nodes: The algorithm demonstrates a strong ability to pinpoint the most central nodes, outperforming other approximation methods in this specific task.

Key Results

  • High Correlation: RA-κpath achieved a high correlation (0.70 to 0.95) with exact betweenness centrality across various network sizes and types.
  • Significant Speedup: The algorithm provided speedups of up to 6 orders of magnitude compared to Brandes' exact algorithm for networks with over 10K nodes.
  • Top-N% Node Identification: RA-κpath consistently outperformed RA-Brandes and AS-Brandes in identifying the top 1% of high betweenness centrality nodes, showing a significant advantage (10-40% higher overlap).
  • Parameter Sensitivity: The best correlation was generally achieved with lower values of α (closer to 0) and higher values of κ (up to 20), while speedup increased with higher α. Optimal parameters were suggested as α=0.2 and κ=ln(n+m).

Limitations and Future Work

  • Ordering of low-centrality nodes: The paper notes that for top-5% and top-10% node identification, RA-κpath's performance slightly decreased. This is attributed to the arbitrary ordering of low-κ-path centrality nodes with similar values, which might incorrectly enter the top central node set.
  • Future Work: The authors plan to further investigate this ordering issue and explore ways to improve the relative ranking of nodes to enhance performance for identifying broader sets of central nodes. They also suggest that RA-κpath can be applied to other domains like data placement and diffusion in large networks.

Summary updated

Abstract

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.
BibTeX
@inproceedings{kourtellis2013identifying,
  author = {Nicolas Kourtellis and Tharaka Alahakoon and Ramanuja Simha and Adriana Iamnitchi and Rahul Tripathi},
  title = {{Identifying high betweenness centrality nodes in large social networks}},
  booktitle = {Soc. Netw. Anal. Min},
  year = {2013},
  doi = {10.1007/s13278-012-0076-6},
}
Figure