王鈺蓉 丁鵬飛 劉 安

(蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 江蘇 蘇州 215006)

0 引 言

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

然而，上下文社交網(wǎng)絡(luò)中[7]具有許多與頂點(diǎn)和邊相關(guān)聯(lián)的上下文信息，例如特定領(lǐng)域中用戶的社會(huì)角色(例如，AI的頂級(jí)專家)，以及用戶之間的社會(huì)關(guān)系(例如，同事關(guān)系)和用戶之間的信任度。在基于社交網(wǎng)絡(luò)的各種應(yīng)用中，如眾包旅游[8]、研究團(tuán)隊(duì)選擇(classroomsalon.com)和社交網(wǎng)絡(luò)中的專家發(fā)現(xiàn)[7]，人們通常愿意對(duì)GPM中用戶之間的親密社交關(guān)系和用戶之間的強(qiáng)信任關(guān)系設(shè)置一些約束。這些因素對(duì)用戶的決策和協(xié)作有顯著影響[9-12]。

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

圖1 圖匹配方法分類

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

(1) 提出了一個(gè)新的概念，稱為強(qiáng)社交圖(SSG)，它是由具有強(qiáng)社會(huì)關(guān)系的用戶組成的網(wǎng)絡(luò)結(jié)構(gòu)，并提出了一種識(shí)別SSG的方法以及一種新的具有多項(xiàng)式時(shí)間復(fù)雜度的SSG索引結(jié)構(gòu)。

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

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

(4) 對(duì)五個(gè)大規(guī)模的真實(shí)社交圖進(jìn)行了廣泛的實(shí)證研究，驗(yàn)證了本文所提出的SSG-IncMGPM算法的有效性和效率比現(xiàn)有最好算法SSG-MGPM[19]在回答MC-GPM查詢時(shí)的優(yōu)越性。

1 相關(guān)工作

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

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

2 強(qiáng)社交圖與基于強(qiáng)社交圖的索引

2.1 強(qiáng)社交網(wǎng)絡(luò)

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

算法1SSG發(fā)現(xiàn)算法

輸入：數(shù)據(jù)圖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;

正如社會(huì)科學(xué)研究[39]所指出的，SSG的結(jié)構(gòu)和相應(yīng)的社交情境，包括用戶之間的信任、用戶之間的社交關(guān)系以及用戶的社會(huì)角色可以在很長(zhǎng)的一段時(shí)間內(nèi)保持穩(wěn)定。

因此，可以建立SSG的索引來加速M(fèi)C-GPM。識(shí)別所有SSG也是NP完全問題，因?yàn)樗采w了經(jīng)典NP完全最大團(tuán)問題[38]。因此，可以隨機(jī)選擇具有高角色影響因子值的k個(gè)頂點(diǎn)來作為k個(gè)種子。然后采用廣度優(yōu)先搜索方法識(shí)別出k個(gè)SSG，找到與種子有密切社會(huì)關(guān)系和強(qiáng)信任關(guān)系的頂點(diǎn)。建立SSG的時(shí)間復(fù)雜度為O(NDED)。

2.2 強(qiáng)社交圖索引

為SSG建立一個(gè)索引結(jié)構(gòu)，如圖2所示。表1是輔助索引構(gòu)建的矩陣，矩陣中記錄了兩點(diǎn)間的最短距離及相應(yīng)路徑。在這個(gè)索引中，索引了3種信息：可達(dá)性、圖模式和社交背景。

圖2 SSG索引結(jié)構(gòu)

表1 SSG索引矩陣

(1) 可達(dá)性索引。首先建立可達(dá)性索引，記錄節(jié)點(diǎn)間的可達(dá)性關(guān)系。在每個(gè)節(jié)點(diǎn)上，它都會(huì)保存一個(gè)列表來索引節(jié)點(diǎn)的祖先和后代。因?yàn)镾SG的大小通常比整個(gè)數(shù)據(jù)圖小很多，可以有效地建立可達(dá)性索引[40]。然后，在執(zhí)行MC-GPM時(shí)，可以有效地檢查SSG中任意兩個(gè)節(jié)點(diǎn)之間是否可達(dá)。

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

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

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

3 SSG索引的增量維護(hù)算法INC-SSG

3.1 INC-SSG問題

表2中給出了本文中使用的相關(guān)符號(hào)及其含義。

表2 符號(hào)表

續(xù)表2

INC-SSG問題的定義如下：

輸入：強(qiáng)社交圖SSG、SSG索引、矩陣M和SSG的變化。

