基于強社交圖的多約束信任圖模式增量匹配算法

王鈺蓉 丁鵬飛 劉 安

(蘇州大學計算機科學與技術學院 江蘇 蘇州 215006)

0 引 言

圖模式匹配(GPM)在許多基于社交網絡的應用中發揮了重要的作用，如專家發現[1]和社交社區挖掘[2]。GPM通常是根據子圖同構來定義的，其中模式圖和數據圖之間需要節點和邊的精確匹配。子圖同構是一個經典的NP完全問題，計算量大。此外，對于一些社交應用程序來說，點和邊的精確匹配過于嚴格。因此，提出了圖模擬[3]的概念。在圖模擬中，如果數據圖中路徑的起點和終點分別與模式圖中的邊的兩頂點具有相同的標簽，則該路徑被視為模式邊的匹配。然而，對于一些實際應用而言，圖模擬有時仍然過于嚴格[4-5]。然后，提出了有界模擬[6]的概念。在有界模擬中，每個頂點都被標記為特定的類別，每個邊都可以用常數k或*標記。k和*分別代表匹配的最大路徑長度的約束不大于k以及不限制該路徑長度。有界模擬不執行邊到邊的映射，而是通過有界長度將模式圖中的邊與數據圖中的路徑匹配[6]。根據有界模擬的性質，基于有界模擬的GPM試圖找到最小直徑的子圖。

然而，上下文社交網絡中[7]具有許多與頂點和邊相關聯的上下文信息，例如特定領域中用戶的社會角色(例如，AI的頂級專家)，以及用戶之間的社會關系(例如，同事關系)和用戶之間的信任度。在基于社交網絡的各種應用中，如眾包旅游[8]、研究團隊選擇(classroomsalon.com)和社交網絡中的專家發現[7]，人們通常愿意對GPM中用戶之間的親密社交關系和用戶之間的強信任關系設置一些約束。這些因素對用戶的決策和協作有顯著影響[9-12]。

因此，在基于GPM的社交圖應用中，一種帶有有界路徑長度和社交上下文多重約束的圖模擬方法具有重要意義?；谕瑯嫷腉PM、圖模擬和有界模擬之間的關系如圖1所示。具有多個約束的GPM覆蓋了NP完全的多約束路徑問題[13-14]。因此，在基于多約束模擬的GPM中采用傳統的算法進行有界模擬計算代價昂貴。這是因為傳統的GPM算法必須枚舉每個約束的所有可能匹配，然后找到匹配的區間，導致效率低下。此外，現有的正則路徑查詢方法[15-16]只考慮了一個表達式，沒有考慮到不同屬性的多正則表達式，因此正則路徑查詢方法不適用于基于多約束模擬的GPM。在以前的研究基礎上[17-18]，本文提出了一個考慮多約束的近似算法。這些方法在求解MC-GPM問題中證明了其有效性和效率。

圖1 圖匹配方法分類

在實際應用中，在線社交網絡會頻繁地改變。例如，在Facebook上，平均每分鐘有400個新用戶加入，這會導致社交圖結構的變化。一家市場研究公司Statista(statista.com)已經表明了這種頻繁變化的存在。但是現有的工作沒有提供多約束下的增量匹配，導致GPM在面對數據圖結構的變化時效率較低。因此，目前面臨的主要挑戰是設計高效的技術來支持MC-GPM查詢。本文的主要工作包括：

(1) 提出了一個新的概念，稱為強社交圖(SSG)，它是由具有強社會關系的用戶組成的網絡結構，并提出了一種識別SSG的方法以及一種新的具有多項式時間復雜度的SSG索引結構。

(2) 提出了一種SSG索引增量維護算法INC-SSG。當面臨SSG結構的變化時，INC-SSG可以根據受影響的小部分SSG來更新SSG索引，而不是通過掃描整個SSG結構來重建SSG索引，這可以大大節省MC-GPM的查詢處理時間。

(3) 在INC-SSG的基礎上，提出了一種強社交圖增量MC-GPM算法SSG-IncMGPM。它可以在原匹配結果上進行增量計算，避免重新查詢匹配，加速結果查詢。

