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 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 \({\mathcal {R}}\)-energy as a new robustness measurement for weighted networks based on the method of spectral analysis. \({\mathcal {R}}\)-energy can cope with disconnected networks and is efficient to compute with a time complexity of \(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 \({\mathcal {R}}\)-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 \({\mathcal {R}}\)-energy.