輸出：更新的SSG索引。

定義1當(dāng)面對(duì)SSG的變化時(shí)，INC-SSG是通過查找SSG受影響的部分AFF來增量更新SSG索引信息。

3.2 算法概述

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

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

首先給出一個(gè)處理單邊刪除的增量算法，用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是節(jié)點(diǎn)對(duì)集合，記錄圖更新時(shí)節(jié)點(diǎn)間距離發(fā)生變化的節(jié)點(diǎn)對(duì)。

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

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

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

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

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

圖3 刪除邊(C,E)后的索引結(jié)構(gòu)

更新索引的步驟如下：

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

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

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

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

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

同樣，也設(shè)計(jì)了一個(gè)增量算法來處理單邊插入，用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對(duì)于SSG中的每個(gè)頂點(diǎn)z(v除外)，重復(fù)執(zhí)行步驟3，直到workSet變?yōu)榭铡?/p>

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

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

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

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

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

圖4 插入邊(C,H)后的索引結(jié)構(gòu)

索引更新步驟如下：

首先，找到AFF并同時(shí)更新矩陣M，取頂點(diǎn)H為例。C和H之間的距離變?yōu)?，比原距離2更近。因此，更新M并記錄路徑C→H。顯然，頂點(diǎn)C沒有任何祖先，因此繼續(xù)研究E和H。最后，受影響的節(jié)點(diǎn)對(duì)是(C，H)。

接下來，更新索引。C和H之間的最短路徑長(zhǎng)度變?yōu)?。重新計(jì)算AS(path(C→H))={0.98，0.9，0.92}。

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

3.5 增刪頂點(diǎn)的索引更新算法

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

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

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

提出的INC-SSG算法可以應(yīng)用于整個(gè)社交圖。然而，在大規(guī)模的社交圖中，建立和維護(hù)索引信息可能會(huì)導(dǎo)致昂貴的時(shí)間開銷，其中圖結(jié)構(gòu)和屬性值的更改比SSG中的更改更頻繁。此外，在圖模式匹配過程中，數(shù)據(jù)圖中的許多節(jié)點(diǎn)不會(huì)被訪問，而強(qiáng)社交圖中節(jié)點(diǎn)訪問概率更高。因此，保留整個(gè)社交圖的索引信息是沒有必要的。

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

首先，采用HAMC方法[17]對(duì)原始數(shù)據(jù)圖進(jìn)行查詢圖匹配，獲得初始匹配結(jié)果。HAMC方法是現(xiàn)今解決未發(fā)生圖結(jié)構(gòu)變化的MC-GPM問題最優(yōu)的方法。然后，當(dāng)數(shù)據(jù)圖更新時(shí)，采用INC-SSG對(duì)索引進(jìn)行更新。最后，調(diào)用增量匹配算法IncGMPM對(duì)初始匹配結(jié)果進(jìn)行增量計(jì)算，得到最終匹配。下面介紹多約束路徑匹配的一個(gè)目標(biāo)函數(shù)，用來輔助匹配過程；其次，對(duì)增量匹配算法進(jìn)行詳細(xì)說明，如圖5所示。

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

4.1 路徑匹配目標(biāo)函數(shù)

首先，對(duì)于強(qiáng)社交多約束信任圖中的路徑匹配問題，給出一個(gè)目標(biāo)函數(shù)式如下：

(1)

4.2 增量匹配算法

在對(duì)更新之后的數(shù)據(jù)圖進(jìn)行圖匹配時(shí)，因?yàn)槊看胃虏僮髁慷际窍鄬?duì)較少的，若每次更新都要重新匹配，會(huì)帶來冗余的計(jì)算量。所以結(jié)合更新的索引信息，可以對(duì)數(shù)據(jù)圖進(jìn)行增量匹配，并且索引能輔助加快匹配速度。

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

4.2.1刪邊的增量匹配算法

邊的減少肯定不會(huì)導(dǎo)致匹配結(jié)果增加，同時(shí)如果減少的邊不包含在原始匹配結(jié)果中也不會(huì)導(dǎo)致匹配結(jié)果的減少。只有當(dāng)減少的邊包含在原始匹配結(jié)果中，則需要將該邊從匹配結(jié)果中刪除。

算法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根據(jù)刪除的邊，判斷是否在原始匹配結(jié)果中，若不存在，則返回原結(jié)果。

