Publication Type

Conference Proceeding Article

Version

acceptedVersion

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

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Publication

WebSci '13: Proceedings of the 5th Annual ACM Web Science Conference

First Page

89

Last Page

98

ISBN

9781450318891

Identifier

10.1145/2464464.2464486

Publisher

ACM

City or Country

Paris

Copyright Owner and License

LARC

Additional URL

http://doi.org/10.1145/2464464.2464486

Download

Share

COinS