Yifan Sun

【Abstract】

How to optimize the spreading process on networks has been a hot issue in complex networks, marketing, epidemiology, finance, etc. In this paper, we investigate a problem of optimizing locally the spreading: identifying a fixed number of nodes as seeds which would maximize the propagation of influence to their direct neighbors. All the nodes except the selected seeds are assumed not to spread their influence to their neighbors. This problem can be mapped onto a spin glass model with a fixed magnetization. We provide a message-passing algorithm based on replica symmetrical mean-field theory in statistical physics, which can find the nearly optimal set of seeds. Extensive numerical results on computer-generated random networks and real-world networks demonstrate that this algorithm has a better performance than several other optimization algorithms.

【Keywords】

statistical and nonlinear physics