(4) 對五個大規模的真實社交圖進行了廣泛的實證研究，驗證了本文所提出的SSG-IncMGPM算法的有效性和效率比現有最好算法SSG-MGPM[19]在回答MC-GPM查詢時的優越性。

1 相關工作

為了減少GPM的同構復雜度，Zou等[20]提出了一種索引方法來記錄數據圖中任意兩個節點之間的最短路徑長度。該索引可以加快GPM的進程。Sun等[21]提出了一種圖模式匹配方法，避免了建立整個圖的索引，從而減少了查詢處理時間。此外，Cheng等[22]提出了一個索引，用于記錄兩跳范圍內的頂點，以加快GPM過程。Cheng等[23]提出了一種Top-k查詢優化方法，建立了循環圖查詢的生成樹，并根據答案邊的長度之和對答案進行排序。Ren等[24]提出了一種緩存多個查詢圖并重新排序這些查詢序列的方法，以提高查詢的應答效率。在實際應用中，從同構的角度提取包含整個查詢圖的子圖通常是不現實的。因此，Yan等[25]定義了一個距離來研究查詢圖和數據圖之間最大公共子圖中匹配的差異。它們為距離的上限定義了一個閾值，距離在上限內的子圖就是需要的結果。Zhu等[26]將一個數據圖分成若干組相似的圖，并對這些圖進行索引，以支持有效的剪枝，從而提高基于相似性的GPM的效率。此外，Shang等[27]提出了一種索引方法來索引查詢圖和數據圖中特征的相似性，以提高GPM的效率。為了進一步提高大圖中圖模式匹配的效率，文獻中提出了采用分布式并行GPM方法進行圖模式匹配的研究。Shao等[28]在一個大數據圖中采用并行框架提取匹配子圖。此外，文獻[29-30]的研究提出了將大數據圖分解成小數據圖的方法，通過將小數據圖的每個分區的結果連接起來，可以得到圖模式匹配的結果。此外，Huang等[31]還提出了一種將大數據圖分解成若干小片段的方法。

由于子圖同構方面的GPM在某些實際應用中過于嚴格，為了進一步放寬約束，圖模擬[32]和有界模擬[6]應運而生。圖模擬可以避免精確的點對點匹配，是在模式圖和數據圖中匹配兩個節點的標簽。在有界模擬中，沒有精確的邊到邊匹配的限制，而是指定了數據圖中匹配路徑的最大路徑長度。這種GPM可以在立方時間內進行。有界模擬[33]是圖模擬的一個擴展，它進一步考慮了GPM中不同類型邊的需求，并根據有界模擬[1]開發了一個社會專家查找系統。Sun等基于圖模擬，研究了特定點匹配問題[34-35]。Fan等[36]進一步提高了基于有界模擬的GPM的效率。他們從數據圖中提取一組視圖，然后研究這些視圖是否能夠回答特定GPM的有界模擬。在分析視圖的基礎上，Fan等[37]又提出了一個資源有界查詢。在他們的模型中，數據圖只有某些部分被識別和索引，因為這些部分很可能包含一些典型模式圖的答案。文獻[17]提出的工作考慮了社交背景的多重約束，但沒有提供增量更新索引的場景，導致GPM在面對數據圖結構變化時效率低下。

2 強社交圖與基于強社交圖的索引

2.1 強社交網絡

圖論[38]中定義了強連通概念：當一個圖任意兩個頂點都是可達的，則這個圖稱為強連通圖。強連通分量可以是有向圖中強連通的子圖?；趫D論中強連通的定義可以延伸出強社交圖的概念：如果每個頂點的角色影響力值都很高，并且頂點之間相連接的邊都具有親密的社交關系和強社交信任關系，則這種連接稱為強社交連接，這種子圖稱為強社交圖(SSG)。強社交圖的細節可以在文獻[18]中找到，發現SSG的偽代碼如算法1所示。

算法1SSG發現算法

輸入：數據圖G,k,λV,λE

