DSPC: Efficiently Answering Shortest Path Counting on Dynamic Graphs

Feng, Q; Peng, Y; Zhang, W; Lin, X; Zhang, Y

DSPC: Efficiently Answering Shortest Path Counting on Dynamic Graphs

Feng, Q Peng, Y Zhang, W Lin, X Zhang, Y

Permalink

Publication Type:: Conference Proceeding
Citation:: Advances in Database Technology - EDBT, 2023, 27, (1), pp. 116-128
Issue Date:: 2023-08-18

Recently Added

	Filename	Description	Size
	2014_EDBT.pdf	Published version	2.02 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is new to OPUS and is not currently available.

Full metadata record

Field	Value	Language
dc.contributor.author	Feng, Q
dc.contributor.author	Peng, Y
dc.contributor.author	Zhang, W
dc.contributor.author	Lin, X
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.date.accessioned	2024-11-26T13:45:02Z
dc.date.available	2024-11-26T13:45:02Z
dc.date.issued	2023-08-18
dc.identifier.citation	Advances in Database Technology - EDBT, 2023, 27, (1), pp. 116-128
dc.identifier.issn	2367-2005
dc.identifier.uri	http://hdl.handle.net/10453/182114
dc.description.abstract	The widespread use of graph data in various applications and the highly dynamic nature of today’s networks have made it imperative to analyze structural trends in dynamic graphs on a continual basis. The shortest path is a fundamental concept in graph analysis and recent research shows that counting the number of shortest paths between two vertices is crucial in applications like potential friend recommendation and betweenness analysis. However, current studies that use hub labeling techniques for real-time shortest path counting are limited by their reliance on a pre-computed index, which cannot tackle frequent updates over dynamic graphs. To address this, we propose a novel approach for maintaining the index in response to changes in the graph structure and develop incremental (IncSPC) and decremental (DecSPC) update algorithms for inserting and deleting vertices/edges, respectively. The main idea of these two algorithms is that we only locate the affected vertices to update the index. Our experiments demonstrate that our dynamic algorithms are up to four orders of magnitude faster processing for incremental updates and up to three orders of magnitude faster processing for hybrid updates than reconstruction.
dc.language	en
dc.relation	http://purl.org/au-research/grants/arc/DP230101445
dc.relation	http://purl.org/au-research/grants/arc/LP210301046
dc.relation.ispartof	Advances in Database Technology - EDBT
dc.relation.isbasedon	10.48786/edbt.2024.11
dc.rights	info:eu-repo/semantics/restrictedAccess
dc.title	DSPC: Efficiently Answering Shortest Path Counting on Dynamic Graphs
dc.type	Conference Proceeding
utslib.citation.volume	27
pubs.organisational-group	University of Technology Sydney
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	University of Technology Sydney/UTS Groups
pubs.organisational-group	University of Technology Sydney/UTS Groups/Australian Artificial Intelligence Institute (AAII)
utslib.copyright.status	recently_added	*
dc.rights.license	This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License (CC BY-NC-ND 4.0). To view a copy of this license, visit https://creativecommons.org/licenses/by-nc-nd/4.0/
dc.date.updated	2024-11-26T13:45:01Z
pubs.issue	1
pubs.publication-status	Published
pubs.volume	27
utslib.citation.issue	1

Abstract:

The widespread use of graph data in various applications and the highly dynamic nature of today’s networks have made it imperative to analyze structural trends in dynamic graphs on a continual basis. The shortest path is a fundamental concept in graph analysis and recent research shows that counting the number of shortest paths between two vertices is crucial in applications like potential friend recommendation and betweenness analysis. However, current studies that use hub labeling techniques for real-time shortest path counting are limited by their reliance on a pre-computed index, which cannot tackle frequent updates over dynamic graphs. To address this, we propose a novel approach for maintaining the index in response to changes in the graph structure and develop incremental (IncSPC) and decremental (DecSPC) update algorithms for inserting and deleting vertices/edges, respectively. The main idea of these two algorithms is that we only locate the affected vertices to update the index. Our experiments demonstrate that our dynamic algorithms are up to four orders of magnitude faster processing for incremental updates and up to three orders of magnitude faster processing for hybrid updates than reconstruction.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/182114