面向大图的近似环挖掘算法

打开文本图片集

中图分类号：TP399 文献标志码：A 文章编号：1000-582X（2026）04-117-18

Approximate cycle mining algorithm for large graphs

JIANG Tao，LIU Xiaoting，XU Shangqin，GAO Shule，WANG Jian （School ofComputer and Information Engineering，Henan University of Economics and Law， Zhengzhou ，P.R. China）

Abstract： Cycle mining can help people deeplyunderstand the structure and functionofcomplex networks，whichis ofgreat significance forpracticalapplicationfieldssuchasroadtraffc networks，bioproteinnetworks，financial and economic networks，etc.However，the massve data in the information age makes cycle mining extremely challenging.In response to the problem of large data volumesbutrelatively limited available data that cannot mine complete cycles，the concept of approximate cycle （AC）is defined，and the approximate cycle detection algorithm （ACD）and its optimization algorithm （IACD）are proposed.Both algorithms are divided into three stages：first，calculate hotpoints through vertex degree calculation;secondly，perform forwardand backward searches on the dataset based on hotpoints to obtain hotpoints and their neighbors，anduse this to construct an index （H-Index）；finally，calculate the tightness coeficientand average tightness coefficient between different vertices based on H-Index，the path between vertex pairs with a tightness coeficient greater than the average tightness coeffcient is an approximatecycle.The IACD algorithm has been optimized in two aspects based onthe ACD algorithm.On theone hand，it increases thededuplication of vertices in the acquisition of hotpoints and their neighbors，while reducing the number of searches for data.On the other hand，it uses function vectorization instead of cyclic modification in the constructionof indexes.The experimental data used are allreal datasets of SNAP public website.The experimental results show that both algorithms can run smoothly on larger datasets and have good scalability and efficiency. The efficiency of the IACD algorithm is about 25% higher than that of the ACD algorithm.

Keywords： graph data mining; large directed graph; approximate cycle; index; reachable

在现实世界中，一个实体常常可以通过忽略其中的各种复杂细节，简化为图模型中的一个节点。（剩余17724字）