一种高效的大规模图数据频繁子图挖掘算法.docxVIP

中国科技论文在线 一种高效的大规模图数据频繁子图挖掘算 法 靳思萌，李仲伟，解晓芳，张海威 5 （南开大学计算机与控制工程学院，天津，300071） 摘要：随着计算机技术的发展和互联网应用的普及，各个领域可获取的数据呈爆炸式增长的趋势。图作为一种常用的数据表示模型，能够表达更复杂的结构模式和更一般性的语义信息，因此与大图数据相关的技术正在成为研究热点。频繁子图挖掘是图数据管理与分析的重要方 法之一，其任务是根据支持度找到输入图数据中频繁出现的子图。随着图数据规模的不断增大，传统面向图集的算法无法直接应用于像社会网络或 web 结构这样复杂的单图中。针对上述问题，本文提出了一种频繁子图挖掘算法——KFSM 算法，能够在大规模单图数据中快速挖掘出所需的频繁子图。KFSM 算法首先挖掘出一棵极大频繁树，然后基于极大频繁树挖掘出频繁子树，并通过添加频繁边，最终得到频繁子图。算法采用了一种可压缩的树形结构 来记录子图及其实例，将复杂的子图同构测试简化为一步邻居计数操作，极大地减少了挖掘时间，同时节约了存储空间。另外，KFSM 算法通过限制频繁子图的顶点个数，确保用户能够高效地挖掘所需的频繁子图，避免了大量不必要的时间代价。在模拟数据集和真实数据集中进行实验的结果表明，与已有算法相比，当输入图数据规模越大、复杂程度越高时，KFSM 算法能够在更短时间内挖掘出更大更丰富多样的频繁子图。如果进一步放宽最小支持度和最 大顶点数的限定条件，KFSM 算法在效率方面的优势将会更加显著。 关键词：图数据; 频繁子图挖掘; 单图; 启发式算法 中图分类号：请查阅《中国图书馆分类法》 An Efficient Algorithm for Mining Frequent Subgraphs on a 25 Large Single Graph JIN Simeng, LI Zhongwei, XIE Xiaofang, ZHANG Haiwei (College of Computer amd Control Engineering, Nankai University, Tianjin, 300071) Abstract: With the continuous development of computer technology and rapidly growth of Internet application, obtained data from various fields show an explosive trend. As a commonly used abstract data structure, graph has a more complex and general representation ability in both structure and semantic aspects. Therefore, the technology related with big graph data is becoming the research hotspot. Frequent subgraphs mining is an important basic operation on the graph, whose task is to find subgraphs that appear frequently on input graph according to support. More and more applications require mining frequent subgraphs on a large single graph with the increasing scale of graph, but traditional algorithms oriented a set of small graphs can’t be directly applied to complex single graph, such as the social network or web structure data. This paper proposes an algorithm called KFSM, which can fast mining demand frequent subgraphs on the large-scale single graph. KFSM algorithm first dig out a maximum frequent tree, then mining frequent subtrees on it, an