The random walk-based gravity model to identify influential nodes in complex networks

The identification of influential nodes in complex networks has been a topic of immense interest. In most cases, the local approach represented by degree centrality performs well but has limitations when dealing with the bridge nodes. In order to solve the problem of being trapped in the locality, researchers have proposed many useful methods. The gravity model is an emerging research direction among them. However, such models have to exhaust the shortest distance between all nodes, which renders them impractical and dif-ficult to run over large graphs. In order to address this issue, we propose a random walk -based gravity model to identify influential spreaders. Our proposed model decreases the time complexity of calculating the shortest distance-a critical step in the conventional gravity models, from O eth jVj2 + to O eth jVj ? c? l r eth l?r + + , and reduces space complexity of O eth jVj2 + to O eth 2jVj + , where < K > 2 ? jVj and c ? l r eth l?r + ? jVj. Some random walk proper-ties are also investigated to support our model. In order to demonstrate the feasibility of the proposed gravity centrality, we have verified its spreading ability and convergence speed under different random walk strategies. Experimental results indicate that our method performs far better than most gravity models.(c) 2022 Elsevier Inc. All rights reserved.

Automated summary

The article introduces the methods for identifying influential nodes in complex networks and the existing problems. It proposes a random walk-based gravity model to solve this problem, and through experiments, it demonstrates the superior performance of the model.