Efficient Algorithms for Computing Random Walk Centrality

• URL: http://arxiv.org/abs/2510.20604v1
• Date: Thu, 23 Oct 2025 14:36:38 GMT
• Title: Efficient Algorithms for Computing Random Walk Centrality
• Authors: Changan Liu, Zixuan Xie, Ahad N. Zehmakan, Zhongzhi Zhang,
• Abstract summary: We present a novel formulation of random walk centrality, underpinning two scalable algorithms.<n>Experiments on large real-world networks, including one with over 10 million nodes, demonstrate the efficiency and approximation quality of the proposed algorithms.
• Score: 19.36361626345712
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Random walk centrality is a fundamental metric in graph mining for quantifying node importance and influence, defined as the weighted average of hitting times to a node from all other nodes. Despite its ability to capture rich graph structural information and its wide range of applications, computing this measure for large networks remains impractical due to the computational demands of existing methods. In this paper, we present a novel formulation of random walk centrality, underpinning two scalable algorithms: one leveraging approximate Cholesky factorization and sparse inverse estimation, while the other sampling rooted spanning trees. Both algorithms operate in near-linear time and provide strong approximation guarantees. Extensive experiments on large real-world networks, including one with over 10 million nodes, demonstrate the efficiency and approximation quality of the proposed algorithms.

Related papers

• Fast Geometric Embedding for Node Influence Maximization [49.84018914962972]
  We introduce an efficient force layout algorithm that embeds a graph into a low-dimensional space, where the radial distance from the origin serves as a proxy for centrality measures.<n>As an application, it turns out that the proposed embedding allows to find high-influence nodes in a network, and provides a fast and scalable alternative to the standard greedy algorithm.
  arXiv  Detail & Related papers  (2025-06-09T05:21:56Z)
• Approximate Contraction of Arbitrary Tensor Networks with a Flexible and Efficient Density Matrix Algorithm [8.329034093208826]
  We introduce a method to efficiently approximate tensor network contractions using low-rank approximations.<n>The proposed algorithm has the flexibility to incorporate a large portion of the environment when performing low-rank approximations.
  arXiv  Detail & Related papers  (2024-06-14T07:13:52Z)
• A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
  Subset selection is a fundamental problem that can play a key role in identifying smaller portions of the training data. We develop a novel factor 3-approximation algorithm to compute subsets based on the weighted sum of both k-center and uncertainty sampling objective functions.
  arXiv  Detail & Related papers  (2023-12-17T04:41:07Z)
• Community detection using low-dimensional network embedding algorithms [1.052782170493037]
  We rigorously understand the performance of two major algorithms, DeepWalk and node2vec, in recovering communities for canonical network models. We prove that, given some fixed co-occurrence window, node2vec using random walks with a low non-backtracking probability can succeed for much sparser networks.
  arXiv  Detail & Related papers  (2021-11-04T14:57:43Z)
• Degree-Based Random Walk Approach for Graph Embedding [0.0]
  A computationally less intensive and node connectivity aware uniform sampling method is proposed. The advantages of the proposed algorithm become more enhanced when the algorithm is applied to large graphs.
  arXiv  Detail & Related papers  (2021-10-21T19:16:16Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Consistency of random-walk based network embedding algorithms [13.214230533788932]
  We study the node2vec and DeepWalk algorithms through the perspective of matrix factorization. Our results indicate a subtle interplay between the sparsity of the observed networks, the window sizes of the random walks, and the convergence rates of the node2vec/DeepWalk embedding.
  arXiv  Detail & Related papers  (2021-01-18T22:49:22Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  We propose a new low-cardinality algorithm that generalizes the local update to maximize a semidefinite relaxation derived from Leiden-k-cut. This proposed algorithm is scalable, outperforms state-of-the-art algorithms, and outperforms in real-world time with little additional cost.
  arXiv  Detail & Related papers  (2020-12-04T15:46:30Z)
• Quantized Decentralized Stochastic Learning over Directed Graphs [54.005946490293496]
  We consider a decentralized learning problem where data points are distributed among computing nodes communicating over a directed graph.<n>As the model size gets large, decentralized learning faces a major bottleneck that is the communication load due to each node transmitting messages (model updates) to its neighbors.<n>We propose the quantized decentralized learning algorithm over directed graphs that is based on the push-sum algorithm in decentralized consensus optimization.
  arXiv  Detail & Related papers  (2020-02-23T18:25:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.