频繁子图挖掘算法的应用分类

摘要：频繁子图挖掘属于数据挖掘领域的一部分，越来越受到研究学者的广泛应用，目前已经成功应用于生物学、化学、社会学等领域。频繁子图算法的操作是从给定的图数据库中，根据同构测试及支持度计算判断出频繁子图。本文整理出国内外学者基于频繁子图的应用文献。根据文献，对这些应用进行分类，列表整理出各个应用领域的数据集的开源地址和图的顶点及边的标识含义。

关键词：频繁子图挖掘;应用场景;顶点;边

中图分类号：TP311.12 文献标识码：A

文章编号：1009-3044（2020）29-0040-02

1 引言

在数据挖掘的领域中，频繁子图挖掘算法越来越受到国内外研究学者的关注。频繁子图将各种数据处理成顶点到顶点的逻辑关系的表示，在该模型[1]中，顶点和对应的边关系可以具有与它们相关联的标签，这些标签不是唯一的。使用这样的图表示，频繁模式的问题变成了在整个图上寻求频繁出现子图的问题，运用频繁子图算法挖掘其潜在的价值。频繁子图挖掘算法即在给定的图中根据设定的支持度阈值，寻找出同构子图大于等于给定支持度阈值的子图。频繁子图算法的发展历经二十年，基于频繁子图的应用也越来越广泛。

2 运用场景

在由顶点和边构成的图中，顶点有其分类的标识，边亦有其分类的标识，我们需要在给定的图数据库中寻找出顶点标识和标识对应一致的子图，计算出支持度，若一旦支持度超过给定的阈值，便输出其子图，其子图便是一个频繁子图。Lin W[2]等人认为频繁子图挖掘问题分为两个方面：在一个大图的不同区域挖掘子图适用于社交网络分析等领域;在大规模图集中挖掘子图适用于生物信息学和计算药理学等领域。图集上的挖掘是指在多张图的图数据库中挖掘这些图中共现的子图。在一张大图上的挖掘则是在一张图上挖掘图内出现的子图。基于图事务集合的频繁子图挖掘算法与基于单个大图的频繁子图挖掘算法不同，在计算候选子图支持度的时候，基于图事务集合的频繁子图挖掘算法只需要计算候选子图与图事务集合中满足子图同构的小图的个数，而基于单个大图的频繁子图挖掘算法需要在这个大图中找出候选子图所有的同构的子图，计算用同构的子图的候选子图支持度[3]。如表1所示，进行的应用分类。

（1）生物学

对多种分子和基因相互作用网络的研究来分析生物功能，其核心问题就发现网络的功能模块，其目的是了解生物系统如何在基本单元的基础上组织起来.并可以通过频繁子图挖掘算法产生一定的生物功能，为分析理解生命基本规律提供依据[23]。其中基因调控网络是有向图。

（2）化学

在化学领域中，不同种类的化合物往往含有一些关键子结构从而具有某一相同的性质，这些关键字结构共同决定这一相同性质。对于由具有某一相同性质的一类化合物组成的数据集，可以通过频繁子图挖掘算法找出频繁出现的关键子结构，然后利用这些关键子结构预测其他一些化合物是否也具有这样的相同性质[24]。

（3）社交网络

社交网络分析即用户关系分析，其含义是分析预测用户之间的态度即推测出社交网络中某个使用者对另一个使用者的潜在态度，研究得到的成果对社交网络非常重要，主要体现在应用价值方面，可以通过频繁子图挖掘算法挖掘出用户关系的关系模式，进而对社交网络中的用户提供个性化的推荐、辨认网络中异常的用户，产生全新的用户聚类。

（4）信息安全

信息安全方面包括恶意代码检测，可疑金融交易识别，软件缺陷检测等。通过恶意代码或缺陷代码或可疑特征数据库，通过频繁子图算法去匹配检测代码或者用户交易行为，进而标记出所有恶意代码或缺陷代码或可疑交易的出处。

（5）其他

在频繁子图的应用中，首先需要定义顶点与顶点之间的关系及顶点信息和边信息。根据图数据库，根据顶点标识和边标识挖掘频繁的关系模式。

本文根据应用方向的参考文献整理得到如下信息.如表2所示。

3 结论

本文结合国内外学者的文献，根据应用领域将这些文献进行分类，列表整理出各个应用领域的数据集的开源地址和图的顶点及边的标识含义。众多文献表明，随着大数据的兴起，频繁子图挖掘算法结合分布式框架越來越成为主流方式。

