论文标题
在动态图上实时计数最短周期：集线器标签方法
Towards Real-Time Counting Shortest Cycles on Dynamic Graphs: A Hub Labeling Approach
论文作者
论文摘要
随着图形数据在广泛的应用中的越来越多的流行率，必须持续分析动态图中的结构趋势至关重要。最短的周期是图分析中的基本模式。在本文中，我们研究了在动态图中给定顶点的最短周期计数问题，鉴于其对诸如欺诈检测等问题的适用性。为了有效地解决此类查询，我们提出了一种基于2-HOP标记的算法，称为最短周期（简称CSC）。此外，还探索了用于动态更新CSC索引的技术。进行全面的实验以证明我们方法的效率和有效性。特别是，CSC可以在数百微秒内对具有数百万边的图表进行查询评估，并且与基线溶液相比，查询效率提高了两个数量级。此外，更新算法可以有效地应对边缘插入（删除）。
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).