輸出：SSGi(i∈[1,k])

1) Selectvii∈[1,k],LV(vi)>λV;

2) Setvi.visit=0;

3) PutviintoExpSet;

4)WhileExpSet≠?do

5) GetvifromExpSet;

6) RemovevifromExpSet;

7)Ifvi.visit=0then

8) Setvi.visit=1;

9)Foreachvj(vjis a neighbor ofvi)do

10)IfLV(vj)>λVandLE(vi,vj)>λEthen

11) PutvjintoExpSet;

12) AddvjandE(vi,vj) into SSG;

正如社會科學研究[39]所指出的，SSG的結構和相應的社交情境，包括用戶之間的信任、用戶之間的社交關系以及用戶的社會角色可以在很長的一段時間內保持穩定。

因此，可以建立SSG的索引來加速MC-GPM。識別所有SSG也是NP完全問題，因為它覆蓋了經典NP完全最大團問題[38]。因此，可以隨機選擇具有高角色影響因子值的k個頂點來作為k個種子。然后采用廣度優先搜索方法識別出k個SSG，找到與種子有密切社會關系和強信任關系的頂點。建立SSG的時間復雜度為O(NDED)。

2.2 強社交圖索引

為SSG建立一個索引結構，如圖2所示。表1是輔助索引構建的矩陣，矩陣中記錄了兩點間的最短距離及相應路徑。在這個索引中，索引了3種信息：可達性、圖模式和社交背景。

圖2 SSG索引結構

表1 SSG索引矩陣

(1) 可達性索引。首先建立可達性索引，記錄節點間的可達性關系。在每個節點上，它都會保存一個列表來索引節點的祖先和后代。因為SSG的大小通常比整個數據圖小很多，可以有效地建立可達性索引[40]。然后，在執行MC-GPM時，可以有效地檢查SSG中任意兩個節點之間是否可達。

(2) 圖模式索引。建立可達性索引后，再建立圖模式索引，記錄SSG的圖模式信息。記錄SSG中任意兩個節點之間的最短路徑長度。然后，在執行MC-GPM時，可以有效地檢查匹配的路徑長度是否滿足SSG中有界路徑長度的約束。

(3) 社交背景索引?；诳蛇_性索引和圖模式索引，建立了社交背景索引。該索引是記錄SSG中路徑的聚合社交影響因子的最大值。在執行MC-GPM時，可以有效地檢查聚合的社交影響因子值是否滿足SSG中用戶給定的約束：如果兩個頂點之間的一條路徑的T、r和ρ的聚合值均占主導地位，將該路徑長度和相應的聚合社交影響因子值作為索引。否則，索引最多三個路徑，分別具有最大聚合T、r和ρ值。

索引中記錄了SSG中的重要信息。給定一個MC-GPM查詢，如果查詢邊的兩個頂點可映射到SSG中的一條路徑中，則該索引信息可用于快速查找是否存在邊模式匹配，從而大大節省查詢處理時間。此外，在最壞的情況下，需要執行Dijkstra算法4次，因此構造索引的時間復雜度為O(NDlogND+ED)。

3 SSG索引的增量維護算法INC-SSG

3.1 INC-SSG問題

表2中給出了本文中使用的相關符號及其含義。

表2 符號表

續表2

INC-SSG問題的定義如下：

輸入：強社交圖SSG、SSG索引、矩陣M和SSG的變化。

輸出：更新的SSG索引。

定義1當面對SSG的變化時，INC-SSG是通過查找SSG受影響的部分AFF來增量更新SSG索引信息。

3.2 算法概述

上述可達性、圖模式和社交背景索引可有效地用于研究是否存在圖模式匹配。然而，在實際應用中，圖的結構變化是常見的[41]，每次更新圖時重建整個索引結構的成本太高。這促使需要研究增量方法來最大限度地保持舊索引，只更新受影響的部分索引，而不是重建整個索引結構。因為圖的結構變化在實踐中通常很小，所以受影響的索引與整個索引相比所占比例也很小。例如，2017年6月，Facebook每月活躍用戶超過20億，每個月約有60萬新用戶加入，但僅占所有用戶的0.03%。顯然，更新受影響部分的索引比更新整個圖更有效。只需構建一次圖的完整索引，然后更新圖時只要增量地維護索引。根據初始可達性索引和圖模式索引計算影響區域，用矩陣來記錄這些信息。

