Skip to main content
Article
R-energy for evaluating robustness of dynamic networks
WebSci '13: Proceedings of the 5th Annual ACM Web Science Conference
  • Ming GAO, Singapore Management University
  • Ee Peng LIM, Singapore Management University
  • David LO, Singapore Management University
Publication Type
Conference Proceeding Article
Publication Date
5-2013
Abstract
The robustness of a network is determined by how well its vertices are connected to one another so as to keep the network strong and sustainable. As the network evolves its robustness changes and may reveal events as well as periodic trend patterns that affect the interactions among users in the network. In this paper, we develop R-energy as a new measure of network robustness based on the spectral analysis of normalized Laplacian matrix. R-energy can cope with disconnected networks, and is efficient to compute with a time complexity of O (jV j + jEj) where V and E are the vertex set and edge set of the network respectively. This makes R-energy more efficient to compute than algebraic connectivity, another well known network robustness measure. Our experiments also show that removal of high degree vertices reduces network robustness (measured by R-energy) more than that of random or small degree vertices. R-energy can scale well for very large networks. It takes as little as 40 seconds to compute for a network with about 5M vertices and 69M 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 R-energy.
Keywords
  • R-energy,
  • network robustness,
  • normalized Laplacian matrix
ISBN
9781450318891
Identifier
10.1145/2464464.2464486
Publisher
ACM
City or Country
Paris
Additional URL
http://dx.doi.org/10.1145/2464464.2464486
Citation Information
Ming GAO, Ee Peng LIM and David LO. "R-energy for evaluating robustness of dynamic networks" WebSci '13: Proceedings of the 5th Annual ACM Web Science Conference (2013) p. 89 - 98
Available at: http://works.bepress.com/david_lo/118/