On measuring network robustness for weighted networks

Network robustness measures how well network structure is strong and healthy when it is under attack, such as vertices joining and leaving. It has been widely used in many applications, such as information diffusion, disease transmission, and network security. However, existing metrics, including no...

Full description

Saved in:
Bibliographic Details
Main Authors: ZHENG, Jianbing, GAO, Ming, LIM, Ee-peng, LO, David, JIN, Cheqing, ZHOU, Aoying
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2022
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/7233
https://ink.library.smu.edu.sg/context/sis_research/article/8236/viewcontent/203423942_On_Measuring_Network_Robustness_for_Weighted_Networks.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
Description
Summary:Network robustness measures how well network structure is strong and healthy when it is under attack, such as vertices joining and leaving. It has been widely used in many applications, such as information diffusion, disease transmission, and network security. However, existing metrics, including node connectivity, edge connectivity, and graph expansion, can be suboptimal for measuring network robustness since they are inefficient to be computed and cannot directly apply to the weighted networks or disconnected networks. In this paper, we define the RR-energy as a new robustness measurement for weighted networks based on the method of spectral analysis. RR-energy can cope with disconnected networks and is efficient to compute with a time complexity of O(|V|+|E|)O(|V|+|E|), where V and E are sets of vertices and edges in the network, respectively. Our experiments illustrate the rationality and efficiency of computing RR-energy: (1) Removal of high degree vertices reduces network robustness more than that of random or small degree vertices; (2) it takes as little as 120 s to compute for a network with about 6M vertices and 33M edges. We can further detect events occurring in a dynamic Twitter network with about 130K users and discover interesting weekly tweeting trends by tracking changes to RR-energy.