Issue |
EPL
Volume 108, Number 6, December 2014
|
|
---|---|---|
Article Number | 68005 | |
Number of page(s) | 6 | |
Section | Interdisciplinary Physics and Related Areas of Science and Technology | |
DOI | https://doi.org/10.1209/0295-5075/108/68005 | |
Published online | 09 January 2015 |
Identifying effective multiple spreaders by coloring complex networks
1 Web Sciences Center, University of Electronic Science and Technology of China - Chengdu 611731, PRC
2 School of Computer Science and Technology, University of Science and Technology of China - Hefei 230027, PRC
3 School of Applied Mathematics, Chengdu University of Information Technology - Chengdu 610225, PRC
4 School of Mathematical Science, Anhui University - Hefei 230601, PRC
5 Department of Communication Engineering, North University of China - Taiyuan, Shan'xi 030051, PRC
(a) tangminghuang521@hotmail.com
(b) haifengzhang1978@gmail.com
Received: 7 October 2014
Accepted: 5 December 2014
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 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 descriptor, 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 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. Moreover, the low computational complexity of the coloring algorithm guarantees the potential applications of our method.
PACS: 89.75.Hc – Networks and genealogical trees / 89.75.Fb – Structures and organization in complex systems / 87.23.Ge – Dynamics of social systems
© EPLA, 2014
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.