基于强连通分量的最短环计数索引  

Index for Counting the Shortest Cycle Based on Strongly Connected Components

作　　者：杨迎 周军锋 杜明[1] YANG Ying;ZHOU Junfeng;DU Ming(School of Computer Science and Technology,Donghua University,Shanghai 201600,China)

机构地区：[1]东华大学计算机科学与技术学院,上海201600

出　　处：《计算机科学》2025年第4期169-176,共8页Computer Science

基　　金：国家自然科学基金(62372101,61873337,62272097)。

摘　　要：最短环计数是图分析的一种基本模式。经过某个顶点的最短环计数指经过该顶点且长度最短的环的数目。在现实生活中,最短环计数应用十分广泛,如欺诈交易检测、罪犯预筛选以及文件共享优化等。针对现有方法索引空间较大、查询效率较低等问题,研究如何在原始图上构建最短环计数索引,提出了一种针对最短环计数且无需进行图转换操作的STC索引(Trough Shortest Cycle Counting Index)。该索引根据最短环的特征对其进行分类,针对不同类型的最短环分别构建不同的索引信息,能够直接基于原始图构造索引,并且在保证索引规模不扩大、索引构造时间不增加的前提下,进一步提升查询效率。此外,根据环与强连通分量的特殊关系,提出了基于强连通分量的索引策略,通过在强连通分量内部构造最短环计数索引,可以进一步提升索引构造效率,有效减小索引规模,提升查询效率。在10个真实数据集上进行了实验。实验结果验证了所提出的STC索引的高效性,以及基于强连通分量的策略可以有效减小索引空间,提升索引构造以及查询效率。The shortest cycle counting is a basic pattern of graph analysis.The shortest cycle counting through a certain vertex refers to the number of shortest cycles passing through the vertex.In real life,the shortest cycle counting has a wide range of applications,such as fraudulent transaction detection,criminal pre-screening,and file sharing optimization.In response to the problems of large indexing space and low query efficiency of existing methods,this paper studies the construction of shortest cycle counting indexing on the original graph,and proposes a trough shortest cycle counting index(STC index)that does not require graph transformation operations.The index classifies the shortest cycles according to their characteristics,constructs different indexing information for different types of shortest cycles,and can directly construct indexes based on the original graph,and further improve query efficiency while ensuring that the indexing size does not expand and the indexing construction time does not increase.In addition,based on the special relationship between cycles and strongly connected components,this paper proposes an indexing strategy based on strongly connected components.By constructing shortest cycle counting indexing within strongly connected components,it can further improve the efficiency of indexing construction,effectively reduce the index size,and improve query efficiency.Experiments on 10 real datasets verify the efficiency of the proposed STC index and the strategy based on strongly connected components,which can effectively reduce the indexing space and improve the efficiency of indexing construction and querying.

关 键 词：图分析 最短环 最短环计数 2-hop索引 强连通分量 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]