{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:44:24Z","timestamp":1760233464284,"version":"build-2065373602"},"reference-count":27,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2021,1,20]],"date-time":"2021-01-20T00:00:00Z","timestamp":1611100800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Zhejiang Provincial Natural Science Foundation of China","award":["LQY19G030001","LY20F0300"],"award-info":[{"award-number":["LQY19G030001","LY20F0300"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>The spread of a computer virus among the Internet of Things (IoT) devices can be modeled as an Epidemic Containment (EC) game, where each owner decides the strategy, e.g., installing anti-virus software, to maximize his utility against the susceptible-infected-susceptible (SIS) model of the epidemics on graphs. The EC game\u2019s canonical solution concepts are the Minimum\/Maximum Nash Equilibria (MinNE\/MaxNE). However, computing the exact MinNE\/MaxNE is NP-hard, and only several heuristic algorithms are proposed to approximate the MinNE\/MaxNE. To calculate the exact MinNE\/MaxNE, we provide a thorough analysis of some special graphs and propose scalable and exact algorithms for general graphs. Especially, our contributions are four-fold. First, we analytically give the MinNE\/MaxNE for EC on special graphs based on spectral radius. Second, we provide an integer linear programming formulation (ILP) to determine MinNE\/MaxNE for the general graphs with the small epidemic threshold. Third, we propose a branch-and-bound (BnB) framework to compute the exact MinNE\/MaxNE in the general graphs with several heuristic methods to branch the variables. Fourth, we adopt NetShiled (NetS) method to approximate the MinNE to improve the scalability. Extensive experiments demonstrate that our BnB algorithm can outperform the naive enumeration method in scalability, and the NetS can improve the scalability significantly and outperform the previous heuristic method in solution quality.<\/jats:p>","DOI":"10.3390\/sym13020156","type":"journal-article","created":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T02:36:05Z","timestamp":1611196565000},"page":"156","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Secure the IoT Networks as Epidemic Containment Game"],"prefix":"10.3390","volume":"13","author":[{"given":"Juntao","family":"Zhu","sequence":"first","affiliation":[{"name":"School of Cyberspace, Hangzhou Dianzi University, Hangzhou 310018, China"}]},{"given":"Hong","family":"Ding","sequence":"additional","affiliation":[{"name":"School of Cyberspace, Hangzhou Dianzi University, Hangzhou 310018, China"}]},{"given":"Yuchen","family":"Tao","sequence":"additional","affiliation":[{"name":"School of Cyberspace, Hangzhou Dianzi University, Hangzhou 310018, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3399-5281","authenticated-orcid":false,"given":"Zhen","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Cyberspace, Hangzhou Dianzi University, Hangzhou 310018, China"}]},{"given":"Lanping","family":"Yu","sequence":"additional","affiliation":[{"name":"School of Information Engineering, Hangzhou Dianzi University, Hangzhou 310018, China"}]}],"member":"1968","published-online":{"date-parts":[[2021,1,20]]},"reference":[{"key":"ref_1","unstructured":"Kumar, M.S., Ben-Othman, J., and Srinivasagan, K.G. (2018, January 25\u201328). An Investigation on Wannacry Ransomware and its Detection. Proceedings of the IEEE ISCC 2018, Natal, Brazil."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Heal, G., and Kunreuther, H. (2004). Interdependent Security: A General Model, National Bureau of Economic Research. Technical Report.","DOI":"10.3386\/w10706"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Omic, J., Orda, A., and Van Mieghem, P. (2009, January 19\u201325). Protecting against network infections: A game theoretic perspective. Proceedings of the IEEE INFOCOM 2009, Rio de Janeiro, Brazil.","DOI":"10.1109\/INFCOM.2009.5062065"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Lelarge, M., and Bolot, J. (2008, January 22). A local mean field analysis of security investments in networks. Proceedings of the 3rd International Workshop on Economics of Networked Systems, Seattle, WA, USA.","DOI":"10.1145\/1403027.1403034"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1077","DOI":"10.1016\/j.jcss.2006.02.003","article-title":"Inoculation strategies for victims of viruses and the sum-of-squares partition problem","volume":"72","author":"Aspnes","year":"2006","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_6","unstructured":"Ganesh, A., Massouli\u00e9, L., and Towsley, D. (2005, January 13\u201317). The effect of network topology on the spread of epidemics. Proceedings of the IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies, Miami, FL, USA."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Saha, S., Adiga, A., and Vullikanti, A.K.S. (2014, January 27\u201331). Equilibria in epidemic containment games. Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, Quebec City, QC, Canada.","DOI":"10.1609\/aaai.v28i1.8819"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Xu, J.H., Wang, Z., Cui, G.H., Ren, Y.Z., Ding, H., and Choo, K.K.R. (August, January 30). An Extended Exploration to the Epidemic Containment Game. Proceedings of the 2018 27th International Conference on Computer Communication and Networks (ICCCN), Hangzhou, China.","DOI":"10.1109\/ICCCN.2018.8487370"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Grossklags, J., Christin, N., and Chuang, J. (2008, January 1). Secure or insure: A game-theoretic analysis of information security games. Proceedings of the 17th International Conference on World Wide Web, Beijing, China.","DOI":"10.1145\/1367497.1367526"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Kumar, V.A., Rajaraman, R., Sun, Z., and Sundaram, R. (2010, January 21\u201325). Existence Theorems and Approximation Algorithms for Generalized Network Security Games. Proceedings of the 2010 IEEE 30th International Conference on Distributed Computing Systems, Genova, Italy.","DOI":"10.1109\/ICDCS.2010.70"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Jiang, L., Anantharam, V., and Walrand, J. (2008, January 22). Efficiency of selfish investments in network security. Proceedings of the 3rd International Workshop on Economics of Networked Systems, Seattle, WA, USA.","DOI":"10.1145\/1403027.1403035"},{"key":"ref_12","unstructured":"Kearns, M., and Ortiz, L.E. (2004, January 13\u201318). Algorithms for interdependent security games. Proceedings of the Advances in Neural Information Processing Systems, Vancouver, BC, Canada."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1177\/0022002704272833","article-title":"IDS models of airline security","volume":"49","author":"Heal","year":"2005","journal-title":"J. Confl. Resolut."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1023\/A:1024119208153","article-title":"Interdependent security","volume":"26","author":"Kunreuther","year":"2003","journal-title":"J. Risk Uncertain."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Briesemeister, L., Lincoln, P., and Porras, P. (2003, January 27). Epidemic profiles and defense of scale-free networks. Proceedings of the 2003 ACM workshop on Rapid Malcode, Washington, DC, USA.","DOI":"10.1145\/948187.948200"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1140\/epjb\/e2004-00119-8","article-title":"Immunization and epidemic dynamics in complex networks","volume":"38","author":"Madar","year":"2004","journal-title":"Eur. Phys. J. B"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1109\/TKDE.2015.2465378","article-title":"Node immunization on large graphs: Theory and algorithms","volume":"28","author":"Chen","year":"2015","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_18","unstructured":"Chen, W., Wang, Y., and Yang, S. (July, January 28). Efficient influence maximization in social networks. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"016101","DOI":"10.1103\/PhysRevE.84.016101","article-title":"Decreasing the spectral radius of a graph by link removals","volume":"84","author":"Kuipers","year":"2011","journal-title":"Phys. Rev. E"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Saha, S., Adiga, A., Prakash, B.A., and Vullikanti, A.K.S. (May, January 30). Approximation algorithms for reducing the spectral radius to control epidemic spread. Proceedings of the 2015 SIAM International Conference on Data Mining, Vancouver, BC, Canada.","DOI":"10.1137\/1.9781611974010.64"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1284680.1284681","article-title":"Epidemic thresholds in real networks","volume":"10","author":"Chakrabarti","year":"2008","journal-title":"ACM Trans. Inf. Syst. Secur. (TISSEC)"},{"key":"ref_22","unstructured":"Godsil, C., and Royle, G.F. (2013). Algebraic Graph Theory, Springer Science & Business Media."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Cvetkovic, D., Simic, S., and Rowlinson, P. (2009). An Introduction to the Theory of Graph Spectra, Cambridge University Press.","DOI":"10.1017\/CBO9780511801518"},{"key":"ref_24","first-page":"18","article-title":"On random graphs i","volume":"6","author":"ERDdS","year":"1959","journal-title":"Publ. Math. Debrecen"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/j.socnet.2009.02.002","article-title":"Clustering in weighted networks","volume":"31","author":"Opsahl","year":"2009","journal-title":"Soc. Netw."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Kayes, A., Han, J., Colman, A., and Islam, M.S. (2014). RelBOSS: A relationship-aware access control framework for software services. OTM Confederated International Conferences \u201cOn the Move to Meaningful Internet Systems\u201d, Springer.","DOI":"10.1007\/978-3-662-45563-0_15"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/j.future.2020.02.001","article-title":"Achieving security scalability and flexibility using Fog-Based Context-Aware Access Control","volume":"107","author":"Kayes","year":"2020","journal-title":"Future Gener. Comput. Syst."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/2\/156\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:13:12Z","timestamp":1760159592000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/2\/156"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,20]]},"references-count":27,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,2]]}},"alternative-id":["sym13020156"],"URL":"https:\/\/doi.org\/10.3390\/sym13020156","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2021,1,20]]}}}