Locating the source that undergoes a diffusion-like process is a fundamental and challenging problem in complex network, which can help inhibit the outbreak of epidemics among humans, suppress the spread of rumors on the Internet, prevent cascading failures of power grids, etc. However, our ability to accurately locate the diffusion source is strictly limited by incomplete information of nodes and inevitable randomness of diffusion process. In this paper, we propose an efficient optimization approach via maximum likelihood estimation to locate the diffusion source in complex networks with limited observations. By modeling the informed times of the observers, we derive an optimal source localization solution for arbitrary trees and then extend it to general graphs via proper approximations. The numerical analyses on synthetic networks and real networks all indicate that our method is superior to several benchmark methods in terms of the average localization accuracy, high-precision localization and approximate area localization. In addition, low computational cost enables our method to be widely applied for the source localization problem in large-scale networks. We believe that our work can provide valuable insights on the interplay between information diffusion and source localization in complex networks.

Epidemic source localization is one of the most meaningful areas of research in complex networks, which helps solve the problem of infectious disease spread. Limited by incomplete information of nodes and inevitable randomness of the spread process, locating the epidemic source becomes a little difficult. In this paper, we propose an efficient algorithm via Bayesian Estimation to locate the epidemic source and find the initial time in complex networks with sparse observers. By modeling the infected time of observers, we put forward a valid epidemic source localization method for tree network and further extend it to the general network via maximum spanning tree. The numerical analyses in synthetic networks and empirical networks show that our algorithm has a higher source localization accuracy than other comparison algorithms. In particular, when the randomness of the spread path enhances, our algorithm has a better performance. We believe that our method can provide an effective reference for epidemic spread and source localization in complex networks.

How to effectively identify a set of influential spreaders in complex networks is of great theoretical and practical value, which can help to inhibit the rapid spread of epidemics, promote the sales of products by word-of-mouth advertising, and so on. A naive strategy is to select the top ranked nodes as identified by some centrality indices, and other strategies are mainly based on greedy methods and heuristic methods. However, most of those approaches did not concern the connections between nodes. Usually, the distances between the selected spreaders are very close, leading to a serious overlapping of their influence. As a consequence, the global influence of the spreaders in networks will be greatly reduced, which largely restricts the performance of those methods. In this paper, a simple and efficient method is proposed to identify a set of discrete yet influential spreaders. By analyzing the spreading paths in the network, we present the concept of effective spreading paths and measure the influence of nodes via expectation calculation. The numerical analysis in undirected and directed networks all show that our proposed method outperforms many other centrality-based and heuristic benchmarks, especially in large-scale networks. Besides, experimental results on different spreading models and parameters demonstrates the stability and wide applicability of our method.