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