Fast Algorithms for Group Markov Centrality Optimization

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.