原文鏈接：https://blog.csdn.net/qq_41653753/article/details/79112436

原文鏈接：https://blog.csdn.net/weidai00/article/details/85245217

一、基本概念

1、圖挖掘

近年來，圖挖掘作為，數據挖掘的重要組成部分引起了社會各界的極大關注。圖挖掘（Graph Mining）是指利用圖模型從海量數據中發現和提起有用知識和信息的過程。通過圖挖掘所獲取的知識和信息已廣泛應用于各種領域，如商務管理、市場分析、生產控制、科學探索和工程設計。

2、圖在不同領域的應用

應用?? ?圖形?? ?頂點?? ?邊
生物信息學
（蛋白質結構分析、基因組織識別）?? ?蛋白質結構?? ?氨基酸?? ?接觸殘基
社交網絡
（實體間的聯系）?? ?社會關系網絡結構?? ?個體或組合?? ?依賴關系
Web分析
（Web連接結構分析、Web內容挖掘、
Web日志搜索）?? ?Web瀏覽模式?? ?Web頁面?? ?頁面之間的超鏈接
網絡計算?? ?計算機網絡?? ?計算機和服務器?? ?機器之間的互聯
3、難點
（1）圖邊的數量是頂點數量的指數倍。而具有規模大于109頂點和邊數量的圖數據愈來愈普遍，對查找和存儲提出了很大的挑戰；

（2）圖同構問題一般認為不是P問題也不是NPC問題，雖然它明顯是一個NP問題。判斷來年改革大圖是否同構非常困難。而同構的概念卻大量用在相關圖挖掘算法中；

（3）由于圖的復雜性，使得圖挖掘具有較高的復雜性，基于圖的算法很難進行并行化；

（4）很多傳統數據挖掘算法無法應用到圖數據中需要重新設計合適的算法。由于圖結構的復雜性，算法的設計要修高效性，并且對實驗機器的配置要求較高。

4、圖挖掘的基礎研究

（1）圖的匹配

（2）圖數據中的關鍵字查詢

（3）頻繁子圖挖掘：

Apriori-based 方法：包括AGM，AcGM，FSG和path-join算法等

FP-growth方法：包括gSpan、CloseGraph和FFSM等（它們主要通過逐漸擴展頻繁邊得到頻繁子圖，但對邊的擴展過程略有不同）

其他的頻繁子圖挖掘算法：例如Wang等人提出了一種基于索引的頻繁子圖挖掘算法GraphMiner；Zhu等人提出了一種基于用戶約束條件的頻繁子圖挖掘短發gPrune；Karste等人提出了適合于動態圖挖掘DynamicGREW算法等。

（4）顯著性子圖挖掘

（5）密集子圖挖掘

（4）圖的聚類

（5）圖的分類

（6）不確定圖的挖掘

（7）社會網絡應用的連接分析（link analysis）
基于連接的對象分類（Link based object classification）；

對象類型預測（object type predication）；

連接類型預測（link type predication）；

預測鏈路擴展（predicate link extension）；

組探測（Group detection）；

元數據挖掘（metadata mining）。

（7）隱私保護

（8）生物信息學

（9）化學圖數據

?

二、gSpan

為了遍歷圖，gSpan算法采用深度優先搜索。初始，隨機選擇一個起始頂點，并且對圖中訪問過的頂點做標記。被訪問過的頂點集合反復擴展，直到建立一個完全的深度優先搜索 (DFS) 樹。（圖中加粗的邊）
如下圖所示：

基于邊序，如果用5元組(i ,j ,L(i), L(i,j), L(j)) 表示邊，其中 L(j) 和 L(i)
分別是 v(i) 和 v(j) 的標記，而 L(i,j) 是連接它們的邊的標記, 則

?

gSpan最右路徑擴展規則