3.3 單邊刪除的索引更新算法

首先給出一個處理單邊刪除的增量算法，用ED-SSG表示，具體如表3所示。

表3 刪除邊(C,E)后的索引矩陣

算法2單邊刪除更新索引的算法

輸入：SSG,SSG索引,刪除的邊(v,w),矩陣M。

輸出：更新的索引。

1) 初始化：AFF=?;

2)Foreach vertexzin SSG andz≠vdo

3)Ifz∈Des(v) andpath(v→z) containswthen

4) addvtoaffectedVertices(z);

5) add(v,z) toAFF;

6)Foreach vertexu∈Anc(v)do

7)Ifpath(u→z) containsvthen

8) addutoaffectedVertices(z);

9) add (u,z) toAFF;

10)Foreach pair(u′,u″) inAFFdo

11)Foreach vertexa∈Des(u′)do

12)Ifa?affectedVertices(u′),u″∈Des(a),a≠w

andpath(u′→a),path(a→u″) do not contain

the vertexwthen

13)M(u′,u″)=min{Slen(u′,a)+Slen(a,u″)}∪{?};

14)path(u′→u″)=path((u′→a)+path(a→u″);

15)Foreach pair(u′,u″) inAFFdo

16)IfM(u′,u″)=∞then

17) removeu″ from the indices ofu′;

18) removeu′ from the indices ofu″;

19)Else

20)Slen(u′,u″)=M(u′,u″)=Plen(u′,u″);

21) computeASaccording to thepath(u′→u″);

22)Returnthe indices of SSG；

步驟1將AFF初始化為空。AFF是節點對集合，記錄圖更新時節點間距離發生變化的節點對。

步驟2對于SSG中的每個頂點z(v除外)，查找到z的最短路徑長度受影響的頂點。如果z是v的后代，且從v到z的最短路徑經過w，則刪除的邊(v,w)會影響v和z之間的距離。然后，搜索v的祖先，以找到到z的最短路徑經過v的頂點。否則，這意味著刪除的邊不會影響任何其他頂點與z之間的距離，因此繼續搜索圖中其他未探索的頂點。

步驟3根據AFF更新矩陣M。對于AFF中的任何節點對(u′,u″)，如果存在一個頂點a，它是u′的后代，u″是a的后代且(a,u′)不在AFF中。此外，a滿足u′到a和a到u″的最短路徑都不經過w，然后計算u′到u″經過a的最短路徑長度并記錄路徑。否則，繼續調查AFF中的另一個節點對。

步驟4根據矩陣M和AFF更新索引。當u′與u″之間的距離為∞時，u″應從u′的可達性索引、圖模式索引和社交背景索引中去除。同樣，u′也應該從u″的索引中去掉。否則，更新u′和u″的圖模式索引和社交背景索引。Slen的值等于新的最短路徑長度。根據記錄的路徑，重新計算Plen和AS。

步驟5返回新SSG的更新索引。

例1：如圖3所示，給出了一個SSG，刪除邊(C，E)。

圖3 刪除邊(C,E)后的索引結構

更新索引的步驟如下：

(1) 找到矩陣M受影響的部分，并以頂點E為例。E是C的后代，C到E的最短路徑通過E，從而C和E之間的距離受到影響。類似地，研究其他頂點H和F。最后，受影響的節點對是(C，E)和(C，H)。

(2) 更新矩陣M。C和E之間的距離變為∞。C與H的距離仍為2，但最短路徑為C→F→H。

(3) 頂點C和E將分別從E和C的索引中移除。AS的值應重新計算為AS(path(C→H))={0.86，0.81，0.89}。

復雜度：算法的偽碼在算法2中給出。復雜度是O(n)，其中n是SSG中頂點的數目。

3.4 單邊插入的索引更新算法

