Abstract
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.
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 |
Volume | LNCS 10178 |
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/Territory | China |
City | Suzou |
Period | 27/03/17 → 30/03/17 |
Internet address |
|