Entropy-Based Approaches of Edge Significance Quantification in Complex Networks: Detection of Link Vulnerabilities Using Static, Dynamic and Group-Focused Methods

Global connectivity is an important issue for networks; in particular, the failure of a few edges in functioning may lead to the failure of the system or a process in its integrity. Initially, the interest in detecting the most vulnerable links in networks was caused by an attempt to prevent the potential breakdown and to increase the systems’ robustness. The recent activities for COVID-19 protection revealed that under some conditions blocking social interaction may be necessary in order to decrease the communication intensity and reduce the risk of the virus spread. The leading approach in edge significance quantification is link entropy (LE), which is based on topological information and community membership detection, Qian et al. [1]. The efficiency of this approach has been enhanced with improved link entropy (ILE), Lubashevskiy et al. [2], and deep link entropy (DLE), Ozaydin and Ozaydin [3]. In the present work, all three methods are compared with one another using well-known benchmark networks and simulating their decomposition. The main metric used in quantifying the algorithm efficiency is the fraction of nodes of the largest connected component, which decreases with link removal, and the space under the curve, which should be minimized. The obtained results show that ILE and DLE outperform the LE approach. The comparison between DLE and ILE demonstrates that when the data and knowledge about the network and similar systems are sufficient, the DLE approach can be more efficient because it takes into account not only the individual edge entropy but also the entropy of all the connected nodes around the removed link. In the case of properly selecting a community number detection algorithm, the ILE approach outperforms the DLE. Still, it requests much less computation and time due to lower computational complexity. The advantages, limitations, and possible improvements of the DLE and the ILE approaches are discussed and form the basis for future investigations.