Coloring the complex networks and its application for immunization strategy

Huang Bin; Zhao Xiang-Yu; Qi Kai; Tang Ming; Do Younghae

doi:10.7498/aps.62.218902

Abstract

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.

Keywords:

Authors and contacts

1.
School of Mathematics, Chengdu University of Information Technology, Chengdu 610225, China;
2.
Web Science Center, University of Electronic Science and Technology of China, Chengdu 610054, China;
3.
Department of Mathematics, Kyungpook National University, Daegu 702-701, South Korea
Funds: Project supported by the National Natural Science Foundation of China (Grant No. 11105025), the China Postdoctoral Science Special Foundation (Grant No. 2012T50711), the China Postdoctoral Science Foundation (Grant No. 20110491705), the Specialized Research Fund for the Doctoral Program of Higher Education of China (Grant No. 20110185120021), the Fundamental Research Funds for the Central Universities of China (Grant No. ZYGX2011J056), and Y. Do was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (NRF-2013R1A1A2010067).

References

[1]	Barabasi A L 2002 Linked:The New science of networks (Cambridge MA: Perseus) pp1–8
[2]	He D R, Liu Z H, Wang B H 2008 Complex Systems and Complex Networks (Beijing: Higher Education Press) pp1–40 (in Chinese) [何大韧, 刘宗华, 汪秉宏 2008 复杂系统与复杂网络 (北京: 高等教育出版社) 第1–40页]
[3]	Wang X F, Chen G R 2006 Complex Networks Theory and its Applications (Beijing: Tsinghua University Press) pp9–14 (in Chinese) [汪小帆, 李翔, 陈关荣 2006 复杂网络理论及其应用 (北京: 清华大学出版社) 第9–14页]
[4]	Cui A X, Zhang Z k, Tang M, Fu Y, Hui P 2012 PLoS ONE 7 50702
[5]	Dorogovtsev S N, Goltsev A V, Mendes J F F 2008 Reviews of Modern Physics 80 pp1275–1335
[6]	Zhang X D, Li Z L 2005 Graph Theory and Its Applications (Beijing: Higher Education Press) pp147–185 (in Chinese) [张先迪, 李正良 2005 图论及其应用 (北京: 高等教育出版社) 第147–185页]
[7]	Appel K, Haken W 1977 Ill. J. Math 21 429
[8]	Appel K,Haken W, Koch J 1977Ill. J. Math 21 491
[9]	Marx D 2004 Periodica Polytechnica Ser. El. Eng. 48 11
[10]	Erdos P 1959 Canad. J. Math 11 34
[11]	Luczak T 1991 Combinatorica 11 45
[12]	Mulet R, Pagnani A, Weigt M, Zecchina R 2002 Phys. Rev. Lett. 89 268701
[13]	Bollobás B 2001 Random graphs 2nd Edn. (Cambridge: Cambridge University Press) 298
[14]	Achlioptas D, Naor A, Peres Y 2005 Nature 435 759
[15]	Bollobás B, Thomason A G 1985 Annals of Discr. Math 28 47
[16]	Watts D J, Strogatz S H 1998 Nature 393 440
[17]	Barabasi A L, Albert R 1999 Science 286 509
[18]	Walsh T 1999 In Proceedings of the 16th International Joint Conference on Artificial Intelligence San Francisco pp1172
[19]	Song C M, Havlin S, Makse H A 2005 Nature 433 392
[20]	Pastor-Satorras R, Vespignani A 2002 Phys. Rev. E 65 036104
[21]	Wang X F, Chen G 2002 Physica A 310 521
[22]	Bomze I M, Budinich M, Pardalos P M, Pelillo M 1999 The maximum clique problem (Netherlands: kluwer academic publishers) pp1–74
[23]	Wang S H 2009 Graph Theory 2nd Eds. (Beijing: SciencePress) pp204–221 (in Chinese) [王树禾 2009 图论第二版 (北京: 科学出版社) 第204–221页]
[24]	Stephen Cook 1971 In Proceedings of the Third Annual ACM Symposium on Theory of Computing pp 151–158
[25]	Brelaz D 1979 Communications of ACM 22 251
[26]	Klotz W 2002 Mathematik-Bericht 5 1
[27]	Welsh D J A, Powell M B 1967 The Comptr. J. 10 85
[28]	Wang Q S, Fan T S 2010 Computer Engineering 36 39 (in Chinese) [王青松, 范铁生 2010 计算机工程 36 39]
[29]	Boccalettia S, Latorab V, Morenod Y, Chavezf M, Hwanga D U 2006 Physics Reports 424 175
[30]	Bollobás B 1980 European Journal of Combinatorics 1 311
[31]	Newman M E J 2009 Phys. Rev. Lett. 103 1
[32]	Newman M E J 2002 Phys. Rev. Lett. 89 20870
[33]	Chen Y Z, Fu C H, Chang H, Li N, He D R 2008 Chin. Phys. B 17 3580
[34]	Holme P, Kim B J 2002 Phys. Rev. E 65 026107
[35]	Tang M, Liu L, Liu Z H 2009 Phys. Rev. E 79 016108
[36]	Tang M, Liu Z H, Li B W 2009 Europhys. Lett. 87 18005
[37]	Ruan Z Y, Tang M, Liu Z H 2012 Phys. Rev. E 86 036117
[38]	Yang H, Tang M, Zhang H F 2012 New J. Phys. 14 123017
[39]	Wang L, Wang Z, Zhang Y, Li X 2013 Sci. Rep. 3 1468
[40]	Zhou J, Xiao G X, Cheong S A, Fu X, Wong L, Ma S, Cheng T H 2012 Phys. Rev. E 85 036107
[41]	Gong K, Tang M, Shang M S, Zhou T 2012 Acta Phys. Sin. 61 098901 (in Chinese) [龚凯, 唐明, 尚明生, 周涛 2010 物理学报 61 098901]
[42]	Li R Q, Tang M, Hui P M 2013 Acta Phys. Sin. 62 168903 (in Chinese) [李睿琪, 唐明, 许伯铭 2013 物理学报 62 168903]
[43]	Wang L, Yan J R, Zhang J G, Liu Z R 2007 Chin. Phys. 16 2498
[44]	Cohen R, Havlin S, Ben-Avraham D 2003 Phys. Rev. Lett. 91 247901
[45]	Zhang H F, Li K Z, Fu X C, Wang B H 2009 Chinese Phys. Lett. 26 068901
[46]	Diekmann O, Heesterbeek J 2000 Mathematical epidemiology of infectious diseases: model building,analysis and interpretation (New York: John Wiley & Sons) pp201–207
[47]	Pei W D, Chen Z Q, Yuan Z Z 2008 Chin. Phys. B 17 373

