Identifying Influential Spreaders by Graph Sampling

The complex nature of real world networks is a central subject in several disciplines, from Physics to computer science. The complex network dynamics of peers communication and information exchange are specified to a large degree by the most efficient spreaders - the entities that play a central role in various ways such as the viruses propagation, the diffusion of information, the viral marketing and network vulnerability to external attacks. In this paper, we deal with the problem of identifying the influential spreaders of a complex network when either the network is very large or else we have limited computational capabilities to compute global centrality measures. Our approach is based on graph sampling and specifically on Rank Degree, a newly published graph exploration sampling method. We conduct extensive experiments in five real world networks using four centrality metrics for the nodes spreading efficiency. We present strong evidence that our method is highly effective. By sampling 30% of the network and using at least two out of four centrality measures, we can identify more than 80% of the influential spreaders, while at the same time, preserving the original ranking to a large extent.