同樣，也設計了一個增量算法來處理單邊插入，用EI-SSG表示，具體如表4所示。

表4 插入邊(C,H)后的索引矩陣

算法3單邊插入更新索引的方法

輸入：SSG,SSG索引,插入的邊(v,w),矩陣M。

輸出：更新的索引。

1) 初始化AFF:?;workSet:{(v,w) };visitedVerteices:{v};

2)Foreach vertexzin SSG andz≠vdo

3)WhileworkSetis not emptydo

4) get and remove edge (u,u′) fromworkSet;

5)IfM(u′,z)>0 andM(u′,z)≠∞then

6)dist(u,z)=Slen(u,z)∪{∞};

7)dist(u′,z)=Slen(u′,z)∪{0};

8)If(1+dist(u′,z))

9) add (u,z) toAFF;

10)M(u,z)=1+dist(u′,z);

11)path(u→z)={u}+path(u′→z);

12)Foreachv′∈Anc(u),Slen(v′,u)=1 andv′ is

not invisitedVerticesdo

13)Ifpath(v′→z) containsuorM(v′,z)=∞

then

14) addv′ tovisitedVertices;

15) add (v′,u) toworkSet;

16)Foreach pair (vf,vt) inAFFdo

17)Ifvtis not inDes(vf)then

18) addvttoDes(vf),Slen=M(vf,vt)=Plen;

19) computeASaccording topath(vf→vt);

20) addvftoAnc(vt),Slen=M(vf,vt)=Plen;

21) computeASaccording topath(vf→vt);

22)Else

23)Slen(vf,vt)=M(vf,vt)=Plen(vf,vt);

24) computeASaccording to thepath(vf→vt);

25)Returnthe indices of SSC;

步驟1將AFF初始化為空，將(v,w)添加到workSet，將v添加到visitedVertices。

步驟2對于SSG中的每個頂點z(v除外)，重復執行步驟3，直到workSet變為空。

步驟3計算AFF，同時更新矩陣M。從workSet中獲取并移除(u,u′)。如果u′到z是可達的，計算u和z之間的新距離，并將其與舊距離進行比較。如果新距離更好，則更新矩陣M并在從u′到z的路徑首部添加u。此外，將(u,z)添加到AFF。然后，轉步驟4。否則，重復執行步驟3。

步驟4找到u的祖先v′，如果從v′到z不可達，或者從v到z的路徑通過u，則將(v′,u)添加到workSet，并將v′設置為已訪問。否則，繼續調查u其他未被訪問過的祖先。

步驟5根據矩陣M和AFF更新索引。對于AFF中的任何節點對(vf,vt),如果在更新前vt不是vf的后代，則應將vt、vf分別插入vf和vt的索引中。同時根據記錄的路徑計算Slen、Plen和AS。否則，更新vf和vt的圖模式索引和社交背景索引。Slen的值等于新的最短路徑長度。根據記錄的路徑，重新計算Plen和AS。

步驟6返回新SSG的更新索引。

例2：如圖4所示，SSG中插入邊(C，H)。

圖4 插入邊(C,H)后的索引結構

索引更新步驟如下：

首先，找到AFF并同時更新矩陣M，取頂點H為例。C和H之間的距離變為1，比原距離2更近。因此，更新M并記錄路徑C→H。顯然，頂點C沒有任何祖先，因此繼續研究E和H。最后，受影響的節點對是(C，H)。

接下來，更新索引。C和H之間的最短路徑長度變為1。重新計算AS(path(C→H))={0.98，0.9，0.92}。

復雜度：算法的偽碼在算法3中給出。復雜度是O(n|E|)，其中n是SSG中頂點的數目，而|E|是SSG中的邊數。

3.5 增刪頂點的索引更新算法

在上述算法的基礎上，更容易解決頂點更新問題。接下來，給出處理頂點刪除和插入的簡明說明。

