计算机科学 ›› 2026, Vol. 53 ›› Issue (5): 137-148.doi: 10.11896/jsjkx.250400006
李天琪, 杜明, 周军锋
LI Tianqi, DU Ming, ZHOU Junfeng
摘要： 最短环计数是对数据图进行分析的重要途径之一,在关键节点识别、周期结构分析和异常检测等领域具有重要应用。然而,在时态图分析中,受边的时效性和查询时间窗口变化的影响,现有方法难以高效支持不同时间窗口下的最短环计数。对此,首先提出基于索引的方案来提升最短环计数的效率,然后提出优化的索引构建策略来降低索引规模,提升索引构建效率,从而在保证索引规模和构建时间的前提下,支持高效的查询处理。最后,在真实世界的时态图上进行了实验,实验结果表明,所提出的方法能够高效构建索引并快速回答给定查询顶点在查询窗口内的最短环数量和长度。
中图分类号:
| [1]ZHANG Y,YU J X.Hub labeling for shortest path counting[C]//Proceedings of the 2020 ACM SIGMOD International Confe-rence on Management of Data.2020:1813-1828. [2]WANG Y,YUAN L,CHEN Z,et al.Towards efficient shortest path counting on billion-scale graphs[C]//2023 IEEE 39th International Conference on Data Engineering(ICDE).IEEE,2023:2579-2592. [3]PENG Y,YU J X,WANG S.PSPC:efficient parallel shortest path counting on large-scale graphs[C]//2023 IEEE 39th International Conference on Data Engineering(ICDE).IEEE,2023:896-908. [4]QIU X,CEN W,QIAN Z,et al.Real-time constrained cycle detection in large dynamic graphs[C]//Proceedings of the VLDB Endowment.2018:1876-1888. [5]LI C,KYNG R,LIU Y P,et al.Almost-Linear Time Algorithms for Incremental Graphs:Cycle Detection,SCCs,s-t Shortest Path,and Minimum-Cost Flow[C]//Proceedings of the 56th Annual ACM Symposium on Theory of Computing.2024:1165-1173. [6]JIN X X,ZHANG Y,LI L,et al.Robust PCA-Based Abnormal Traffic Flow Pattern Isolation and Loop Detector Fault Detection[J].Tsinghua Science and Technology,2008,13(6):829-835. [7]HOLME P,SARAMAKI J.Temporal Networks[J].PhysicsReports,2012,519(3):97-125. [8]JIANG Z H.Frequent Evolution Pattern Mining in Temporal Networks[J].Modern Computer(Professional Edition),2019,638(2):17-21. [9]YANG Y,YAN D,WU H,et al.Diversified Temporal Subgraph Pattern Mining[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2016:1965-1974. [10]MA S,HU R,WANG L,et al.Fast Computation of Dense Temporal Subgraphs[C]//2017 IEEE 33rd International Conference on Data Engineering(ICDE).IEEE,2017:361-372. [11]AKHTAR N,AHAMAD M V.Graph Tools for Social Network Analysis[M]//Research Anthology on Digital Transformation,Organizational Change,and the Impact of Remote Work.IGI Global,2021:485-500. [12]SCHWEIMER C.Fast generation of simple directed social network graphs with reciprocal edges and high clustering[J].Social Network Analysis and Mining,2022,12(1):1-5. [13]HAJDU L,KRÉSZ M.Temporal Network Analytics for Fraud Detection in the Banking Sector[C]//ADBIS,TPDL and EDA 2020 Common Workshops and Doctoral Consortium.2020:145-157. [14]LYU X,ZHENG S,LI Z,et al.Application of graph databases in the communication and information asset management in power grid[C]//2016 International Conference on Automotive Engineering,Mechanical and Electrical Engineering(AEMEE 2016).2017:1-2. [15]FENG Q,PENG Y,ZHANG W,et al.Towards real-time coun-ting shortest cycles on dynamic graphs:A hub labelingapproach[C]//2022 IEEE 38th International Conference on Data Engineering(ICDE).IEEE,2022:512-524. [16]YANG Y,ZHOU J F,DU M.Shortest Cycle Counting Index Based on Strongly Connected Components[J].Computer Science,2025,52(4):169-176. [17]FENG Q,PENG Y,ZHANG W,et al.DSPC:Efficiently An-swering Shortest Path Counting on Dynamic Graphs[J].arXiv:2307.05918,2023. [18]KUMAR R,CALDERS T.Finding simple temporal cycles in an interaction network[EB/OL].https://ceur-ws.org/Vol-1929/paper2.pdf. [19]KUMAR R,CALDERS T.2SCENT:An efficient algorithm for enumerating all simple temporal cycles[J].Proceedings of the VLDB Endowment,2018,11(11):1441-1453. [20]PAN M J,LI R H,ZHAO Y H,et al.Fast Cycle Enumeration Algorithm for Temporal Graph Data[J].Journal of Software,2020,31(12):3823-3835. [21]XIN C,SHI J M,YOU P,et al.Minimum Strongly Connected Subgraph Collection in Dynamic Graphs[J].Proceedings of the VLDB Endowment,2024,17(6):1324-1336. [22]TARJAN R.Depth-first search and linear graph algorithms[C]//12th Annual Symposium on Switching and Automata Theory.1971:114-121. |
|
||
首页