参考文献：

[1] Kuramochi M，Karypis G.Frequent subgraph discovery[Cl//Pro-ceedings 2001 IEEE International Conference on Data Min-ing.29Nov.-2 Dec.200l，Sanjose，CA，USA.lEEE，2001：313-320.

[2] Lin W Q.Efficient techniques for subgraph mining and queryprocessing[D]. Nanyang Technological University， 2015. DOl：10.32657/10356/62137.

[3]张天明.大图上频繁子图挖掘算法的研究[D].沈阳：东北大学。2014.

[4]谢均，尚学群，王淼，等.解决数据样本不平衡性的频繁子图挖掘算澍[J].计算机工程与应用，2008，44（36）：146-149.

[5] Mrzic A，Meysman P，Bittremieux W，et al.Grasping frequentsubgraph mining for bioinformatics applications[Jl. BioDataMining，2018，11（1）：1-24.

[6] Saha T K，Katebi A，Dhifli W，et aI.Discovery of functional mo-tifs from the interfaceregion of oligomeric proteins using fre-quent subgTaph mining[Jl.ACM Transactions on ComputationalBiology and Bioinformatics，2019，16（5）：1537-1549.

[7] Gawronski A R，Turcotte M.RiboFSM：Frequent subgraph min-ing for the discovery of RNA structures and interactions[Jl.BMC Bioinformatics，2014，15（13）：1-15.

[8]汪涛.基于频繁子图挖掘的细胞器通信模式研究[D].哈尔滨：哈尔滨工业大学，2014.

[9]屠黎阳，杜俊强，接标，等.基于判别性子图重构的轻微肝性脑病分类[J].模式识别与人工智能，2016，29（9）：832-839.

[10]高正康.频繁子图挖掘及其在化合物性质预测中的应用[Dl.兰州：兰州大学。2014.

[11] Inokuchi A，Washio T，Motoda H.Complete mining of frequentpatterns from graphs： mining graph data[J].Machine Learning，2003，50（3）：321-354.

[12]廖强，频繁子图挖掘算法及其在分类信息挖掘中的应用研究[D].宜昌：三峡大学，2012.

[13]朱鹏宇，鲍培明，吉根林.用户频繁通信关系的并行挖掘算法研究[J].计算机科学，2018，45 （2）：103-108.

[14]李龙洋，董一鸿，严玉良，等.Spark环境下基于频繁边的大规模单图采样算法[J].计算机研究与发展，2017，54（9）：1966-1978.

[15]许双.基于频繁子图挖掘的小群体社交网络用户关系分析[D].北京：北京邮电大学，2016.

[16] Fan M，Liu J，Luo X P，et al.Android malwarefamilial classifica-tion and representative sample selection via frequent subgraphanalysis[J].IEEE Transactions on Information Forensics and Se-curity，2018，13（8）：1890-1905.

[17]朱雪冰，周安民，左政，基于家族行为频繁子图挖掘的恶意代码检测[J].信息安全研究，2019，5 （2）：105-113.

[18]张成虎，尹为.基于数据流频繁子图挖掘的可疑金融交易动态识别[J].系统工程，2013，31（7）：1-7.

[19]雷珂，何威.基于数据挖掘技术的软件缺陷检测方法研究[J].电子世界，2012（15）：112-114.

[20] Petelin B，Kononenko I，Malaeie V，etaI.Frequent subgraph min-mg in oceanographic multi-level directed graphs[Jl.Internation-al Journal of Geographical Information Science，2019， 33（10）：1936-1959.

[21] Ta Chu W，Tsai M H.Visual pattern discovery for architectureimage classification and product image search[Cl//2012.

[22]肖飛，王悦，梅逸男，等，基于出行模式子图的城市功能区域发现方法[J].计算机科学，2018，45（12）：268-278.

[23]董安国.频繁子图挖掘算法及其在生物网络中的应用[D].西安：长安大学，2009.

[24]彭绍亮，牛琦，李肯立，等.CPU-MIC异构并行架构下基于大规模频繁子图挖掘的药物发现算法[J].大数据，2019，5（2）：89-103.

【通联编辑：梁书】

作者简介：吴成凤（1995-），女，安徽铜陵枞阳人，云南大学硕士在读，主要研究方向为数据挖掘。