頂點刪除：給定一個刪除的頂點v，首先根據可達性索引求出從v開始或結束于v的邊。對于每個受影響的邊，執行前面提到的算法ED-SSG。更重要的是，不要忘記從矩陣中刪除v對應的行和列，同時刪除v的索引。該算法被稱為VD-SSG，刪除每條邊的復雜度是O(n)。

頂點插入：處理頂點插入的算法由VI-SSG表示。與頂點刪除相反，首先需要將頂點v′的行和列插入到矩陣中。然后，通過算法EI-SSG處理相關的邊。類似地，插入每條邊的復雜度是O(n|E|)。

提出的INC-SSG算法可以應用于整個社交圖。然而，在大規模的社交圖中，建立和維護索引信息可能會導致昂貴的時間開銷，其中圖結構和屬性值的更改比SSG中的更改更頻繁。此外，在圖模式匹配過程中，數據圖中的許多節點不會被訪問，而強社交圖中節點訪問概率更高。因此，保留整個社交圖的索引信息是沒有必要的。

4 增量匹配算法框架SSG-IncMGPM

首先，采用HAMC方法[17]對原始數據圖進行查詢圖匹配，獲得初始匹配結果。HAMC方法是現今解決未發生圖結構變化的MC-GPM問題最優的方法。然后，當數據圖更新時，采用INC-SSG對索引進行更新。最后，調用增量匹配算法IncGMPM對初始匹配結果進行增量計算，得到最終匹配。下面介紹多約束路徑匹配的一個目標函數，用來輔助匹配過程；其次，對增量匹配算法進行詳細說明，如圖5所示。

圖5 增量匹配算法框架SSG-IncMGPM

4.1 路徑匹配目標函數

首先，對于強社交多約束信任圖中的路徑匹配問題，給出一個目標函數式如下：

(1)

4.2 增量匹配算法

在對更新之后的數據圖進行圖匹配時，因為每次更新操作量都是相對較少的，若每次更新都要重新匹配，會帶來冗余的計算量。所以結合更新的索引信息，可以對數據圖進行增量匹配，并且索引能輔助加快匹配速度。

下面對增量匹配算法分成兩種情況進行討論：刪除邊和增加邊(對于頂點的增刪情況可以分解為邊的刪減)。

4.2.1刪邊的增量匹配算法

邊的減少肯定不會導致匹配結果增加，同時如果減少的邊不包含在原始匹配結果中也不會導致匹配結果的減少。只有當減少的邊包含在原始匹配結果中，則需要將該邊從匹配結果中刪除。

算法4刪邊增量匹配算法

輸入：原始匹配Gm,查詢圖GQ,刪除邊e,更新后的索引I。

輸出：新的匹配Gnew。

1)IfGmcontainsethen

2) record the path setPinGmand the responding

matched edge inGQ,the path inPcontainse;

3)Foreach pathpinPdo

4) computeδofpaccording toI;

5)Ifδ>1then

6) removepfromGm;

7)Else

8)Gnew=Gm;

9)If? a vertex or an edge inGQand no match inGm

then

10)Gnew=?;

11)Else

12)Gnew=the updatedGm;

13)ReturnGnew

步驟1根據刪除的邊，判斷是否在原始匹配結果中，若不存在，則返回原結果。

步驟2若存在于原始匹配結果中，則記錄結果中包含刪除邊的匹配路徑以及所對應的GQ中被匹配的邊。

步驟3對于受影響的匹配路徑，根據更新的索引計算得δ值，若δ>1，從原匹配結果中移除。

步驟4得到更新后的匹配結果，若查詢圖中存在節點或邊得不到匹配，則將匹配結果置為空。

步驟5返回更新后的匹配結果。

例3：圖6和圖7分別給出了數據圖與查詢圖?？傻玫皆计ヅ浣Y果：A1→B1→B2匹配(A,B)，B2→D→C1匹配(B，C)，B2→D匹配(B,D)，E→C1匹配(E,C)，E→D匹配(E,D)。

圖6 數據圖

圖7 查詢圖

(1) 若刪除邊(B2,C2)不包含在原始匹配結果里，則返回原結果。

