Open AccessColoring the complex networks and its application for immunization strategy
Author(s) -
Bin Huang,
Xiangyu Zhao,
Kai Qi,
Ming Tang,
Younghae Do
Publication year - 2013
Publication title -
wuli xuebao
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.199
H-Index - 47
ISSN - 1000-3290
DOI - 10.7498/aps.62.218902
Subject(s) - complex network , computer science , clique , immunization , set (abstract data type) , degree (music) , clustering coefficient , value (mathematics) , order (exchange) , cluster analysis , mathematical optimization , mathematics , combinatorics , artificial intelligence , machine learning , antigen , physics , finance , biology , world wide web , acoustics , economics , genetics , programming language
Structural analysis of complex networks has gained more and more concerns, but not enough attention has been paid to the coloring problem in complex networks. In order to understand the relationship between network structure and coloring problem, we investigate the effects of WS, BA networks and different macro-scale parameters on the K-proper coloring. We find that the maximum clique number can generally reflect the trend of K value change, the average degree and the degree correlation have a greater impact on the K value than the heterogeneity and the clustering coefficient. These results are verified on some real-world networks. After coloring the complex networks properly, the independent sets of networks can be obtained. According to the characteristic that any two vertices are not connected in an independent set, we propose a random immunization strategy based on the independent set. Compared with the random immunization, the proposed strategy can make the network more vulnerable, and thus effectively mitigate epidemic spreading. This immunization strategy is simple and practical, which helps to design more efficient immunization strategy.