給定圖G 和G 的DFS樹T ，一條新邊e 可以添加到最右節點和最右路徑上另一個節點之間（后向擴展）；或者可以引進一個新的節點并且連接到最右路徑上的節點（前向擴展）。由于這兩種擴展都發生在最右路徑上，因此稱為最右擴展。 （黑點為最右路徑）第一優先級始終是將當前結束頂點鏈接回第一個頂點（標記為0的頂點）。如果那是不可能的，我們看看是否可以將它鏈接回第二個頂點（標記為1的頂點）。如果我們有一個更大的子圖，我們將繼續嘗試鏈接到第3，第4等，如果可能的話。如果這些都不可能，那么我們的下一個（第三個）優先級是從我們所處的頂點（上面標記為4）增長，并使鏈長得更長。如果這不起作用，我們回到父節點，再退一步，然后嘗試從那里開始增長（圖（e））。如果這不起作用，那么我們再向上邁出一步，并嘗試從那里成長（下面的第五個例子）。

gSpan偽代碼

實例

步驟一：圖里共有有7個alpha（α）頂點，8個beta（β）頂點和14個lambda（λ）頂點。有15個邊緣為純藍色，13個為雙紅色，8個為綠色點綴。現在我們已經有了這些計數，我們需要將頂點和邊的原始標簽排序成一個代碼，這將有助于我們稍后對搜索進行優先級排序。為此，我們創建一個代碼，該代碼以具有最高計數的頂點和邊開始降序排列標號。

我們首先查看各個邊（例如A，b，A），看看它們是否滿足此最小支持閾值。我將從查看頂部的第一個圖表開始。有一個邊是（B，a，C），我需要計算有多少圖有這樣的邊。我可以在第一張圖，第二張圖，第三張圖和第四張圖中找到它，因此它支持4; 我們會保留那一個。還要注意我可以選擇將該邊寫為（C，a，B），但是選擇用B作為起始頂點來編寫它，因為我們在上面建立了它的順序。我們繼續前進并檢查（A，a，C）并發現它只能在第一個圖中找到; 它被丟棄了。我們檢查（A，c，C）并在前4個圖中找到它; 收下

我們基于優先級規則的下一步是嘗試將頂點3（‘C’）鏈接到根或’A’。我們可以選擇的唯一常用邊是（C，c，A）。

這僅存在于我們的一個圖表中，因此我們將進入下一個增長優先級。由于在頂點3處的’C’與’B’和頂點1之間已經存在鏈接，因此第二優先級不是一個選項，因此我們嘗試再次從頂點3處的’C’增長/延伸。我們可以添加（C，a，B）或（C，c，A）。添加（C，a，B）看起來像這樣

我們嘗試添加（C，c，A）。但在我們留下的任何圖表中都找不到它。由于我們在這里再次走向死胡同，我們將進入我們的第五個優先增長選擇：再次從根增長。如果我們試圖從根’A’增長，我們可以使用（A，b，B）或（A，c，C）。從（A，b，B）開始，我們將得到一個如下所示的子圖

這在我們的任何圖表中都找不到，所以我們嘗試添加（A，c，C）作為我們最后的努力

support=0，回到最近一個待定狀態（1,3,B,b,A），其support<3,繼續回到（0,4,A,c,C）support<3,繼續回到上一個待定狀態(0,2,A,c,C)。

我們可以從C節點擴展，我們的兩個選項是（2,3，C，a，B）和（2,3，C，c，A）添加（2,3，C，a，B）看起來像這樣

第一條邊擴展結束，下面來擴展第二條邊（0，1，A,c,C）此時在原圖中去掉(A,b,B)邊。原圖變為

經過一系列擴展后得到

下面來擴展第三條邊（0，1，B,a,C）此時在原圖中去掉(A,b,B),(A,c,C)邊。原圖變為

經過一系列擴展后得到

綜上所述，所有的頻繁子圖為：

?

總結

以上是生活随笔為你收集整理的图挖掘算法-gSpan的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。