Effective Graph Protection Method to Prevent the Spreading of Attacks in Networks

  • A. W. Wijayanto Department of Computer Science, Tokyo Institute of Technology, Japan
  • A. Pindarwati Badan Pusat Statistik (BPS) Indonesia, Jakarta, Indonesia


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.


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 Transac-tions 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 Mechan-ics, 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 engi-neering. 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: Bring-ing 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 Infor-mation Systems, 33(3), 549–575.
Song, C., Hsu, W., & Lee, M. L. (2015). Node Immunization over Infectious Period. In Pro-ceedings 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 di-ameter. Linear Algebra and Its Applications, 423(2–3), 408–419.
Wang, Y., Chakrabarti, D., Wang, C., & Faloutsos, C. (2003). Epidemic spreading in real net-works: an eigenvalue viewpoint. In 22nd International Symposium on Reliable Distrib-uted 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 so-cial networks. In Proceedings of the 2017 IEEE/ACM International Conference on Ad-vances 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 Confer-ence 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 Un-certain 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.
How to Cite
WIJAYANTO, A. W.; PINDARWATI, A.. Effective Graph Protection Method to Prevent the Spreading of Attacks in Networks. Indonesian Journal of Computing, Engineering and Design (IJoCED), [S.l.], v. 1, n. 2, p. 77-88, sep. 2019. ISSN 2656-8179. Available at: <http://ojs.sampoernauniversity.ac.id/index.php/IJOCED/article/view/61>. Date accessed: 18 nov. 2019. doi: https://doi.org/10.35806/ijoced.v1i2.61.