(2) 若刪除邊(A1,B1)對應(A,B)的匹配結果路徑，計算得δ不滿足，則移除該匹配。最后發現(A,B)不存在其他匹配，所以更新后的結果為空。

復雜度：算法的偽碼在算法4中給出，復雜度為O(|P|)，其中|P|是指原始匹配Gm中受影響的匹配路徑的數量。

4.2.2增邊的增量匹配算法

邊的增加肯定不會導致匹配結果減少，同時如果增加的邊影響力不夠也不會導致匹配結果的增加。只有當增加的邊使得受影響的AFF中節點對計算得的δ值由大于1變成小于等于1，則增加匹配結果。具體算法與上類似，與之相反的是判斷值來增加結果而不是刪除結果。

算法5增邊增量匹配算法

輸入：原始匹配Gm,查詢圖GQ,增加的邊(vi,vj),AFF,更新后的索引I。

輸出：新的匹配Gnew。

1)IfviorvjinGmthen

2)Foreach pair (vs,vt) inAFFdo

3)If?(vqs,vqt) inGQandvqs,vshave the same

label andvqt,vthave the same labelthen

4) computeδofpath(vs→vt);

5)Ifδ≤1then

6)Ifvsis new inGmthen

7) check if the edge patterns inGQwhich

related tovqshave the matching paths;

8)Ifvtis new inGmthen

9) check if the edge patterns inGQwhich

related tovqthave the matching paths;

10)Ifyesthen

11) add paths toGm;

12)Gnew=the updatedGm;

13)ReturnGnew.

步驟1如果增加的邊的兩個頂點都不包含在Gm中，則返回原結果；否則，執行步驟2。

步驟2對于AFF中的每對頂點(vs,vt)，如果GQ中不存在需匹配的邊與vs、vt具有相同的標簽，則跳過；否則，執行步驟3。

步驟3根據索引計算path(vs→vt)的δ值，如果小于1，執行步驟4。

步驟4判斷vs、vt哪個是新加入的頂點vnew，查詢圖中與vnew相關的邊模式在數據圖中是否存在與之匹配的路徑。若不存在，跳過；否則，把得到的新匹配路徑加到結果中。

步驟5返回更新后的匹配結果。

例4：如圖6和圖7所示，若增加(B2,C2)邊，B2包含在原始結果中。查看AFF中的節點對，發現B2→C2符合匹配，并且查詢圖中與C相關聯的邊(E,C)能得到匹配路徑E→C1→C2。所以，將B2→C2，E→C1→C2加入匹配結果。

復雜度：算法的偽碼在算法5中給出，復雜度為O(|AFF|)。

4.3 總 結

任何更新操作都可以看成增邊與刪邊操作的組合。增量匹配算法的執行時間可能會隨著增加或刪除邊的數量的增加而增加，但是實際情況中，相較于大圖而言，更新的操作量會遠小于大圖的規模。所以，相比于重新進行匹配查詢，增量匹配會節省更多時間開銷。若是更新的邊數量超過原圖的一半，則認為不是以更新為主而是進行了重構，就不采用本算法。

5 實 驗

5.1 實驗設置

1) 數據集。采用了五個在snap.stanford.edu上得到的大規模真實圖，這些圖在圖模式匹配和社交網絡分析方面有著廣泛的應用。這些數據集的詳細情況見表5。

表5 數據集信息

2) 參數設置。在每個數據集中，SSG的個數設置為50，SSG的范圍為70。此外，更新的頂點或邊的數量范圍為5到25，跨度為5；約束值變化范圍為0.075到0.175，跨度為0.025。

3) 實現。實驗實現了本文提出的SSG-IncMGPM和SSG-MGPM[19]這個解決圖結構變化的MC-GPM問題最好的算法，以比較兩個算法的效率。所有的算法都是使用Java實現的，在一臺配備Intel Corei5、2.9 GHz CPU、8 GB RAM的PC機上運行。

5.2 實驗結果和分析

