Abstract
| Original language | English |
|---|---|
| Title of host publication | Database Systems for Advanced Applications |
| Subtitle of host publication | 22nd International Conference, DASFAA 2017, Suzhou, China, March 27-30, 2017, Proceedings, Part II |
| Editors | Selçuk Candan, Lei Chen, Torben Bach Pedersen, Lijun Chang, Wen Hua |
| Publisher | Springer, Cham |
| Pages | 649-660 |
| Number of pages | 12 |
| ISBN (Electronic) | 9783319556994 |
| ISBN (Print) | 9783319556987 |
| DOIs | |
| Publication status | Published - 22 Mar 2017 |
| Event | 22nd International Conference on Database Systems for Advanced Applications - Suzou, China Duration: 27 Mar 2017 → 30 Mar 2017 Conference number: 22 https://link.springer.com/book/10.1007/978-3-319-55753-3 (Link to Conference Details ) |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer |
| Volume | 10178 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 22nd International Conference on Database Systems for Advanced Applications |
|---|---|
| Abbreviated title | DASFAA 2017 |
| Country | China |
| City | Suzou |
| Period | 27/03/17 → 30/03/17 |
| Internet address |
|
Fingerprint
Cite this
}
Edge Influence Computation in Dynamic Graphs. / Qin, Yongrui; Sheng, Quan Z.; Parkinson, Simon; Falkner, Nickolas J G.
Database Systems for Advanced Applications: 22nd International Conference, DASFAA 2017, Suzhou, China, March 27-30, 2017, Proceedings, Part II. ed. / Selçuk Candan; Lei Chen; Torben Bach Pedersen; Lijun Chang; Wen Hua. Springer, Cham, 2017. p. 649-660 (Lecture Notes in Computer Science; Vol. 10178).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
TY - GEN
T1 - Edge Influence Computation in Dynamic Graphs
AU - Qin, Yongrui
AU - Sheng, Quan Z.
AU - Parkinson, Simon
AU - Falkner, Nickolas J G
PY - 2017/3/22
Y1 - 2017/3/22
N2 - Reachability queries are of great importance in many research and application areas, including general graph mining, social network analysis and so on. Many approaches have been proposed to compute whether there exists one path from one node to another node in a graph. Most of these approaches focus on static graphs, however in practice dynamic graphs are more common. In this paper, we focus on handling graph reachability queries in dynamic graphs. Specifically we investigate the influence of a given edge in the graph, aiming to study the overall reachability changes in the graph brought by the possible failure/deletion of the edge. To this end, we firstly develop an efficient update algorithm for handling edge deletions. We then define the edge influence concept and put forward a novel computation algorithm to accelerate the computation of edge influence. We evaluate our approach using several real world datasets. The experimental results show that our approach outperforms traditional approaches significantly.
AB - Reachability queries are of great importance in many research and application areas, including general graph mining, social network analysis and so on. Many approaches have been proposed to compute whether there exists one path from one node to another node in a graph. Most of these approaches focus on static graphs, however in practice dynamic graphs are more common. In this paper, we focus on handling graph reachability queries in dynamic graphs. Specifically we investigate the influence of a given edge in the graph, aiming to study the overall reachability changes in the graph brought by the possible failure/deletion of the edge. To this end, we firstly develop an efficient update algorithm for handling edge deletions. We then define the edge influence concept and put forward a novel computation algorithm to accelerate the computation of edge influence. We evaluate our approach using several real world datasets. The experimental results show that our approach outperforms traditional approaches significantly.
KW - graph reachability
KW - dynamic graph
KW - edge influence
U2 - 10.1007/978-3-319-55699-4_41
DO - 10.1007/978-3-319-55699-4_41
M3 - Conference contribution
SN - 9783319556987
T3 - Lecture Notes in Computer Science
SP - 649
EP - 660
BT - Database Systems for Advanced Applications
A2 - Candan, Selçuk
A2 - Chen, Lei
A2 - Pedersen, Torben Bach
A2 - Chang, Lijun
A2 - Hua, Wen
PB - Springer, Cham
ER -