R-energy for evaluating robustness of dynamic networks
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 net...
Saved in:
Main Authors: | , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2013
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/1894 https://ink.library.smu.edu.sg/context/sis_research/article/2893/viewcontent/p89_gao.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-2893 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-28932018-07-13T03:17:57Z R-energy for evaluating robustness of dynamic networks GAO, Ming LIM, Ee Peng LO, David 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. 2013-05-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/1894 info:doi/10.1145/2464464.2464486 https://ink.library.smu.edu.sg/context/sis_research/article/2893/viewcontent/p89_gao.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University R-energy Network robustness Normalized Laplacian matrix Databases and Information Systems Numerical Analysis and Scientific Computing |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
R-energy Network robustness Normalized Laplacian matrix Databases and Information Systems Numerical Analysis and Scientific Computing |
spellingShingle |
R-energy Network robustness Normalized Laplacian matrix Databases and Information Systems Numerical Analysis and Scientific Computing GAO, Ming LIM, Ee Peng LO, David R-energy for evaluating robustness of dynamic networks |
description |
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. |
format |
text |
author |
GAO, Ming LIM, Ee Peng LO, David |
author_facet |
GAO, Ming LIM, Ee Peng LO, David |
author_sort |
GAO, Ming |
title |
R-energy for evaluating robustness of dynamic networks |
title_short |
R-energy for evaluating robustness of dynamic networks |
title_full |
R-energy for evaluating robustness of dynamic networks |
title_fullStr |
R-energy for evaluating robustness of dynamic networks |
title_full_unstemmed |
R-energy for evaluating robustness of dynamic networks |
title_sort |
r-energy for evaluating robustness of dynamic networks |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2013 |
url |
https://ink.library.smu.edu.sg/sis_research/1894 https://ink.library.smu.edu.sg/context/sis_research/article/2893/viewcontent/p89_gao.pdf |
_version_ |
1770571647541051392 |