步驟2若存在于原始匹配結(jié)果中，則記錄結(jié)果中包含刪除邊的匹配路徑以及所對(duì)應(yīng)的GQ中被匹配的邊。

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

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

步驟5返回更新后的匹配結(jié)果。

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

圖6 數(shù)據(jù)圖

圖7 查詢圖

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

(2) 若刪除邊(A1,B1)對(duì)應(yīng)(A,B)的匹配結(jié)果路徑，計(jì)算得δ不滿足，則移除該匹配。最后發(fā)現(xiàn)(A,B)不存在其他匹配，所以更新后的結(jié)果為空。

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

4.2.2增邊的增量匹配算法

邊的增加肯定不會(huì)導(dǎo)致匹配結(jié)果減少，同時(shí)如果增加的邊影響力不夠也不會(huì)導(dǎo)致匹配結(jié)果的增加。只有當(dāng)增加的邊使得受影響的AFF中節(jié)點(diǎn)對(duì)計(jì)算得的δ值由大于1變成小于等于1，則增加匹配結(jié)果。具體算法與上類似，與之相反的是判斷值來增加結(jié)果而不是刪除結(jié)果。

算法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如果增加的邊的兩個(gè)頂點(diǎn)都不包含在Gm中，則返回原結(jié)果；否則，執(zhí)行步驟2。

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

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

步驟4判斷vs、vt哪個(gè)是新加入的頂點(diǎn)vnew，查詢圖中與vnew相關(guān)的邊模式在數(shù)據(jù)圖中是否存在與之匹配的路徑。若不存在，跳過；否則，把得到的新匹配路徑加到結(jié)果中。

步驟5返回更新后的匹配結(jié)果。

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

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

4.3 總 結(jié)

任何更新操作都可以看成增邊與刪邊操作的組合。增量匹配算法的執(zhí)行時(shí)間可能會(huì)隨著增加或刪除邊的數(shù)量的增加而增加，但是實(shí)際情況中，相較于大圖而言，更新的操作量會(huì)遠(yuǎn)小于大圖的規(guī)模。所以，相比于重新進(jìn)行匹配查詢，增量匹配會(huì)節(jié)省更多時(shí)間開銷。若是更新的邊數(shù)量超過原圖的一半，則認(rèn)為不是以更新為主而是進(jìn)行了重構(gòu)，就不采用本算法。

5 實(shí) 驗(yàn)

5.1 實(shí)驗(yàn)設(shè)置

1) 數(shù)據(jù)集。采用了五個(gè)在snap.stanford.edu上得到的大規(guī)模真實(shí)圖，這些圖在圖模式匹配和社交網(wǎng)絡(luò)分析方面有著廣泛的應(yīng)用。這些數(shù)據(jù)集的詳細(xì)情況見表5。

表5 數(shù)據(jù)集信息

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

3) 實(shí)現(xiàn)。實(shí)驗(yàn)實(shí)現(xiàn)了本文提出的SSG-IncMGPM和SSG-MGPM[19]這個(gè)解決圖結(jié)構(gòu)變化的MC-GPM問題最好的算法，以比較兩個(gè)算法的效率。所有的算法都是使用Java實(shí)現(xiàn)的，在一臺(tái)配備Intel Corei5、2.9 GHz CPU、8 GB RAM的PC機(jī)上運(yùn)行。

5.2 實(shí)驗(yàn)結(jié)果和分析

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

圖8 刪邊時(shí)，Cit-HepTh數(shù)據(jù)集上算法執(zhí)行時(shí)間

圖9 刪邊時(shí)，Slashdot數(shù)據(jù)集上算法執(zhí)行時(shí)間

圖10 刪邊時(shí)，DBLP數(shù)據(jù)集上算法執(zhí)行時(shí)間

圖11 刪邊時(shí)，LiveJournal數(shù)據(jù)集上算法執(zhí)行時(shí)間

圖12 刪邊時(shí)，Twitter數(shù)據(jù)集上算法執(zhí)行時(shí)間

圖13 插入邊時(shí)，Cit-HepTh數(shù)據(jù)集上算法執(zhí)行時(shí)間

圖14 插入邊時(shí)，Slashdot數(shù)據(jù)集上算法執(zhí)行時(shí)間

圖15 插入邊時(shí)，DBLP數(shù)據(jù)集上算法執(zhí)行時(shí)間

圖16 插入邊時(shí)，LiveJournal數(shù)據(jù)集上算法執(zhí)行時(shí)間

圖17 插入邊時(shí)，Twitter數(shù)據(jù)集上算法執(zhí)行時(shí)間

