頻繁子圖挖掘算法的應用分類

摘要：頻繁子圖挖掘屬于數據挖掘領域的一部分，越來越受到研究學者的廣泛應用，目前已經成功應用于生物學、化學、社會學等領域。頻繁子圖算法的操作是從給定的圖數據庫中，根據同構測試及支持度計算判斷出頻繁子圖。本文整理出國內外學者基于頻繁子圖的應用文獻。根據文獻，對這些應用進行分類，列表整理出各個應用領域的數據集的開源地址和圖的頂點及邊的標識含義。

關鍵詞：頻繁子圖挖掘;應用場景;頂點;邊

中圖分類號：TP311.12 文獻標識碼：A

文章編號：1009-3044（2020）29-0040-02

1 引言

在數據挖掘的領域中，頻繁子圖挖掘算法越來越受到國內外研究學者的關注。頻繁子圖將各種數據處理成頂點到頂點的邏輯關系的表示，在該模型[1]中，頂點和對應的邊關系可以具有與它們相關聯的標簽，這些標簽不是唯一的。使用這樣的圖表示，頻繁模式的問題變成了在整個圖上尋求頻繁出現子圖的問題，運用頻繁子圖算法挖掘其潛在的價值。頻繁子圖挖掘算法即在給定的圖中根據設定的支持度閾值，尋找出同構子圖大于等于給定支持度閾值的子圖。頻繁子圖算法的發(fā)展歷經二十年，基于頻繁子圖的應用也越來越廣泛。

2 運用場景

在由頂點和邊構成的圖中，頂點有其分類的標識，邊亦有其分類的標識，我們需要在給定的圖數據庫中尋找出頂點標識和標識對應一致的子圖，計算出支持度，若一旦支持度超過給定的閾值，便輸出其子圖，其子圖便是一個頻繁子圖。Lin W[2]等人認為頻繁子圖挖掘問題分為兩個方面：在一個大圖的不同區(qū)域挖掘子圖適用于社交網絡分析等領域;在大規(guī)模圖集中挖掘子圖適用于生物信息學和計算藥理學等領域。圖集上的挖掘是指在多張圖的圖數據庫中挖掘這些圖中共現的子圖。在一張大圖上的挖掘則是在一張圖上挖掘圖內出現的子圖?；趫D事務集合的頻繁子圖挖掘算法與基于單個大圖的頻繁子圖挖掘算法不同，在計算候選子圖支持度的時候，基于圖事務集合的頻繁子圖挖掘算法只需要計算候選子圖與圖事務集合中滿足子圖同構的小圖的個數，而基于單個大圖的頻繁子圖挖掘算法需要在這個大圖中找出候選子圖所有的同構的子圖，計算用同構的子圖的候選子圖支持度[3]。如表1所示，進行的應用分類。

（1）生物學

對多種分子和基因相互作用網絡的研究來分析生物功能，其核心問題就發(fā)現網絡的功能模塊，其目的是了解生物系統如何在基本單元的基礎上組織起來.并可以通過頻繁子圖挖掘算法產生一定的生物功能，為分析理解生命基本規(guī)律提供依據[23]。其中基因調控網絡是有向圖。

（2）化學

在化學領域中，不同種類的化合物往往含有一些關鍵子結構從而具有某一相同的性質，這些關鍵字結構共同決定這一相同性質。對于由具有某一相同性質的一類化合物組成的數據集，可以通過頻繁子圖挖掘算法找出頻繁出現的關鍵子結構，然后利用這些關鍵子結構預測其他一些化合物是否也具有這樣的相同性質[24]。

（3）社交網絡

社交網絡分析即用戶關系分析，其含義是分析預測用戶之間的態(tài)度即推測出社交網絡中某個使用者對另一個使用者的潛在態(tài)度，研究得到的成果對社交網絡非常重要，主要體現在應用價值方面，可以通過頻繁子圖挖掘算法挖掘出用戶關系的關系模式，進而對社交網絡中的用戶提供個性化的推薦、辨認網絡中異常的用戶，產生全新的用戶聚類。

（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]張?zhí)烀?大圖上頻繁子圖挖掘算法的研究[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].哈爾濱：哈爾濱工業(yè)大學，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環(huán)境下基于頻繁邊的大規(guī)模單圖采樣算法[J].計算機研究與發(fā)展，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]張成虎，尹為.基于數據流頻繁子圖挖掘的可疑金融交易動態(tài)識別[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]肖飛，王悅，梅逸男，等，基于出行模式子圖的城市功能區(qū)域發(fā)現方法[J].計算機科學，2018，45（12）：268-278.

[23]董安國.頻繁子圖挖掘算法及其在生物網絡中的應用[D].西安：長安大學，2009.

[24]彭紹亮，牛琦，李肯立，等.CPU-MIC異構并行架構下基于大規(guī)模頻繁子圖挖掘的藥物發(fā)現算法[J].大數據，2019，5（2）：89-103.

【通聯編輯：梁書】

作者簡介：吳成鳳（1995-），女，安徽銅陵樅陽人，云南大學碩士在讀，主要研究方向為數據挖掘。