Approximate cycle mining algorithm for large graphs
CSTR:
Author:
Affiliation:

School of Computer and Information Engineering, Henan University of Economics and Law, Zhengzhou 450046, P. R. China

Clc Number:

Fund Project:

Supported by National Natural Science Foundation of China (61702161), Key Research Fund for Higher Education of He’nan Province (24A520001), Key Research and Development and Promotion Program of He’nan Province (252102210128), Natural Science Foundation of Henan (262300420290), “Dual-Leader” Faculty Party Branch Secretary Studios Project of Henan Provincial Education Working Committee (2025-09), Henan University of Economics and Law University-Level Research Project (Cultivation Project for National General Program)(24HNCDXJ54).

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    Cycle mining can help people deeply understand the structure and function of complex networks, which is of great significance for practical application fields such as road traffic networks, bioprotein networks, financial and economic networks, etc. However, the massive data in the information age makes cycle mining extremely challenging. In response to the problem of large data volumes but relatively 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 forward and backward searches on the dataset based on hotpoints to obtain hotpoints and their neighbors, and use this to construct an index (H-Index); finally, calculate the tightness coefficient and average tightness coefficient between different vertices based on H-Index, the path between vertex pairs with a tightness coefficient greater than the average tightness coefficient is an approximate cycle. The IACD algorithm has been optimized in two aspects based on the ACD algorithm. On the one hand, it increases the deduplication 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 construction of indexes. The experimental data used are all real 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.

    Reference
    Related
    Cited by
Get Citation

姜涛,刘笑婷,徐上钦,高舒乐,王健.面向大图的近似环挖掘算法[J].重庆大学学报,2026,49(4):117~134

Copy
Related Videos

Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:December 11,2023
  • Revised:
  • Adopted:
  • Online: April 21,2026
  • Published:
Article QR Code