實(shí)驗(yàn)結(jié)果表明：(1) 隨著刪除或插入邊數(shù)量的增加，兩種方法都需要花更多的時(shí)間來更新索引，因此兩者都需要更多的查詢處理時(shí)間；(2) 隨著刪除或插入邊數(shù)量的增加，SSG-IncMGPM增量匹配時(shí)需要花時(shí)間處理更多受影響的邊，并且更新索引比重也在增加，所以改進(jìn)比率逐漸降低；(3) 無論插入或刪除多少邊，SSG-IncMGPM的性能總是優(yōu)于SSG-MGPM，這是因?yàn)楸疚姆椒ㄔ诿鎸?duì)SSG結(jié)構(gòu)的變化時(shí)不需要再重新遍歷整個(gè)圖得到匹配結(jié)果。

圖18-圖27描述了刪減邊數(shù)量固定不變的情況下，在五個(gè)數(shù)據(jù)集上執(zhí)行具有不同約束值的MC-GPM查詢時(shí)的平均查詢處理時(shí)間。可以看出：(1) 隨著約束值的變化，兩種方法的查詢處理時(shí)間都相對(duì)穩(wěn)定；(2) 在所有情況下，SSG-MGPM算法都比SSG-IncMGPM需要更多的處理時(shí)間；(3) SSG-IncMGPM算法執(zhí)行時(shí)間改進(jìn)比率保持較穩(wěn)定狀態(tài)。

圖18 不同約束值，Cit-HepTh數(shù)據(jù)集上刪邊算法執(zhí)行時(shí)間

圖19 不同約束值，Slashdot數(shù)據(jù)集上刪邊算法執(zhí)行時(shí)間

圖20 不同約束值，DBLP數(shù)據(jù)集上刪邊算法執(zhí)行時(shí)間

圖21 不同約束值，LiveJournal數(shù)據(jù)集上刪邊算法執(zhí)行時(shí)間

圖22 不同約束值，Twitter數(shù)據(jù)集上刪邊算法執(zhí)行時(shí)間

圖23 不同約束值，Cit-HepTh數(shù)據(jù)集上增邊算法執(zhí)行時(shí)間

圖24 不同約束值，Slashdot數(shù)據(jù)集上增邊算法執(zhí)行時(shí)間

圖25 不同約束值，DBLP數(shù)據(jù)集上增邊算法執(zhí)行時(shí)間

圖26 不同約束值，LiveJournal數(shù)據(jù)集上增邊算法執(zhí)行時(shí)間

圖27 不同約束值，Twitter數(shù)據(jù)集上增邊算法執(zhí)行時(shí)間

實(shí)驗(yàn)結(jié)果表明：(1) 約束值的大小對(duì)算法的查詢處理時(shí)間無較大影響，所以隨著約束值的增大，兩者的查詢處理時(shí)間均保持穩(wěn)定；(2) 由于不需要重新匹配得到結(jié)果，SSG-IncMGPM的性能一直優(yōu)于SSG-MGPM；(3) 由于增刪邊數(shù)無變化，所以對(duì)SSG-IncMGPM和SSG-MGPM算法執(zhí)行時(shí)間不會(huì)產(chǎn)生較大波動(dòng)，兩者均處于平穩(wěn)狀態(tài)。

綜上，本文提出的SSG-IncMGPM考慮了強(qiáng)社交圖，并增量維護(hù)了SSG索引的同時(shí)，對(duì)模式圖進(jìn)行增量匹配。實(shí)驗(yàn)結(jié)果表明，SSG-IncMGPM是解決具有挑戰(zhàn)性的NP完全問題MC-GPM的有效方法。所提出的方法可以作為許多基于社交圖的應(yīng)用的核心，如在線社交網(wǎng)絡(luò)中的信任/惡意網(wǎng)絡(luò)查找和基于社交網(wǎng)絡(luò)的眾包中的可信作品選擇。

6 結(jié) 語

本文提出了一個(gè)強(qiáng)社交圖的概念，并給出了一個(gè)SSG的索引結(jié)構(gòu)。在此基礎(chǔ)上，提出了一種基于增量的SSG索引維護(hù)算法INC-SSG。最后，提出了一種基于INC-SSG的求解NP完全問題MC-GPM的SSG-IncMGPM算法。在五個(gè)真實(shí)的社交圖上進(jìn)行的實(shí)驗(yàn)表明，本文方法優(yōu)于最新的方法。