Effective Graph Protection Method to Prevent the Spreading of Attacks in Networks
DOI:
https://doi.org/10.35806/ijoced.v1i2.61Keywords:
graph protection, node immunization, graph connectivity, principal eigenvectorAbstract
Networks are fundamental models for representing and analyzing the structures of real-world systems. For instance, in social networks, nodes are used to represent users and edges represent the connection between users. Networks are also termed as graphs in the discrete mathematics language. One essential problem in networks is how to protect a limited number of nodes to prevent the spreading of malicious attacks or dangerous rumor in the networks, which is known as the graph protection problem. In this paper, an effective graph protection method called PowerShield is proposed which pre-emptively protects critical nodes prior to any incoming attacks. It combines connectivity and centrality criteria of the input graph. Connectivity criterion is measured by the principal eigenvector, i.e., the eigenvector corresponding to the largest eigenvalue of the adjacency matrix of the input graph. Centrality criterion is defined by the degree centrality which considers nodes having more neighborhood relations to be more important. Contrary to the existing state-of-the-art method which takes into account only the connectivity criterion, the proposed method combines both criteria and empirically improves the effectiveness of protection result.
References
Borgatti, S. P. (2005). Centrality and network flow. Social Networks, 27(1), 55–71.
Brouwer, A. E., & Haemers, W. H. (2012). Spectra of Graphs. New York, NY: Springer New York.
Chen, C., Tong, H., Prakash, B. A., Tsourakakis, C. E., Eliassi-Rad, T., Faloutsos, C., & Chau, D. H. (2016). Node Immunization on Large Graphs: Theory and Algorithms. IEEE Transactions on Knowledge and Data Engineering, 28(1), 113–126.
Chung, F. R. K. (1997). Spectral Graph Theory. Providence, Rhode Island, USA: American Mathematical Society.
Dangalchev, C. (2006). Residual closeness in networks. Physica A: Statistical Mechanics and Its Applications, 365(2), 556–564.
Gerasimov, E. N., & Repko, V. N. (1978). Multicriterial optimization. Soviet Applied Mechanics, 14(11), 1179–1184.
Kermack, W. O., & McKendrick, A. G. (1927). A Contribution to the Mathematical Theory of Epidemics. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 115(772), 700–721.
Lee, S. H. (Mark), Cotte, J., & Noseworthy, T. J. (2010). The role of network centrality in the flow of consumer influence. Journal of Consumer Psychology, 20(1), 66–77.
Lusseau, D., Schneider, K., Boisseau, O. J., Haase, P., Slooten, E., & Dawson, S. M. (2003). The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations: Can geographic isolation explain this unique trait? Behavioral Ecology and Sociobiology, 54(4), 396–405.
Marler, R. T., & Arora, J. S. (2004). Survey of multi-objective optimization methods for engineering. Structural and Multidisciplinary Optimization, 26(6), 369–395.
Newman, M. (2010). Networks: An Introduction. New York, NY, USA: Oxford University Press, Inc.
Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The pagerank citation ranking: Bringing order to the web (No. Previous number=SIDL-WP-1999-0120).
Prakash, B. A., Chakrabarti, D., Valler, N. C., Faloutsos, M., & Faloutsos, C. (2012). Threshold conditions for arbitrary cascade models on arbitrary networks. Knowledge and Information Systems, 33(3), 549–575.
Song, C., Hsu, W., & Lee, M. L. (2015). Node Immunization over Infectious Period. In Proceedings of the 24th ACM International Conference on Information and Knowledge Management (pp. 831–840).
Tong, H., Prakash, B. A., Tsourakakis, C., Eliassi-Rad, T., Faloutsos, C., & Chau, D. H. (2010). On the vulnerability of large graphs. Proceedings - IEEE International Conference on Data Mining, ICDM, 1091–1096.
van Dam, E. R., & Kooij, R. E. (2007). The minimal spectral radius of graphs with a given diameter. Linear Algebra and Its Applications, 423(2–3), 408–419.
Wang, Y., Chakrabarti, D., Wang, C., & Faloutsos, C. (2003). Epidemic spreading in real networks: an eigenvalue viewpoint. In 22nd International Symposium on Reliable Distributed Systems, 2003. Proceedings. (pp. 25–34). IEEE Comput. Soc.
Watts, D., & Strogatz, S. (1998). Collective dynamics of ’small-world’ networks. Nature, 393(June), 440–442.
Wijayanto, A. W., & Murata, T. (2017). Flow-Aware vertex protection strategy on large social networks. In Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2017.
Wijayanto, A. W., & Murata, T. (2018a). Learning Adaptive Graph Protection Strategy on Dynamic Networks via Reinforcement Learning. In 2018 IEEE/WIC/ACM International Conference on Web Intelligence (WI) (pp. 534–539). Santiago, Chile: IEEE.
Wijayanto, A. W., & Murata, T. (2018b). Pre-emptive spectral graph protection strategies on multiplex social networks. Applied Network Science, 3(1), 5.
Wijayanto, A. W., & Murata, T. (2019). Effective and scalable methods for graph protection strategies against epidemics on dynamic networks. Applied Network Science, 4(1), 18.
Wijayanto, A. W., & Takdir. (2014). Fighting cyber crime in email spamming: An evaluation of fuzzy clustering approach to classify spam messages. In 2014 International Conference on Information Technology Systems and Innovation (ICITSI) (pp. 19–24). IEEE.
Zhang, Y., & Prakash, B. A. (2014a). DAVA: Distributing Vaccines over Networks under Prior Information. In Proceedings of the 2014 SIAM International Conference on Data Mining (pp. 46–54). Philadelphia, PA: Society for Industrial and Applied Mathematics.
Zhang, Y., & Prakash, B. A. (2014b). Scalable Vaccine Distribution in Large Graphs given Uncertain Data. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management - CIKM ’14 (pp. 1719–1728). New York, New York, USA: ACM Press.
Zhang, Y., & Prakash, B. A. (2015). Data-Aware Vaccine Allocation Over Large Networks. Acm Transactions on Knowledge Discovery from Data, 10(2), 20.
Zhuang, H., Sun, Y., Tang, J., Zhang, J., & Sun, X. (2013). Influence maximization in dynamic social networks. Proceedings - IEEE International Conference on Data Mining, ICDM, 1313–1318.
Brouwer, A. E., & Haemers, W. H. (2012). Spectra of Graphs. New York, NY: Springer New York.
Chen, C., Tong, H., Prakash, B. A., Tsourakakis, C. E., Eliassi-Rad, T., Faloutsos, C., & Chau, D. H. (2016). Node Immunization on Large Graphs: Theory and Algorithms. IEEE Transactions on Knowledge and Data Engineering, 28(1), 113–126.
Chung, F. R. K. (1997). Spectral Graph Theory. Providence, Rhode Island, USA: American Mathematical Society.
Dangalchev, C. (2006). Residual closeness in networks. Physica A: Statistical Mechanics and Its Applications, 365(2), 556–564.
Gerasimov, E. N., & Repko, V. N. (1978). Multicriterial optimization. Soviet Applied Mechanics, 14(11), 1179–1184.
Kermack, W. O., & McKendrick, A. G. (1927). A Contribution to the Mathematical Theory of Epidemics. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 115(772), 700–721.
Lee, S. H. (Mark), Cotte, J., & Noseworthy, T. J. (2010). The role of network centrality in the flow of consumer influence. Journal of Consumer Psychology, 20(1), 66–77.
Lusseau, D., Schneider, K., Boisseau, O. J., Haase, P., Slooten, E., & Dawson, S. M. (2003). The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations: Can geographic isolation explain this unique trait? Behavioral Ecology and Sociobiology, 54(4), 396–405.
Marler, R. T., & Arora, J. S. (2004). Survey of multi-objective optimization methods for engineering. Structural and Multidisciplinary Optimization, 26(6), 369–395.
Newman, M. (2010). Networks: An Introduction. New York, NY, USA: Oxford University Press, Inc.
Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The pagerank citation ranking: Bringing order to the web (No. Previous number=SIDL-WP-1999-0120).
Prakash, B. A., Chakrabarti, D., Valler, N. C., Faloutsos, M., & Faloutsos, C. (2012). Threshold conditions for arbitrary cascade models on arbitrary networks. Knowledge and Information Systems, 33(3), 549–575.
Song, C., Hsu, W., & Lee, M. L. (2015). Node Immunization over Infectious Period. In Proceedings of the 24th ACM International Conference on Information and Knowledge Management (pp. 831–840).
Tong, H., Prakash, B. A., Tsourakakis, C., Eliassi-Rad, T., Faloutsos, C., & Chau, D. H. (2010). On the vulnerability of large graphs. Proceedings - IEEE International Conference on Data Mining, ICDM, 1091–1096.
van Dam, E. R., & Kooij, R. E. (2007). The minimal spectral radius of graphs with a given diameter. Linear Algebra and Its Applications, 423(2–3), 408–419.
Wang, Y., Chakrabarti, D., Wang, C., & Faloutsos, C. (2003). Epidemic spreading in real networks: an eigenvalue viewpoint. In 22nd International Symposium on Reliable Distributed Systems, 2003. Proceedings. (pp. 25–34). IEEE Comput. Soc.
Watts, D., & Strogatz, S. (1998). Collective dynamics of ’small-world’ networks. Nature, 393(June), 440–442.
Wijayanto, A. W., & Murata, T. (2017). Flow-Aware vertex protection strategy on large social networks. In Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2017.
Wijayanto, A. W., & Murata, T. (2018a). Learning Adaptive Graph Protection Strategy on Dynamic Networks via Reinforcement Learning. In 2018 IEEE/WIC/ACM International Conference on Web Intelligence (WI) (pp. 534–539). Santiago, Chile: IEEE.
Wijayanto, A. W., & Murata, T. (2018b). Pre-emptive spectral graph protection strategies on multiplex social networks. Applied Network Science, 3(1), 5.
Wijayanto, A. W., & Murata, T. (2019). Effective and scalable methods for graph protection strategies against epidemics on dynamic networks. Applied Network Science, 4(1), 18.
Wijayanto, A. W., & Takdir. (2014). Fighting cyber crime in email spamming: An evaluation of fuzzy clustering approach to classify spam messages. In 2014 International Conference on Information Technology Systems and Innovation (ICITSI) (pp. 19–24). IEEE.
Zhang, Y., & Prakash, B. A. (2014a). DAVA: Distributing Vaccines over Networks under Prior Information. In Proceedings of the 2014 SIAM International Conference on Data Mining (pp. 46–54). Philadelphia, PA: Society for Industrial and Applied Mathematics.
Zhang, Y., & Prakash, B. A. (2014b). Scalable Vaccine Distribution in Large Graphs given Uncertain Data. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management - CIKM ’14 (pp. 1719–1728). New York, New York, USA: ACM Press.
Zhang, Y., & Prakash, B. A. (2015). Data-Aware Vaccine Allocation Over Large Networks. Acm Transactions on Knowledge Discovery from Data, 10(2), 20.
Zhuang, H., Sun, Y., Tang, J., Zhang, J., & Sun, X. (2013). Influence maximization in dynamic social networks. Proceedings - IEEE International Conference on Data Mining, ICDM, 1313–1318.
Downloads
Published
2019-09-30
Issue
Section
Articles
How to Cite
Effective Graph Protection Method to Prevent the Spreading of Attacks in Networks (A. W. Wijayanto & A. Pindarwati , Trans.). (2019). Indonesian Journal of Computing, Engineering, and Design (IJoCED), 1(2), 77-88. https://doi.org/10.35806/ijoced.v1i2.61
