面向大图的近似环挖掘算法
Approximate cycle mining algorithm for large graphs
摘要
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.关键词
图数据挖掘/大型有向图/近似环/索引/可达Key words
graph data mining/large directed graph/approximate cycle/index/reachable分类
信息技术与安全科学引用本文复制引用
姜涛,刘笑婷,徐上钦,高舒乐,王健..面向大图的近似环挖掘算法[J].重庆大学学报,2026,49(4):117-134,18.基金项目
国家自然科学基金资助项目(61702161) （61702161）
河南省高等学校重点科研项目(24A520001) （24A520001）
河南省重点研发与推广专项(科技攻关)(252102210128) （科技攻关）
河南省自然科学基金(262300420290) （262300420290）
中共河南省委教育工委高校"双带头人"教师党支部书记工作室建设项目(2025-09) （2025-09）
河南财经政法大学校级研究课题(国家一般项目培育项目)(24HNCDXJ54). 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). （国家一般项目培育项目）
