Discovering important nodes of complex networks based on laplacian spectra

Abstract

© 2023 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes,creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Knowledge of the Laplacian eigenvalues of a network provides important insights into its structural features and dynamical behaviours. Node or link removal caused by possible outage events, such as mechanical and electrical failures or malicious attacks, significantly impacts the Laplacian spectra. This can also happen due to intentional node removal against which, increasing the algebraic connectivity is desired. In this article, an analytical metric is proposed to measure the effect of node removal on the Laplacian eigenvalues of the network. The metric is formulated based on the local multiplicity of each eigenvalue at each node, so that the effect of node removal on any particular eigenvalues can be approximated using only one single eigen-decomposition of the Laplacian matrix. The metric is applicable to undirected networks as well as strongly-connected directed ones. It also provides a reliable approximation for the “Laplacian energy” of a network. The performance of the metric is evaluated for several synthetic networks and also the American Western States power grid. Results show that this metric has a nearly perfect precision in correctly predicting the most central nodes, and significantly outperforms other comparable heuristic methods.

This research was partly supported by the Erasmus+ KA107 grant. AMA, MJ, LS and XY were supported by the Australian Research Council through project No. DP170102303. MJ and XY are also supported by the Australian Research Council through project No. DP200101199. MAF was supported by AGAUR from the Catalan Government under project 2017SGR1087, and by MICINN from the Spanish Government with the European Regional Development Fund under project PGC2018-095471-B-I00

Peer Reviewed

Postprint (author's final draft)