崔景洋

(河北地質大學 信息工程學院，河北 石家莊 050031)

0 引言

一般來說，圖數(shù)據是指以圖形為對象的形式化表示，包括點、線、面等屬性，是一種常見的數(shù)據結構，主要用以表示事物之間的聯(lián)系、結構等.相較之傳統(tǒng)數(shù)據結構而言，圖數(shù)據是復雜的.這種復雜表現(xiàn)在處理圖數(shù)據過程中的各個方面.存儲方面，由于圖中邊的數(shù)量與點的數(shù)量成指數(shù)級的關系，再加上大數(shù)據時代的來臨，頂點以及邊的規(guī)模都變得越來越大，就為圖數(shù)據的存儲提出了新的挑戰(zhàn).計算方面，傳統(tǒng)分類聚類等數(shù)據挖掘算法主要是針對簡單類型數(shù)據進行挖掘，圖的特殊性使得普通算法難以應對如此錯綜復雜的圖內頂點之間的關系.這就使得對于圖挖掘算法的需求變得越來越迫切.

在社交網絡(social networks)中，其頂點表示人，邊表示人與人之間的關系[1].對于社交網絡，可以通過圖聚類算法來進行交際圈的劃分，以形成準確的用戶畫像，來輔助企業(yè)的戰(zhàn)略決策[2].在生物學信息中，圖數(shù)據可以用來表示蛋白質交互網絡(protein-protein interaction，PPI)，通過挖掘實驗得到的PPI網絡[3]，可以使得生物科學家很清晰地認識某種蛋白質結構且不用耗費大量人力財力進行測定實驗.

根據圖數(shù)據的性質進行圖數(shù)據挖掘的研究，無論是在科學研究上還是生產生活中，都有比較大的意義.尤其在信息高速產出的今天，對于事物之間錯綜復雜關系的總結，有利于我們從宏觀上對于事物進行更加細致的掌握.

1 圖挖掘的主要研究內容

圖挖掘這一領域很難用一個時間點來明確圖挖掘研究的提出.近幾年，國內外學者對于圖挖掘領域的研究成果層出不窮.一些新概念、新技術例如機器學習、并行化計算等新方法也被應用到了圖數(shù)據的分析過程之中.下面介紹幾類比較重要的圖數(shù)據挖掘方法.

1.1 圖分類

無論是對于圖的研究還是在計算機領域的其他研究中，分類算法都占有比較大的比重.圖的分類是根據圖結構的相似程度分別歸類.目前，圖分類的方法主要包括基于圖頻繁結構及基于圖核函數(shù)的分類方法.

基于圖頻繁結構的方法主要包含三個主要步驟：首先將圖分類問題轉化為頻繁子圖求解問題，通過挖掘得到頻繁子圖，第二步是選擇頻繁子圖中的分類特征，最后通過第二步所選取的特征構建分類模型[4].值得注意的是，選取的分類特征不同，對于分類的結果也有一定的影響.王海榮[5]考慮到了這個問題，提出了一種通過加權法提取頻繁子圖的算法，并將之應用到了文本分類的過程中.

圖核是通過核函數(shù)的方法，將圖映射到高維空間.低維線性不可分的圖在更高維度就會變得可分.不過，映射到高維空間后勢必會增加計算量，但是核函數(shù)可以代替高維計算結果，往往可以減小計算量以降低計算時間.所以這種分類方法的難點在于圖核函數(shù)的選取.主流的圖核函數(shù)選取方法有兩種：一種是基于游走的圖核[6]，另一種是基于循環(huán)的圖核[7].王桂娟等[8]對圖內在結構進行分析，通過機器學習的方法對圖進行分類.

1.2 圖聚類

圖的聚類分析在目前的研究現(xiàn)狀中，主要包含兩個方向.第一個方向是在一個圖內進行頂點或邊的聚類，第二個方向是在多個圖中進行圖與圖之間的相似性歸納.

圖內頂點聚類是將圖中聯(lián)系密切的頂點及其相關邊組成一個子圖的過程[9]，聚類的任務就是要從大圖中找出那些相似的頂點.另一方面，對于若干小圖來說，圖之間的距離就可以根據結構相似性函數(shù)來衡量.高陽等[10]使用拉普拉斯矩陣和譜聚類方法對于圖數(shù)據進行聚類，將NP難的問題轉化為了多項式時間算法.

1.3 頻繁子圖挖掘

頻繁子圖問題就是找出在某一圖結構中頻繁出現(xiàn)的子圖結構，并將這些頻繁子圖結構用到分類、聚類、搜索等方面.傳統(tǒng)查找頻繁項集的方法例如Apriori,FP-Growth算法等在頻繁子圖求解時也是適用的.單曉歡等[11]提出了一種標簽約束的頻繁子圖Top-k查詢方法.另外，針對當前形勢下的大數(shù)據量的問題，通常的解決方式是將頻繁子圖挖掘問題進行并行化以加快處理速度[12,13].

