Edge Influence Computation in Dynamic Graphs

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

doi:10.1007/978-3-319-55699-4_41

Edge Influence Computation in Dynamic Graphs

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-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 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	https://doi.org/10.1007/978-3-319-55699-4_41
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	https://link.springer.com/book/10.1007/978-3-319-55753-3 (Link to Conference Details )

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1007/978-3-319-55699-4_41Licence: Unspecified

http://eprints.hud.ac.uk/id/eprint/30895/Licence: Unspecified

Cite this

Qin, Y., Sheng, Q. Z., Parkinson, S., & Falkner, N. J. G. (2017). Edge Influence Computation in Dynamic Graphs. In S. Candan, L. Chen, T. B. Pedersen, L. Chang, & W. Hua (Eds.), Database Systems for Advanced Applications: 22nd International Conference, DASFAA 2017, Suzhou, China, March 27-30, 2017, Proceedings, Part II (Vol. LNCS 10178, pp. 649-660). (Lecture Notes in Computer Science; Vol. 10178). Springer, Cham. https://doi.org/10.1007/978-3-319-55699-4_41

Qin, Yongrui ; Sheng, Quan Z. ; Parkinson, Simon et al. / Edge Influence Computation in Dynamic Graphs. Database Systems for Advanced Applications: 22nd International Conference, DASFAA 2017, Suzhou, China, March 27-30, 2017, Proceedings, Part II. editor / Selçuk Candan ; Lei Chen ; Torben Bach Pedersen ; Lijun Chang ; Wen Hua. Vol. LNCS 10178 Springer, Cham, 2017. pp. 649-660 (Lecture Notes in Computer Science).

@inproceedings{5551542058714c4b87d5c03f92027a0b,

title = "Edge Influence Computation in Dynamic Graphs",

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.",

keywords = "graph reachability, dynamic graph, edge influence",

author = "Yongrui Qin and Sheng, {Quan Z.} and Simon Parkinson and Falkner, {Nickolas J G}",

year = "2017",

month = mar,

day = "22",

doi = "10.1007/978-3-319-55699-4_41",

language = "English",

isbn = "9783319556987",

volume = "LNCS 10178",

series = "Lecture Notes in Computer Science",

publisher = "Springer, Cham",

pages = "649--660",

editor = "Sel{\c c}uk Candan and Lei Chen and Pedersen, {Torben Bach} and Lijun Chang and Wen Hua",

booktitle = "Database Systems for Advanced Applications",

address = "Switzerland",

note = "22nd International Conference on Database Systems for Advanced Applications, DASFAA 2017 ; Conference date: 27-03-2017 Through 30-03-2017",

url = "https://link.springer.com/book/10.1007/978-3-319-55753-3",

}

Qin, Y, Sheng, QZ, Parkinson, S & Falkner, NJG 2017, Edge Influence Computation in Dynamic Graphs. in S Candan, L Chen, TB Pedersen, L Chang & W Hua (eds), Database Systems for Advanced Applications: 22nd International Conference, DASFAA 2017, Suzhou, China, March 27-30, 2017, Proceedings, Part II. vol. LNCS 10178, Lecture Notes in Computer Science, vol. 10178, Springer, Cham, pp. 649-660, 22nd International Conference on Database Systems for Advanced Applications, Suzou, China, 27/03/17. https://doi.org/10.1007/978-3-319-55699-4_41

Edge Influence Computation in Dynamic Graphs. / Qin, Yongrui; Sheng, Quan Z.; Parkinson, Simon et al.

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. Vol. LNCS 10178 Springer, Cham, 2017. p. 649-660 (Lecture Notes in Computer Science; Vol. 10178).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Edge Influence Computation in Dynamic Graphs

AU - Qin, Yongrui

AU - Sheng, Quan Z.

AU - Parkinson, Simon

AU - Falkner, Nickolas J G

N1 - Conference code: 22

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

VL - LNCS 10178

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

T2 - 22nd International Conference on Database Systems for Advanced Applications

Y2 - 27 March 2017 through 30 March 2017

ER -

Qin Y, Sheng QZ, Parkinson S, Falkner NJG. Edge Influence Computation in Dynamic Graphs. In Candan S, Chen L, Pedersen TB, Chang L, Hua W, editors, Database Systems for Advanced Applications: 22nd International Conference, DASFAA 2017, Suzhou, China, March 27-30, 2017, Proceedings, Part II. Vol. LNCS 10178. Springer, Cham. 2017. p. 649-660. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-55699-4_41

Edge Influence Computation in Dynamic Graphs

Abstract

Publication series

Conference

UN SDGs

Access to Document

Fingerprint

Cite this