Publication Type

Journal Article

Version

publishedVersion

Publication Date

7-2022

Abstract

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.

Keywords

2-step commute probability, Normalized Laplacian matrix, R-energy, Weighted network

Discipline

Databases and Information Systems | Information Security

Research Areas

Data Science and Engineering

Publication

Knowledge and Information Systems

Volume

64

Issue

7

First Page

1967

Last Page

1996

ISSN

0219-1377

Identifier

10.1007/s10115-022-01670-z

Publisher

Springer Verlag (Germany)

Additional URL

https://doi.org/10.1007/s10115-022-01670-z

Download

Share

COinS