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

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

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

Since 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).

LanguageEnglish
Pages915-937
Number of pages23
JournalWorld Wide Web
Volume20
Issue number5
Early online date20 Oct 2016
DOIs
Publication statusPublished - Sep 2017

Fingerprint

Labeling

Cite this

Qin, Yongrui ; Sheng, Quan Z. ; Falkner, Nickolas J G ; Yao, Lina ; Parkinson, Simon. / Efficient computation of distance labeling for decremental updates in large dynamic graphs. In: World Wide Web. 2017 ; Vol. 20, No. 5. pp. 915-937.
@article{4eb4c0fa9a76487d8097623db81898a3,
title = "Efficient computation of distance labeling for decremental updates in large dynamic graphs",
abstract = "Since 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).",
keywords = "Distance labeling, Dynamic graph, Graph computation, Shortest path",
author = "Yongrui Qin and Sheng, {Quan Z.} and Falkner, {Nickolas J G} and Lina Yao and Simon Parkinson",
year = "2017",
month = "9",
doi = "10.1007/s11280-016-0421-1",
language = "English",
volume = "20",
pages = "915--937",
journal = "World Wide Web",
issn = "1386-145X",
publisher = "Springer New York",
number = "5",

}

Efficient computation of distance labeling for decremental updates in large dynamic graphs. / Qin, Yongrui; Sheng, Quan Z.; Falkner, Nickolas J G; Yao, Lina; Parkinson, Simon.

In: World Wide Web, Vol. 20, No. 5, 09.2017, p. 915-937.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Qin, Yongrui

AU - Sheng, Quan Z.

AU - Falkner, Nickolas J G

AU - Yao, Lina

AU - Parkinson, Simon

PY - 2017/9

Y1 - 2017/9

N2 - Since 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).

AB - Since 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).

KW - Distance labeling

KW - Dynamic graph

KW - Graph computation

KW - Shortest path

UR - http://www.scopus.com/inward/record.url?scp=84991758386&partnerID=8YFLogxK

U2 - 10.1007/s11280-016-0421-1

DO - 10.1007/s11280-016-0421-1

M3 - Article

VL - 20

SP - 915

EP - 937

JO - World Wide Web

T2 - World Wide Web

JF - World Wide Web

SN - 1386-145X

IS - 5

ER -