1.4 圖關鍵詞查詢

圖中數(shù)據關鍵字查詢的主要難點在于圖的遍歷和檢索[14]，查詢的可以是圖的結構，也可以是頂點或者邊的屬性.按照其返回結果的不同，可以分成兩類：一類返回的是關鍵詞位置，另外一類返回的是關鍵詞的結構.一般的處理過程是根據遍歷索引的方法定位關鍵詞所在的位置，并記錄搜索結果后，根據一定的排序策略將結果展現(xiàn)給用戶[15].

1.5 圖匹配

圖的一個匹配就是一個圖中若干沒有端點的邊的集合，最大匹配就是求這個邊集最大有多少條邊.圖匹配技術可以作為圖數(shù)據查詢的一種重要技術手段，一般分為精確圖匹配以及非精確圖匹配[16].大部分情況下需要一種可以接受錯誤和忍耐噪聲的一種算法來解決實際生活中遇到的問題.所以可以通過定義一種距離，來評價圖與圖之間的相似程度[17].

2 圖挖掘應用的發(fā)展趨勢

2.1 社交網絡挖掘

近幾年，互聯(lián)網發(fā)展迅猛.越來越多的人們選擇將互聯(lián)網作為一種社交手段.在此背景下，對于社交網絡的研究層出不窮.對社交網絡進行分析，可以看做是上述圖數(shù)據挖掘研究內容的一個融合性應用.陳克寒等[18]提出了一種基于用戶聚類的社交網絡推薦方法.根據用戶與用戶之間的關系將其進行聚類分析，并跟據聚類的結果構架了一個基于用戶主題的推薦系統(tǒng).周方[19]將圖分類技術應用于社交網絡，通過標記社交網絡中節(jié)點的形式，來進行社交網絡的社會學分析.張青[20]設計了一種基于信息熵傳傳播模型的子圖查詢方法，該方法在大數(shù)據量時有著更高的效率.

2.2 學術網絡挖掘

對于學術網絡的研究相較之社交網絡而言，無論是從數(shù)量上還是質量上都是遠遠達不到的.但是2008年開始，我國授予博士學位的人數(shù)就超過了美國，成為了世界上每年授予博士學位人數(shù)最多的國家.同時，我國學者僅在2015年一年發(fā)表的論文數(shù)量就高達百萬篇[21].學術網絡可以加強學者之間的交流，對于知識共享、思維方式等方面的推動有著不小的作用.劉萍等[22]根據文獻間的引用關系對于學者學術影響力進行了研究，通過學者文獻影響力測度新指標為圖書情報學(LIS)領域的初學者提供了一個清晰明確的學習方向.

2.3 圖數(shù)據庫

許多新興計算框架的出現(xiàn)，使得傳統(tǒng)圖數(shù)據的計算不得不考慮移植問題，開始有專門針對圖數(shù)據優(yōu)化的數(shù)據庫產生，例如：Neo4j[23],Graphchi[24]等.也有針對圖的計算框架產生，例如Spark平臺的圖計算包——GraphX.邱勝海等[25]利用 Neo4j提出了一種云計算環(huán)境中的圖數(shù)據庫建模方法.

3 總結

當今時代是大數(shù)據時代，數(shù)據量的急劇增加與圖結構的復雜相結合將導致對于圖的計算將變得越來越復雜，這就為圖數(shù)據挖掘提出了如下要求：

1)圖數(shù)據存儲.傳統(tǒng)方式方法對于解決大數(shù)據的問題已經顯得力不從心，那么是否能夠出現(xiàn)一種新型的數(shù)據結構來存儲圖數(shù)據，以方便計算以及與其他設備或者節(jié)點間的通信.

2)圖數(shù)據計算.對于圖數(shù)據的計算都需要反復迭代，這將耗費巨大的計算資源.目前主流算法都是針對規(guī)模較小的圖數(shù)據所設計的內存算法，但是在現(xiàn)實生活中，圖數(shù)據往往都是海量的儲存在硬盤或者集群之中的數(shù)據.

3)實時性.在線實時處理業(yè)務的迅猛成長為大數(shù)據量的圖數(shù)據流的解決方法提供了一個廣闊的發(fā)展前景.例如在社交網絡中的節(jié)點往往是動態(tài)變化的，而且由于這些數(shù)據不能離線存儲，那么就要求我們去尋求針對圖數(shù)據流的處理方法.

由于數(shù)據的不確定性是普遍存在的，而目前的主流算法解決的都是確定圖的數(shù)據挖掘，如何將圖的不確定性與已經解決的確定圖問題建立聯(lián)系也為研究人員提供了一個新的發(fā)展方向.