Cited By

[1]	Barabasi A L 2002 Linked:The New science of networks (Cambridge MA: Perseus) pp1–8
[2]	He D R, Liu Z H, Wang B H 2008 Complex Systems and Complex Networks (Beijing: Higher Education Press) pp1–40 (in Chinese) [何大韧, 刘宗华, 汪秉宏 2008 复杂系统与复杂网络 (北京: 高等教育出版社) 第1–40页]
[3]	Wang X F, Chen G R 2006 Complex Networks Theory and its Applications (Beijing: Tsinghua University Press) pp9–14 (in Chinese) [汪小帆, 李翔, 陈关荣 2006 复杂网络理论及其应用 (北京: 清华大学出版社) 第9–14页]
[4]	Cui A X, Zhang Z k, Tang M, Fu Y, Hui P 2012 PLoS ONE 7 50702
[5]	Dorogovtsev S N, Goltsev A V, Mendes J F F 2008 Reviews of Modern Physics 80 pp1275–1335
[6]	Zhang X D, Li Z L 2005 Graph Theory and Its Applications (Beijing: Higher Education Press) pp147–185 (in Chinese) [张先迪, 李正良 2005 图论及其应用 (北京: 高等教育出版社) 第147–185页]
[7]	Appel K, Haken W 1977 Ill. J. Math 21 429
[8]	Appel K,Haken W, Koch J 1977Ill. J. Math 21 491
[9]	Marx D 2004 Periodica Polytechnica Ser. El. Eng. 48 11
[10]	Erdos P 1959 Canad. J. Math 11 34
[11]	Luczak T 1991 Combinatorica 11 45
[12]	Mulet R, Pagnani A, Weigt M, Zecchina R 2002 Phys. Rev. Lett. 89 268701
[13]	Bollobás B 2001 Random graphs 2nd Edn. (Cambridge: Cambridge University Press) 298
[14]	Achlioptas D, Naor A, Peres Y 2005 Nature 435 759
[15]	Bollobás B, Thomason A G 1985 Annals of Discr. Math 28 47
[16]	Watts D J, Strogatz S H 1998 Nature 393 440
[17]	Barabasi A L, Albert R 1999 Science 286 509
[18]	Walsh T 1999 In Proceedings of the 16th International Joint Conference on Artificial Intelligence San Francisco pp1172
[19]	Song C M, Havlin S, Makse H A 2005 Nature 433 392
[20]	Pastor-Satorras R, Vespignani A 2002 Phys. Rev. E 65 036104
[21]	Wang X F, Chen G 2002 Physica A 310 521
[22]	Bomze I M, Budinich M, Pardalos P M, Pelillo M 1999 The maximum clique problem (Netherlands: kluwer academic publishers) pp1–74
[23]	Wang S H 2009 Graph Theory 2nd Eds. (Beijing: SciencePress) pp204–221 (in Chinese) [王树禾 2009 图论第二版 (北京: 科学出版社) 第204–221页]
[24]	Stephen Cook 1971 In Proceedings of the Third Annual ACM Symposium on Theory of Computing pp 151–158
[25]	Brelaz D 1979 Communications of ACM 22 251
[26]	Klotz W 2002 Mathematik-Bericht 5 1
[27]	Welsh D J A, Powell M B 1967 The Comptr. J. 10 85
[28]	Wang Q S, Fan T S 2010 Computer Engineering 36 39 (in Chinese) [王青松, 范铁生 2010 计算机工程 36 39]
[29]	Boccalettia S, Latorab V, Morenod Y, Chavezf M, Hwanga D U 2006 Physics Reports 424 175
[30]	Bollobás B 1980 European Journal of Combinatorics 1 311
[31]	Newman M E J 2009 Phys. Rev. Lett. 103 1
[32]	Newman M E J 2002 Phys. Rev. Lett. 89 20870
[33]	Chen Y Z, Fu C H, Chang H, Li N, He D R 2008 Chin. Phys. B 17 3580
[34]	Holme P, Kim B J 2002 Phys. Rev. E 65 026107
[35]	Tang M, Liu L, Liu Z H 2009 Phys. Rev. E 79 016108
[36]	Tang M, Liu Z H, Li B W 2009 Europhys. Lett. 87 18005
[37]	Ruan Z Y, Tang M, Liu Z H 2012 Phys. Rev. E 86 036117
[38]	Yang H, Tang M, Zhang H F 2012 New J. Phys. 14 123017
[39]	Wang L, Wang Z, Zhang Y, Li X 2013 Sci. Rep. 3 1468
[40]	Zhou J, Xiao G X, Cheong S A, Fu X, Wong L, Ma S, Cheng T H 2012 Phys. Rev. E 85 036107
[41]	Gong K, Tang M, Shang M S, Zhou T 2012 Acta Phys. Sin. 61 098901 (in Chinese) [龚凯, 唐明, 尚明生, 周涛 2010 物理学报 61 098901]
[42]	Li R Q, Tang M, Hui P M 2013 Acta Phys. Sin. 62 168903 (in Chinese) [李睿琪, 唐明, 许伯铭 2013 物理学报 62 168903]
[43]	Wang L, Yan J R, Zhang J G, Liu Z R 2007 Chin. Phys. 16 2498
[44]	Cohen R, Havlin S, Ben-Avraham D 2003 Phys. Rev. Lett. 91 247901
[45]	Zhang H F, Li K Z, Fu X C, Wang B H 2009 Chinese Phys. Lett. 26 068901
[46]	Diekmann O, Heesterbeek J 2000 Mathematical epidemiology of infectious diseases: model building,analysis and interpretation (New York: John Wiley & Sons) pp201–207
[47]	Pei W D, Chen Z Q, Yuan Z Z 2008 Chin. Phys. B 17 373

