CSS: A new combined spreading score measurement for identifying multiple influential spreaders in complex networks

Identifying multiple influential spreaders is a significant procedure to understand, control or accelerate the dynamics of information diffusion process in complex networks effectively. For a given network G and an integer k, we need to find a set of k vertices as “seeds†which carry the information originally, and then through a certain diffusion model, the information can be spread as widely as possible. Note that these seeds cannot be too close to each other, otherwise information is easy to be congested. In this paper, we make an attempt to identify multiple spreaders by considering the “marginal benefit†CSS(v,S) of a vertex v when it is added to an existing seed set S. Here CSS(v,S) is defined as a function of v’s influential ability and the common influence range between vertex v and S. In particular, we use the degree to measure the vertex’s influential ability and use the number of common neighbors between vertex v and S to measure their common influence range. In order to verify this new algorithm’s validity, we apply it on several social networks and the new method performs better than others. This new method is simple to implement and has lower time complexity, thus is expected to have promising applications in the future.