Iterative diffusion importance: advancing edge criticality evaluation in complex networks

Jarrah A.A., Ejjbiri H., Lubashevskiy V.
 pdf (3882K)

This paper is devoted to the problem of edge criticality identification and ranking in complex networks, which is a part of a modern research direction in the novel network science. The diffusion importance belongs to the set of acknowledged methods that help to identify the significant connections in the graph that are critical to retaining structural integrity. In the present work, we develop the Iterative Diffusion Importance algorithm that is based on the re-estimation of critical topological features at each step of the graph deconstruction. The Iterative Diffusion Importance has been compared with methods such as diffusion importance and degree product, which are two very well-known benchmark algorithms. As for benchmark networks, we tested the Iterative Diffusion Importance on three standard networks, such as Zachary’s Karate Club, the American Football Network, and the Dolphins Network, which are often used for algorithm efficiency evaluation and are different in size and density. Also, we proposed a new benchmark network representing the airplane communication between Japan and the US. The numerical experiment on finding the ranking of critical edges and the following network decomposition demonstrated that the proposed Iterative Diffusion Importance exceeds the conventional diffusion importance by the efficiency for 2–35% depending on the network complexity, the number of nodes, and the number of edges. The only drawback of the Iterative Diffusion Importance is an increase in computation complexity and hencely in the runtime, but this drawback can be easily compensated for by the preliminary planning of the network deconstruction or protection and by reducing the re-evaluation frequency of the iterative process.

Keywords: edge significance, diffusion importance, complex networks
Citation in English: Jarrah A.A., Ejjbiri H., Lubashevskiy V. Iterative diffusion importance: advancing edge criticality evaluation in complex networks // Computer Research and Modeling, 2025, vol. 17, no. 5, pp. 783-797
Citation in English: Jarrah A.A., Ejjbiri H., Lubashevskiy V. Iterative diffusion importance: advancing edge criticality evaluation in complex networks // Computer Research and Modeling, 2025, vol. 17, no. 5, pp. 783-797
DOI: 10.20537/2076-7633-2025-17-5-783-797
URL: http://crm-en.ics.org.ru/journal/article/3652/
Creative Commons License This work is licensed under a Creative Commons Attribution-NoDerivs 3.0 Unported License.

Copyright © 2025 Jarrah A.A., Ejjbiri H., Lubashevskiy V.

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"

Website Copyright © 2009–2026 Institute of Computer Science