[1]	Zhao Guo-Tao, Wang Li-Fu, Guan Bo-Fei. A class of edge set affecting network controllability. Acta Physica Sinica, 2021, 70(14): 148902. doi: 10.7498/aps.70.20201831
[2]	Jiang Wen-Jun, Liu Run-Ran, Fan Tian-Long, Liu Shuang-Shuang, Lü Lin-Yuan. Overview of precaution and recovery strategies for cascading failures in multilayer networks. Acta Physica Sinica, 2020, 69(8): 088904. doi: 10.7498/aps.69.20192000
[3]	Wan Yi-Ping, Zhang Dong-Ge, Ren Qing-Hui. Propagation and inhibition of online rumor with considering rumor elimination process. Acta Physica Sinica, 2015, 64(24): 240501. doi: 10.7498/aps.64.240501
[4]	Liu Wei-Yan, Liu Bin. Congestion control in complex network based on local routing strategy. Acta Physica Sinica, 2014, 63(24): 248901. doi: 10.7498/aps.63.248901
[5]	Li Yu-Shan, Lü Ling, Liu Ye, Liu Shuo, Yan Bing-Bing, Chang Huan, Zhou Jia-Nan. Spatiotemporal chaos synchronization of complex networks by Backstepping design. Acta Physica Sinica, 2013, 62(2): 020513. doi: 10.7498/aps.62.020513
[6]	Cai Jun, Yu Shun-Zheng. An efficient management strategy for enhancing traffic capacity in scale-free networks. Acta Physica Sinica, 2013, 62(5): 058901. doi: 10.7498/aps.62.058901
[7]	Zhou Xuan, Zhang Feng-Ming, Li Ke-Wu, Hui Xiao-Bin, Wu Hu-Sheng. Finding vital node by node importance evaluation matrix in complex networks. Acta Physica Sinica, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
[8]	Liu Gang, Li Yong-Shu. Routing strategy for complex networks based on gravitation field theory. Acta Physica Sinica, 2012, 61(24): 248901. doi: 10.7498/aps.61.248901
[9]	Wang Ya-Qi, Yang Xiao-Yuan. Study on a model of topology evolution of wireless sensor networks among cluster heads and its immunization. Acta Physica Sinica, 2012, 61(9): 090202. doi: 10.7498/aps.61.090202
[10]	Cui Ai-Xiang, Fu Yan, Shang Ming-Sheng, Chen Duan-Bing, Zhou Tao. Emergence of local structures in complex network:common neighborhood drives the network evolution. Acta Physica Sinica, 2011, 60(3): 038901. doi: 10.7498/aps.60.038901
[11]	Jiang Zhi-Hong, Wang Hui, Gao Chao. A evolving network model generated by random walk and policy attachment. Acta Physica Sinica, 2011, 60(5): 058903. doi: 10.7498/aps.60.058903
[12]	Wang Ya-Qi, Jiang Guo-Ping. Epidemic immunization on scale-free networks with traffic flow. Acta Physica Sinica, 2011, 60(6): 060202. doi: 10.7498/aps.60.060202
[13]	Wang Ya-Qi, Jiang Guo-Ping. Virus spreading on complex networks with imperfect immunization. Acta Physica Sinica, 2010, 59(10): 6734-6743. doi: 10.7498/aps.59.6734
[14]	Wang Dan, Yu Hao, Jing Yuan-Wei, Jiang Nan, Zhang Si-Ying. Study on the congestion in complex network based on traffic awareness algorithm. Acta Physica Sinica, 2009, 58(10): 6802-6808. doi: 10.7498/aps.58.6802
[15]	Lü Ling, Zhang Chao. Chaos synchronization of a complex network with different nodes. Acta Physica Sinica, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
[16]	Chen Hua-Liang, Liu Zhong-Xin, Chen Zeng-Qiang, Yuan Zhu-Zhi. Research on one weighted routing strategy for complex networks. Acta Physica Sinica, 2009, 58(9): 6068-6073. doi: 10.7498/aps.58.6068
[17]	Li Tao, Pei Wen-Jiang, Wang Shao-Ping. Optimal traffic routing strategy on scale-free complex networks. Acta Physica Sinica, 2009, 58(9): 5903-5910. doi: 10.7498/aps.58.5903
[18]	Xu Dan, Li Xiang, Wang Xiao-Fan. An investigation on local area control of virus spreading in complex networks. Acta Physica Sinica, 2007, 56(3): 1313-1317. doi: 10.7498/aps.56.1313
[19]	Lin Hai, Wu Chen-Xu. Evolution of strategies based on genetic algorithm in the iterated prisoner’s dilemma on complex networks. Acta Physica Sinica, 2007, 56(8): 4313-4318. doi: 10.7498/aps.56.4313
[20]	Li Ji, Wang Bing-Hong, Jiang Pin-Qun, Zhou Tao, Wang Wen-Xu. Growing complex network model with acceleratingly increasing number of nodes. Acta Physica Sinica, 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051

Catalog

Vol. 62, Issue 21 - 2013-11-05

Metrics

Abstract views: 6172
PDF Downloads: 761
Cited By: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

Search

Article

留言板