复杂网络的顶点着色及其在疾病免疫中的应用

黄斌; 赵翔宇; 齐凯; 唐明; 都永海

doi:10.7498/aps.62.218902

摘要

在复杂网络研究中, 对于网络结构特征的分析已经引起了人们的极大关注, 而其中的网络着色问题却没有得到足够的重视. 为了理解网络结构与着色之间的关系, 本文研究了WS, BA网络以及不同宏观结构参量对于正常K色数的影响, 发现最大团数可以大致反映正常K色数的变化趋势, 而网络的平均度和匹配系数比异质性和聚类系数对于色数的影响更大. 对于一些实际网络的正常着色验证了本文的分析结果. 对复杂网络的顶点进行着色后, 根据独立集内任意两个顶点均不相邻的特点, 我们提出了基于独立集的免疫策略. 与全网随机免疫相比, 基于独立集的免疫策略可令网络更为脆弱, 从而有效抑制疾病的传播. 基于网络着色的独立集提供了一种崭新的免疫思路, 作为一个简单而适用的平台,有助于设计更为有效的免疫策略.

关键词:

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:

作者及机构信息

1.
成都信息工程学院数学学院, 成都 610225;

2.
电子科技大学互联网科学中心, 成都 610054;

3.
韩国庆北国立大学数学系, 韩国大邱 702-701

基金项目: 国家自然科学基金(批准号: 11105025)、博士后科学基金特别资助(批准号: 2012T50711)、博士后科学基金(批准号: 20110491705)、博士点新教师基金 (批准号: 20110185120021)和中央高校基本科研业务费项目 (批准号: ZYGX2011J056)资助的课题; 都永海感谢韩国教育、科学与技术部支持的国家研究基金会基础科学研究项目(批准号: NRF-2013R1A1A2010067)的资助.

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).

参考文献

[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]	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]	赵国涛, 王立夫, 关博飞. 一类影响网络能控性的边集研究. 物理学报, 2021, 70(14): 148902. doi: 10.7498/aps.70.20201831
[2]	蒋文君, 刘润然, 范天龙, 刘霜霜, 吕琳媛. 多层网络级联失效的预防和恢复策略概述. 物理学报, 2020, 69(8): 088904. doi: 10.7498/aps.69.20192000
[3]	万贻平, 张东戈, 任清辉. 考虑谣言清除过程的网络谣言传播与抑制. 物理学报, 2015, 64(24): 240501. doi: 10.7498/aps.64.240501
[4]	刘伟彦, 刘斌. 基于局部路由策略的复杂网络拥塞控制. 物理学报, 2014, 63(24): 248901. doi: 10.7498/aps.63.248901
[5]	李雨珊, 吕翎, 刘烨, 刘硕, 闫兵兵, 常欢, 周佳楠. 复杂网络时空混沌同步的Backstepping设计. 物理学报, 2013, 62(2): 020513. doi: 10.7498/aps.62.020513
[6]	蔡君, 余顺争. 一种有效提高无标度网络负载容量的管理策略. 物理学报, 2013, 62(5): 058901. doi: 10.7498/aps.62.058901
[7]	周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 物理学报, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
[8]	刘刚, 李永树. 基于引力场理论的复杂网络路由选择策略研究. 物理学报, 2012, 61(24): 248901. doi: 10.7498/aps.61.248901
[9]	王亚奇, 杨晓元. 一种无线传感器网络簇间拓扑演化模型及其免疫研究. 物理学报, 2012, 61(9): 090202. doi: 10.7498/aps.61.090202
[10]	崔爱香, 傅彦, 尚明生, 陈端兵, 周涛. 复杂网络局部结构的涌现:共同邻居驱动网络演化. 物理学报, 2011, 60(3): 038901. doi: 10.7498/aps.60.038901
[11]	姜志宏, 王晖, 高超. 一种基于随机行走和策略连接的网络演化模型. 物理学报, 2011, 60(5): 058903. doi: 10.7498/aps.60.058903
[12]	王亚奇, 蒋国平. 考虑网络流量的无标度网络病毒免疫策略研究. 物理学报, 2011, 60(6): 060202. doi: 10.7498/aps.60.060202
[13]	王亚奇, 蒋国平. 复杂网络中考虑不完全免疫的病毒传播研究. 物理学报, 2010, 59(10): 6734-6743. doi: 10.7498/aps.59.6734
[14]	吕翎, 张超. 一类节点结构互异的复杂网络的混沌同步. 物理学报, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
[15]	王丹, 于灏, 井元伟, 姜囡, 张嗣瀛. 基于感知流量算法的复杂网络拥塞问题研究. 物理学报, 2009, 58(10): 6802-6808. doi: 10.7498/aps.58.6802
[16]	李涛, 裴文江, 王少平. 无标度复杂网络负载传输优化策略. 物理学报, 2009, 58(9): 5903-5910. doi: 10.7498/aps.58.5903
[17]	陈华良, 刘忠信, 陈增强, 袁著祉. 复杂网络的一种加权路由策略研究. 物理学报, 2009, 58(9): 6068-6073. doi: 10.7498/aps.58.6068
[18]	许丹, 李翔, 汪小帆. 复杂网络病毒传播的局域控制研究. 物理学报, 2007, 56(3): 1313-1317. doi: 10.7498/aps.56.1313
[19]	林海, 吴晨旭. 基于遗传算法的重复囚徒困境博弈策略在复杂网络中的演化. 物理学报, 2007, 56(8): 4313-4318. doi: 10.7498/aps.56.4313
[20]	李季, 汪秉宏, 蒋品群, 周涛, 王文旭. 节点数加速增长的复杂网络生长模型. 物理学报, 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051

计量

文章访问数: 6170
PDF下载量: 761
被引次数: 0

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

搜索

留言板