Current studentsExisting staffContact us
 

Efficient computation of distance labeling for decremental updates in large dynamic graphs

Simple item page
dc.contributor.authorQin, Y.
dc.contributor.authorSheng, Q.
dc.contributor.authorFalkner, N.
dc.contributor.authorYao, L.
dc.contributor.authorParkinson, S.
dc.date.issued2017
dc.descriptionPublished online: 20 October 2016
dc.description.abstractSince today’s real-world graphs, such as social network graphs, are evolving all the time, it is of great importance to perform graph computations and analysis in these dynamic graphs. Due to the fact that many applications such as social network link analysis with the existence of inactive users need to handle failed links or nodes, decremental computation and maintenance for graphs is considered a challenging problem. Shortest path computation is one of the most fundamental operations for managing and analyzing large graphs. A number of indexing methods have been proposed to answer distance queries in static graphs. Unfortunately, there is little work on answering such queries for dynamic graphs. In this paper, we focus on the problem of computing the shortest path distance in dynamic graphs, particularly on decremental updates (i.e., edge deletions). We propose maintenance algorithms based on distance labeling, which can handle decremental updates efficiently. By exploiting properties of distance labeling in original graphs, we are able to efficiently maintain distance labeling for new graphs. We experimentally evaluate our algorithms using eleven real-world large graphs and confirm the effectiveness and efficiency of our approach. More specifically, our method can speed up index re-computation by up to an order of magnitude compared with the state-of-the-art method, Pruned Landmark Labeling (PLL).
dc.description.statementofresponsibilityYongrui Qin, Quan Z. Sheng, Nickolas J.G. Falkner, Lina Yao, Simon Parkinson
dc.identifier.citationWorld Wide Web, 2017; 20(5):915-937
dc.identifier.doi10.1007/s11280-016-0421-1
dc.identifier.issn1386-145X
dc.identifier.issn1573-1413
dc.identifier.orcidFalkner, N. [0000-0001-7892-6813]
dc.identifier.urihttp://hdl.handle.net/2440/108868
dc.language.isoen
dc.publisherSpringer
dc.rights© Springer Science+Business Media New York 2016
dc.source.urihttps://doi.org/10.1007/s11280-016-0421-1
dc.subjectShortest path; graph computation; distance labeling; dynamic graph
dc.titleEfficient computation of distance labeling for decremental updates in large dynamic graphs
dc.typeJournal article
pubs.publication-statusPublished

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
RA_hdl_108868.pdf
Size:
1.26 MB
Format:
Adobe Portable Document Format
Description:
Restricted Access
Download

Collections

Computer Science publications