Critical node identification in complex networks via gravity model based on steady-state restart Markov chain

The identification of critical nodes in complex networks constitutes a fundamental challenge in understanding information dissemination and network vulnerability. Although various centrality measures are available, they often consider network structures solely from either local or global perspectives, failing to simultaneously characterize multi-hop propagation effects and distant hierarchical architecture. Gravity models have attracted attention for integrating multi-scale information, yet suffer from limitations such as distance computation relying on shortest paths and gravitational constant determination depending on heuristic rules. Random Walk with Restart (RWR) and its improvements, while capable of capturing global structure, rely on Monte Carlo simulations that result in inherent randomness and variance, high computational overhead, and lack of theoretical guarantees, thereby constraining algorithm stability and scalability. To address these limitations, this paper proposes a deterministic analytical framework grounded in Markov Chain steady-state theory to eliminate the randomness of RWR methods. Distinct from traditional stochastic simulations, we directly compute visit probability distributions by analytically solving steady-state equations, achieving deterministic metrics with zero variance, high efficiency, and theoretical provability. Building upon this framework, we propose the Restart Markov Chain-based Gravity Centrality (RMCG), which adaptively determines influence scope through steady-state probabilities, constructs probability distances reflecting multi-hop reachability, and incorporates a position-aware dynamic gravitational constant to amplify the impact of core nodes. Extensive experiments on multiple real-world and synthetic networks demonstrate that RMCG achieves the highest or near-highest spreading consistency and identification accuracy across most networks and infection intensities, with particularly pronounced superiority during weak spreading regimes. Complexity analysis reveals that RMCG maintains favorable scalability while preserving analytical precision. • Proposes a deterministic gravity model based on restart Markov chains, enabling analytic and variance-free node influence estimation. • Introduces a probability-based multi-path distance that captures path redundancy, community structure, and distance decay. • Incorporates a K-shell-driven dynamic gravitational constant to emphasize hierarchical position and reinforce core-node importance. • Establishes theoretical guarantees through steady-state convergence analysis, providing a rigorous foundation for the model.