The identification of crucial nodes in complex networks is a fundamental problem with broad applications in graph mining, influence maximization, and other domains. Centrality measures, such as Markov centrality, quantify node importance by leveraging random walk dynamics, particularly hitting times. However, optimizing group Markov centrality, which is defined as the inverse of the expected hitting time to a node set, poses significant computational challenges due to its NP-hard nature. In this work, we propose efficient approximation algorithms based on dynamic forest sampling and Schur complement techniques to address this problem. Our algorithms exploit the supermodularity of hitting time functions and employ rooted spanning forest sampling to estimate electrical network quantities, enabling scalable and accurate node selection. Theoretical guarantees demonstrate that our methods achieve near-linear solutions with provable error bounds. Extensive experiments on diverse real-world networks validate the practical effectiveness of our approaches, demonstrating significant improvements in computational efficiency and scalability compared to conventional methods.

Derived from effective resistances, the current flow closeness centrality (CFCC) for a group of nodes measures the importance of node groups in an undirected graph with$n$nodes. Given the widespread applications of identifying crucial nodes, we investigate the problem of maximizing CFCC for a node group$S$subject to the cardinality constraint$\vert S \vert =k<<n$. Despite the proven NP-hardness of this problem, we propose two novel greedy algorithms for its solution. Our algorithms are based on spanning forest sampling and Schur complement, which exhibit nearly linear time complexities and achieve an approximation factor of 1- k/k-1 -∊ for any 0 < ∊ < 1. Extensive experiments on real-world graphs illustrate that our algorithms outperform the state-of-the-art method in terms of efficiency and effectiveness, scaling to graphs with millions of nodes.

For random walks on graph \(\mathcal{G}\) with \(n\) vertices and \(m\) edges, the mean hitting time \(H_{j}\) from a vertex chosen from the stationary distribution to vertex \(j\) measures the importance for \(j\) , while the Kemeny constant \(\mathcal{K}\) is the mean hitting time from one vertex to another selected randomly according to the stationary distribution. In this article, we first establish a connection between the two quantities, representing \(\mathcal{K}\) in terms of \(H_{j}\) for all vertices. We then develop an efficient algorithm estimating \(H_{j}\) for all vertices and \(\mathcal{K}\) in nearly linear time of \(m\) . Moreover, we extend the centrality \(H_{j}\) of a single vertex to \(H(S)\) of a vertex set \(S\) , and establish a link between \(H(S)\) and some other quantities. We further study the NP-hard problem of selecting a group \(S\) of \(k\ll n\) vertices with minimum \(H(S)\) , whose objective function is monotonic and supermodular. We finally propose two greedy algorithms approximately solving the problem. The former has an approximation factor \((1-\frac{k}{k-1}\frac{1}{e})\) and \(O(kn^{3})\) running time, while the latter returns a \((1-\frac{k}{k-1}\frac{1}{e}-\epsilon)\) -approximation solution in nearly-linear time of \(m\) , for any parameter \(0{\lt}\epsilon{\lt}1\) . Extensive experiment results validate the performance of our algorithms.

Kemeny's constant for random walks on a graph is defined as the mean hitting time from one node to another selected randomly according to the stationary distribution. It has found numerous applications and attracted considerable research interest. However, exact computation of Kemeny's constant requires matrix inversion, which scales poorly for large networks with millions of nodes. Existing approximation algorithms either leverage properties exclusive to undirected graphs or involve inefficient simulation, leaving room for further optimization. To address these limitations for directed graphs, we propose two novel approximation algorithms for estimating Kemeny's constant on directed graphs with theoretical error guarantees. Extensive numerical experiments on real-world networks validate the superiority of our algorithms over baseline methods in terms of efficiency and accuracy.

For an undirected graph, its Kemeny's constant is defined as the mean hitting time of random walks from one vertex to another chosen randomly according to the stationary distribution. Kemeny's constant exhibits numerous explanations from different perspectives and has found various applications in the field of complex networks. Due to the requirement of computing the inverse of the normalized Laplacian matrix, it is infeasible to get the accurate Kemeny's constant of large networks with millions of vertices. Existing methods either consume excessive memory space that are impractical for large-scale networks, or involve redundant simulation, leaving room for further optimization. In this paper, we propose two scalable Monte Carlo algorithms RefinedMC and ForestMC to approximate Kemeny's constant. RefinedMC makes several refinements based on the simulation of truncated random walks, significantly reducing the amount of required random walks, while ForestMC utilizes the newly discovered paradigm connecting Kemeny's constant with the inverse of corresponding Laplacian submatrix, which is considerably accurate. Extensive numerical experiments on model and realistic networks demonstrate that our approximation algorithms evidently outperform the baseline methods in terms of efficiency and accuracy.