Identifying effective multiple spreaders by coloring complex networks

Abstract

How to identify influential nodes in social networks is of theoretical significance, which relates to how to prevent epidemic spreading or cascading failure, how to accelerate information diffusion, and so on. In this Letter, we make an attempt to find \emph{effective multiple spreaders} in complex networks by generalizing the idea of the coloring problem in graph theory to complex networks. In our method, each node in a network is colored by one kind of color and nodes with the same color are sorted into an independent set. Then, for a given centrality index, the nodes with the highest centrality in an independent set are chosen as multiple spreaders. Comparing this approach with the traditional method, in which nodes with the highest centrality from the \emph{entire} network perspective are chosen, we find that our method is more effective in accelerating the spreading process and maximizing the spreading coverage than the traditional method, no matter in network models or in real social networks. Meanwhile, the low computational complexity of the coloring algorithm guarantees the potential applications of our method.

6 pages, 6 figures

References in corpus (15)

• Emergence of scaling in random networks
• The structure and function of complex networks
• Epidemic processes in complex networks
• Identification of influential spreaders in complex networks
• Specificity and stability in topology of protein networks
• Epidemic dynamics and endemic states in complex networks
• Self-similar community structure in organisations
• Subgraph Centrality in Complex Networks
• Ranking spreaders by decomposing complex networks
• Searching for superspreaders of information in real-world social media
• Absence of influential spreaders in rumor dynamics
• Non mean-field behavior of the contact process on scale-free networks
• Locating privileged spreaders on an Online Social Network
• Variability of Contact Process in Complex Networks
• Core-like groups result in invalidation of identifying super-spreader by k-shell decomposition

Cited by in corpus (3)

• Vital nodes identification in complex networks
• Identifying influential spreaders in complex networks based on gravity formula
• Maximizing spreading influence via measuring influence overlap for social networks