Enhancing network security with graph theory through identification of critical nodes and vulnerabilities
Y. M. Manjunathy.manjunath@jaincollege.ac.inDepartment of MathematicsBGS Institute TechnologyAdichunchanagiri UniversityB. G Nagara, Mandya, Karnataka, 571811, IndiaView full profile → , *H. L. ParashivamurthyCorresponding authorparashivamurthyhl@bgsit.ac.inDepartment of MathematicsBGS Institute of TechnologyAdichunchanagiri UniversityB. G Nagara, Mandya, Karnataka, 571811, IndiaView full profile → , S. Girish Babugirishbabu.s@rrit.ac.inDepartment of MathematicsR R Institute of TechnologyBangalore, Karnataka, 560090, IndiaView full profile → , G. Manjunathmanjunath.g@rrit.ac.inDepartment of MathematicsR R Institute of TechnologyBangalore, Karnataka, 560090, IndiaView full profile →
* Corresponding author · click or hover a name for details
- Received:
- 01 Nov 2025
- Published Online:
- 14 Aug 2026
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JDMSC-2690
- Pages:
- 3051–3064
Abstract
The concept of network security is on the increase in the digital era and cyber threats have increasingly become more advanced and sophisticated. This study examines the research of finding critical nodes with the help of a graph theory and determining weaknesses in network structures. The analysis of the network based on centrality metrics which include degree, betweenness and closeness centrality names important node identities that are essential in ensuring the network remains connected and efficient. The effect of node failure is estimated using the MATLAB simulation, and it is concentrated on how the centrality of nodes is compromised to cause network fragmentation and performance deterioration. The findings demonstrate the importance of centrality metrics in identifying vulnerabilities in a network, and degree-centrality nodes are the most susceptible systems to failure. Betweenness and closeness centrality also underscore how important nodes are in regulating the movement of the network and removing delays. The results confirm the usefulness of the graph theory-related approaches to enhancing the security of the network through providing information on the identification of the key nodes and simulation of attacks. The paper also shows the capabilities of dynamic simulations versus the static methodology that offers real-time analysis of network vulnerabilities and security policies. It is a work in progress to expand these methods to larger networks (including real-time data to detect vulnerabilities) and improve recovery measures in the future.
Keywords
Subject Classifications
References
[1] G. N. Kannaiyan and R. Veerubommu, “Graph theory matrix approach in cryptography and network security,” in Proc. 2022 Algorithms, Computing and Mathematics Conf. (ACM), Chennai, India, pp. 108–110 (2022), doi: 10.1109/ACM57404.2022.00025.
[2] H. A. Dawood, “Graph theory and cyber security,” in 2014 3rd Int. Conf. Advanced Computer Science Applications and Technologies, Amman, Jordan, pp. 90–96 (2014).
[3] I. Boufelgha, M. Ahmia, and M. Guettiche, “Secure 2-domination in graphs,” J. Discrete Mathematical Sciences and Cryptography, vol. 28, no. 7, pp. 2723–2736 (2025).
[4] N. Khokhlov, S. Kanavin, and A. Rybokitov, “Modeling information security infringements in mobile self-organizing network of communication using fuzzy logic and theory of graphs,” in 2019 1st Int. Conf. Control Systems, Mathematical Modelling, Automation and Energy Efficiency (SUMMA), Lipetsk, Russia, pp. 60–63 (2019).
[5] Y. Huang and D. Li, “Design of malicious software classification and recognition algorithms based on graph theory in computer networks,” in 2024 Int. Conf. Interactive Intelligent Systems and Techniques (IIST), Bhubaneswar, India, pp. 593–597 (2024).
[6] A. Torres and G. Anders, “Spectral graph theory and network dependability,” in 2009 Fourth Int. Conf. Dependability of Computer Systems, Brunow, Poland, pp. 356–363 (2009).
[7] F. Zhang and B. Bu, “A cyber security risk assessment methodology for CBTC systems based on complex network theory and attack graph,” in 2021 7th Annual Int. Conf. Network and Information Systems for Computers (ICNISC), Guiyang, China, pp. 15–20 (2021).
[8] A. S. Odyuo, P. Mercy, and M. K. Patel, “Fibonacci range labeling on direct product and union of graphs,” J. Discrete Mathematical Sciences and Cryptography, vol. 28, no. 7, pp. 2671–2678 (2025).
[9] W. Jiang, B.-X. Fang, H.-L. Zhang, Z.-H. Tian, and X.-F. Song, “Optimal network security strengthening using attack-defense game model,” in 2009 Sixth Int. Conf. Information Technology: New Generations, Las Vegas, NV, USA, pp. 475–480 (2009).
[10] M. Aouina, H. Karami, and D. J. LaFountain, “Distance-balancing of cube-connected cycles graphs,” J. Discrete Mathematical Sciences and Cryptography, vol. 28, no. 7, pp. 2849–2861 (2025).
[11] H. Gao, S. Wang, H. Zhang, B. Liu, D. Zhao, and Z. Liu, “Network security situation assessment method based on absorbing Markov chain,” in 2022 Int. Conf. Networking and Network Applications (NaNA), Urumqi, China, pp. 556–561 (2022).
[12] L. Lima, M. Médard, and J. Barros, “Random linear network coding: A free cipher?” in 2007 IEEE Int. Symp. Information Theory, Nice, France, pp. 546–550 (2007).
[13] V. Dankan Gowda, N. Suganthi, V. N. Prasad, M. R. Tarambale, P. S. V. V. S. R. Kumar, and A. Muthusamy, “Implementing secure cryptographic protocols in 5G and 6G networks,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 28, no. 5-A, pp. 1505–1515 (2025), doi: 10.47974/JDMSC-2149.
[14] F. Xu, “Design of network attack traceability algorithm based on graph neural network and complex network theory,” in 2024 3rd Int. Conf. Artificial Intelligence and Autonomous Robot Systems (AIARS), Bristol, United Kingdom, pp. 705–710 (2024).
[15] H. Ge, L. Gu, Y. Yang, and K. Liu, “An attack graph based network security evaluation model for hierarchical network,” in 2010 IEEE Int. Conf. Information Theory and Information Security, Beijing, China, pp. 208–211 (2010).
[16] M. Keramati and A. Akbari, “An attack graph based metric for security evaluation of computer networks,” in 6th Int. Symp. Telecommunications (IST), Tehran, Iran, pp. 1094–1098 (2012).
[17] D. Man, B. Zhang, W. Yang, W. Jin, and Y. Yang, “A method for global attack graph generation,” in 2008 IEEE Int. Conf. Networking, Sensing and Control, Sanya, China, pp. 236–241 (2008).
[18] V. Dankan Gowda, V. Praveena, M. Nagabhushanam, P. SVVSR Kumar, C. R. Q. Lezama, and D. Pathak, “Homomorphic encryption performance in secure data processing for machine learning,” J. Discrete Mathematical Sciences and Cryptography, vol. 28, no. 5-A, pp. 1517–1526 (2025).
[19] Q. Xu, S. Yang, L. Xu, and D. Zhao, “Android malware detection method based on graph convolutional networks,” in 2024 Int. Conf. Artificial Intelligence and Power Systems (AIPS), Chengdu, China, pp. 95–98 (2024).
[20] L. Hailin, W. Yadi, and H. Jihong, “A novel method for modeling complex network of software system security,” in 2012 IEEE Sixth Int. Conf. Software Security and Reliability Companion, Gaithersburg, MD, USA, pp. 24–26 (2012).
