Towards Real-Time Counting Shortest Cycles on Dynamic Graphs: A Hub Labeling Approach

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

Towards Real-Time Counting Shortest Cycles on Dynamic Graphs: A Hub Labeling Approach

Feng, Q Peng, Y Zhang, W Zhang, Y

Lin, X

Permalink

Publisher:: IEEE
Publication Type:: Conference Proceeding
Citation:: Proceedings - International Conference on Data Engineering, 2022, 2022-May, pp. 512-524
Issue Date:: 2022-01-01

Closed Access

	Filename	Description	Size
	ICDE_22_Towards_Real-Time_Counting_Shortest_Cycles_on_Dynamic_Graphs_A_Hub_Labeling_Approach.pdf	Accepted version	766.21 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not 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	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Lin, X
dc.date	2022-05-09
dc.date.accessioned	2023-01-13T03:56:16Z
dc.date.available	2023-01-13T03:56:16Z
dc.date.issued	2022-01-01
dc.identifier.citation	Proceedings - International Conference on Data Engineering, 2022, 2022-May, pp. 512-524
dc.identifier.isbn	9781665408837
dc.identifier.issn	1084-4627
dc.identifier.uri	http://hdl.handle.net/10453/164959
dc.description.abstract	With the ever-increasing prevalence of graph data in a wide spectrum of applications, it becomes essential to analyze structural trends in dynamic graphs on a continual basis. The shortest cycle is a fundamental pattern in graph analytics. In this paper, we investigate the problem of shortest cycle counting for a given vertex in dynamic graphs in light of its applicability to problems such as fraud detection. To address such queries efficiently, we propose a 2-hop labeling based algorithm called Counting Shortest Cycle (CSC for short). Additionally, techniques for dynamically updating the CSC index are explored. Comprehensive experiments are conducted to demonstrate the efficiency and effectiveness of our method. In particular, CSC enables query evaluation in a few hundreds of microseconds for graphs with millions of edges, and improves query efficiency by two orders of magnitude when compared to the baseline solutions. Also, the update algorithm could efficiently cope with edge insertions (deletions).
dc.language	en
dc.publisher	IEEE
dc.relation	http://purl.org/au-research/grants/arc/DP210101393
dc.relation.ispartof	Proceedings - International Conference on Data Engineering
dc.relation.ispartof	2022 IEEE 38th International Conference on Data Engineering (ICDE)
dc.relation.isbasedon	10.1109/ICDE53745.2022.00043
dc.rights	info:eu-repo/semantics/closedAccess
dc.title	Towards Real-Time Counting Shortest Cycles on Dynamic Graphs: A Hub Labeling Approach
dc.type	Conference Proceeding
utslib.citation.volume	2022-May
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/Strength - AAII - Australian Artificial Intelligence Institute
utslib.copyright.status	closed_access	*
dc.date.updated	2023-01-13T03:56:15Z
pubs.finish-date	2022-05-12
pubs.publication-status	Published
pubs.start-date	2022-05-09
pubs.volume	2022-May

Abstract:

With the ever-increasing prevalence of graph data in a wide spectrum of applications, it becomes essential to analyze structural trends in dynamic graphs on a continual basis. The shortest cycle is a fundamental pattern in graph analytics. In this paper, we investigate the problem of shortest cycle counting for a given vertex in dynamic graphs in light of its applicability to problems such as fraud detection. To address such queries efficiently, we propose a 2-hop labeling based algorithm called Counting Shortest Cycle (CSC for short). Additionally, techniques for dynamically updating the CSC index are explored. Comprehensive experiments are conducted to demonstrate the efficiency and effectiveness of our method. In particular, CSC enables query evaluation in a few hundreds of microseconds for graphs with millions of edges, and improves query efficiency by two orders of magnitude when compared to the baseline solutions. Also, the update algorithm could efficiently cope with edge insertions (deletions).

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

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