圖8-圖17描述了在邊刪除、邊插入的情況下，在五個數據集中不同更新規模的SSG返回MC-GPM查詢答案時的平均查詢處理時間?？梢钥闯觯?1) 隨著刪除或插入邊數量的增加，兩種方法的平均查詢處理時間都增加；(2) 隨著刪除或插入邊數量的增加，SSG-IncMGPM執行的時間的改進比率逐漸降低；(3) SSG-IncMGPM的查詢處理時間總是小于SSG-MGPM的查詢處理時間。

圖8 刪邊時，Cit-HepTh數據集上算法執行時間

圖9 刪邊時，Slashdot數據集上算法執行時間

圖10 刪邊時，DBLP數據集上算法執行時間

圖11 刪邊時，LiveJournal數據集上算法執行時間

圖12 刪邊時，Twitter數據集上算法執行時間

圖13 插入邊時，Cit-HepTh數據集上算法執行時間

圖14 插入邊時，Slashdot數據集上算法執行時間

圖15 插入邊時，DBLP數據集上算法執行時間

圖16 插入邊時，LiveJournal數據集上算法執行時間

圖17 插入邊時，Twitter數據集上算法執行時間

實驗結果表明：(1) 隨著刪除或插入邊數量的增加，兩種方法都需要花更多的時間來更新索引，因此兩者都需要更多的查詢處理時間；(2) 隨著刪除或插入邊數量的增加，SSG-IncMGPM增量匹配時需要花時間處理更多受影響的邊，并且更新索引比重也在增加，所以改進比率逐漸降低；(3) 無論插入或刪除多少邊，SSG-IncMGPM的性能總是優于SSG-MGPM，這是因為本文方法在面對SSG結構的變化時不需要再重新遍歷整個圖得到匹配結果。

圖18-圖27描述了刪減邊數量固定不變的情況下，在五個數據集上執行具有不同約束值的MC-GPM查詢時的平均查詢處理時間?？梢钥闯觯?1) 隨著約束值的變化，兩種方法的查詢處理時間都相對穩定；(2) 在所有情況下，SSG-MGPM算法都比SSG-IncMGPM需要更多的處理時間；(3) SSG-IncMGPM算法執行時間改進比率保持較穩定狀態。

圖18 不同約束值，Cit-HepTh數據集上刪邊算法執行時間

圖19 不同約束值，Slashdot數據集上刪邊算法執行時間

圖20 不同約束值，DBLP數據集上刪邊算法執行時間

圖21 不同約束值，LiveJournal數據集上刪邊算法執行時間

圖22 不同約束值，Twitter數據集上刪邊算法執行時間

圖23 不同約束值，Cit-HepTh數據集上增邊算法執行時間

圖24 不同約束值，Slashdot數據集上增邊算法執行時間

圖25 不同約束值，DBLP數據集上增邊算法執行時間

圖26 不同約束值，LiveJournal數據集上增邊算法執行時間

圖27 不同約束值，Twitter數據集上增邊算法執行時間

實驗結果表明：(1) 約束值的大小對算法的查詢處理時間無較大影響，所以隨著約束值的增大，兩者的查詢處理時間均保持穩定；(2) 由于不需要重新匹配得到結果，SSG-IncMGPM的性能一直優于SSG-MGPM；(3) 由于增刪邊數無變化，所以對SSG-IncMGPM和SSG-MGPM算法執行時間不會產生較大波動，兩者均處于平穩狀態。

綜上，本文提出的SSG-IncMGPM考慮了強社交圖，并增量維護了SSG索引的同時，對模式圖進行增量匹配。實驗結果表明，SSG-IncMGPM是解決具有挑戰性的NP完全問題MC-GPM的有效方法。所提出的方法可以作為許多基于社交圖的應用的核心，如在線社交網絡中的信任/惡意網絡查找和基于社交網絡的眾包中的可信作品選擇。

6 結 語

本文提出了一個強社交圖的概念，并給出了一個SSG的索引結構。在此基礎上，提出了一種基于增量的SSG索引維護算法INC-SSG。最后，提出了一種基于INC-SSG的求解NP完全問題MC-GPM的SSG-IncMGPM算法。在五個真實的社交圖上進行的實驗表明，本文方法優于最新的方法。