Edge influence computation in dynamic graphs

Yongrui Qin*, Quan Z. Sheng, Simon Parkinson, Nickolas J.G. Falkner

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

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 languageEnglish
Title of host publication22nd International Conference on Database Systems for Advanced Applications : proceedings
Subtitle of host publicationDASFAA 2017
EditorsSelçuk Candan, Lijun Chang, Lei Chen, Wen Hua, Torben Bach Pedersen
Place of PublicationCham, Switzerland
PublisherSpringer, Springer Nature
Pages649-660
Number of pages12
ISBN (Electronic)9783319556994
ISBN (Print)9783319556987
DOIs
Publication statusPublished - 2017
Event22nd International Conference on Database Systems for Advanced Applications, DASFAA 2017 - Suzhuo, China
Duration: 27 Mar 201730 Mar 2017

Publication series

NameLecture Notes in Computer Science
Volume10178
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference22nd International Conference on Database Systems for Advanced Applications, DASFAA 2017
CountryChina
CitySuzhuo
Period27/03/1730/03/17

Keywords

  • Dynamic graph
  • Edge influence
  • Graph reachability

Fingerprint Dive into the research topics of 'Edge influence computation in dynamic graphs'. Together they form a unique fingerprint.

Cite this