張曉琳，袁昊晨，李卓麟，張換香，劉 嬌

內(nèi)蒙古科技大學(xué) 信息工程學(xué)院，內(nèi)蒙古 包頭 014000

1 引言

隨著社會(huì)網(wǎng)絡(luò)的快速發(fā)展，社會(huì)網(wǎng)絡(luò)含有更加豐富的信息，例如Facebook、Twitter、微博等。社會(huì)網(wǎng)絡(luò)中含有用戶的隱私信息，在云平臺(tái)內(nèi)進(jìn)行子圖匹配[1-4]時(shí)保護(hù)隱私信息是非常重要的。K-自同構(gòu)算法[5]是傳統(tǒng)的社會(huì)網(wǎng)絡(luò)隱私保護(hù)算法，這種方法在處理大規(guī)模社會(huì)網(wǎng)絡(luò)圖時(shí)，處理效率會(huì)大幅度下降[6]而且不能保證較高的數(shù)據(jù)可用性。傳統(tǒng)的K-自同構(gòu)算法在原始圖中添加噪聲邊，使原始圖中的每個(gè)節(jié)點(diǎn)都有至少有k-1 個(gè)對(duì)稱節(jié)點(diǎn)。如圖1 是社會(huì)網(wǎng)絡(luò)原始圖，在原始圖的基礎(chǔ)上添加3 條噪聲邊，同時(shí)根據(jù)表1對(duì)原始圖的標(biāo)簽進(jìn)行標(biāo)簽分組泛化[7]后使原始圖轉(zhuǎn)換成2-自同構(gòu)圖，如圖2。

可以看出K-自同構(gòu)算法能很好地抵御結(jié)構(gòu)攻擊。但這種方法因?yàn)樘砑恿嗽肼曔叄瑢?dǎo)致了子圖匹配結(jié)果的不準(zhǔn)確以及在云平臺(tái)中進(jìn)行子圖匹配大量的空間時(shí)間消耗。

為此提出一種解決方案，將原始社會(huì)網(wǎng)絡(luò)圖匿名成K-自同構(gòu)匿名圖并將K-自同構(gòu)匿名圖的一部分和K-自同構(gòu)函數(shù)上傳至云平臺(tái)中；在云平臺(tái)中進(jìn)行子圖匹配操作得到不完全子圖匹配結(jié)果；將得到的結(jié)果以及K-自同構(gòu)函數(shù)下載至客戶端內(nèi)進(jìn)行恢復(fù)和過濾。本文主要研究內(nèi)容如下：

（1）提出分布式K-自同構(gòu)社會(huì)網(wǎng)絡(luò)隱私保護(hù)算法DK-A（distributedK-automorphism）保護(hù)社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)隱私，為了減少子圖匹配時(shí)間空間成本，上傳K-自同構(gòu)圖的一部分和K-自同構(gòu)函數(shù)至云平臺(tái)。

（2）提出分布并行的子圖匹配方法，在云平臺(tái)中對(duì)搜索分解子圖QSGs（query subgraphs）進(jìn)行子圖匹配，將得到的結(jié)果以及K-自同構(gòu)函數(shù)下載回客戶端中進(jìn)行子圖匹配。

（3）通過實(shí)驗(yàn)證明以上方法保證了社會(huì)網(wǎng)絡(luò)在上傳至云平臺(tái)中進(jìn)行子圖匹配時(shí)沒有泄露隱私，并且大幅度減少了空間和計(jì)算成本。

2 相關(guān)工作

Fig.1 Original graph of social network圖1 社會(huì)網(wǎng)絡(luò)原始圖

Fig.2 2-automorphism anonymous graph of original graph圖2 原始圖的2-自同構(gòu)匿名圖

許多學(xué)者對(duì)保護(hù)社會(huì)網(wǎng)絡(luò)的結(jié)構(gòu)隱私信息做出了研究，這些研究可以作為保護(hù)上傳圖隱私信息的基本方法。文獻(xiàn)[8]假設(shè)攻擊者只使用一種結(jié)構(gòu)攻擊方法，然而攻擊者有可能使用多種結(jié)構(gòu)攻擊方法獲得隱私信息。文獻(xiàn)[9-13]提出的基于刪除邊的結(jié)構(gòu)隱私保護(hù)算法，邊的刪除可能會(huì)導(dǎo)致上傳圖丟失重要信息。使用分布式K-自同構(gòu)社會(huì)網(wǎng)絡(luò)隱私保護(hù)算法作為匿名社會(huì)網(wǎng)絡(luò)的基本方法原因如下：因?yàn)樗惴]有刪除邊，所以不會(huì)丟失重要信息；利用K-自同構(gòu)圖的對(duì)稱性可以在客戶端中恢復(fù)子圖匹配結(jié)果；分布式K-自同構(gòu)社會(huì)網(wǎng)絡(luò)隱私保護(hù)算法適用于大規(guī)模社會(huì)網(wǎng)絡(luò)環(huán)境。

文獻(xiàn)[14]提出LP（linear programming）模型可以匿名權(quán)重社會(huì)網(wǎng)絡(luò)圖并且保留圖中節(jié)點(diǎn)間的最短路徑，但是攻擊者具有任意拓?fù)浔尘靶畔r(shí)可以對(duì)匿名圖進(jìn)行重識(shí)別，而且不能保護(hù)客戶端內(nèi)子圖匹配結(jié)果的準(zhǔn)確。文獻(xiàn)[7，15]提出了保護(hù)子圖匹配結(jié)果正確性的社會(huì)網(wǎng)絡(luò)隱私保護(hù)方法，這些思想通過使用圖的索引進(jìn)行子圖匹配，保證結(jié)果的正確性但是不適用于大規(guī)模社會(huì)網(wǎng)絡(luò)環(huán)境。

本文提出DK-A 算法保護(hù)發(fā)布至云平臺(tái)中社會(huì)網(wǎng)絡(luò)的圖的隱私，提出適用于大規(guī)模社會(huì)網(wǎng)路的分布式子圖匹配方法，保證在云平臺(tái)中進(jìn)行高效的子圖匹配同時(shí)確保隱私不會(huì)泄露，并通過對(duì)匹配結(jié)果的恢復(fù)和過濾得到正確的子圖匹配結(jié)果。

3 背景知識(shí)及問題定義

定義1（特征無向圖）[7]將社會(huì)網(wǎng)絡(luò)表示成節(jié)點(diǎn)帶標(biāo)簽的簡單無向G=(V(G),E(G),T,Γ,L)。（1）V(G)是圖G的節(jié)點(diǎn)的集合；（2）E(G)?V(G)×V(G)是一個(gè)無向邊的集合；（3）T是節(jié)點(diǎn)的類型，每個(gè)節(jié)點(diǎn)只有一種類型；（4）Γ是節(jié)點(diǎn)的特征集合，一個(gè)節(jié)點(diǎn)有一個(gè)或多個(gè)節(jié)點(diǎn)特征，并且節(jié)點(diǎn)的類型不同，節(jié)點(diǎn)的特征也不同；（5）L是節(jié)點(diǎn)的標(biāo)簽集合，每個(gè)節(jié)點(diǎn)特征有一個(gè)或多個(gè)節(jié)點(diǎn)標(biāo)簽。T(V)、Γ(V)、L(V)是節(jié)點(diǎn)的類型、特征和標(biāo)簽。例如在圖1中節(jié)點(diǎn)c1的類型是C（company），節(jié)點(diǎn)s1的類型是S（school），節(jié)點(diǎn)p1的類型是P（person）。對(duì)于任意兩個(gè)不同的節(jié)點(diǎn)V1、V2，如果T(V1)=T(V2)，那么Γ(V1)=Γ(V2)。對(duì)于一個(gè)節(jié)點(diǎn)特征A∈Γ(V)，表示節(jié)點(diǎn)V的特征A的標(biāo)簽。一個(gè)節(jié)點(diǎn)特征或許有多個(gè)標(biāo)簽，例如圖1 中公司類型的特征有互聯(lián)網(wǎng)、軟件、網(wǎng)絡(luò)媒體等標(biāo)簽。

定義2（K-自同構(gòu)圖）[5]如果圖Gk={V(Gk),E(Gk)},并且V(Gk)可以被分割至k個(gè)塊內(nèi)，每塊圖中有個(gè)節(jié)點(diǎn)。任意節(jié)點(diǎn)v有k-1 個(gè)對(duì)應(yīng)節(jié)點(diǎn)在其他塊中，那么這個(gè)圖是K-自同構(gòu)圖。

定義3（K-自同構(gòu)函數(shù)）[5]v是K-自同構(gòu)圖Gk中的一個(gè)節(jié)點(diǎn)，v和它的k-1 個(gè)對(duì)稱節(jié)點(diǎn)組成了序列AVI（alignment vertex instance），所有的序列組成了表AVT（alignment vertex table），AVT表中每一行表示一組AVI，如圖3。基于自同構(gòu)圖Gk的AVT表建立K-自同構(gòu)函數(shù)Fi(i=0,1,…,k-1)。

F0(v)=v

Fi(v)=Fi-1(v).next,for 1≤i≤k-1

Fig.3 AVT table圖3 AVT表

例如在圖3的AVT表中，F(xiàn)0(p1)=p1；F1(p1)=p5。

定義4（子圖匹配）[4]給出一個(gè)圖G=(V(G),E(G),T,Γ,L)，一個(gè)搜索圖Q=(V(Q),E(Q),T,Γ,L)，如果存在至少一個(gè)映射V(Q)→V(G)使得：

（1）?qi∈V(Q),g(qi)∈V(G)?L(qi)?L(g(qi))

（2）?qi,qj∈V(Q),edge qiqj∈E(Q)?

edge g(qi)g(qj)∈E(G)

那么Q是G的同構(gòu)子圖。如果Q是G的同構(gòu)子圖，子圖匹配是找出在圖G中所有與Q同構(gòu)的子圖，這些子圖的集合就是搜索圖Q關(guān)于數(shù)據(jù)圖G的子圖匹配結(jié)果。搜索圖Q關(guān)于數(shù)據(jù)圖G的子圖匹配結(jié)果記為R(Go)。

云計(jì)算提供的服務(wù)主要有兩種：基礎(chǔ)設(shè)施即服務(wù)（infrastructure-as-a-service，IaaS）和軟件即服務(wù)（software-as-a-service，SaaS）。數(shù)據(jù)的擁有者可以將數(shù)據(jù)上傳至云平臺(tái)中進(jìn)行分析。使用合適的算法可以降低數(shù)據(jù)的存儲(chǔ)、分析成本，提高數(shù)據(jù)分析效率。例如在云平臺(tái)中對(duì)數(shù)據(jù)進(jìn)行子圖匹配操作的速度要遠(yuǎn)遠(yuǎn)大于在單機(jī)環(huán)境下對(duì)數(shù)據(jù)進(jìn)行子圖匹配，當(dāng)處理大規(guī)模的圖數(shù)據(jù)時(shí)，這種差異會(huì)更加明顯。

云平臺(tái)會(huì)完全按照使用者提供的要求運(yùn)行，但是數(shù)據(jù)存儲(chǔ)以及運(yùn)行是在第三方提供的云平臺(tái)中，因此對(duì)于數(shù)據(jù)提供者來說存在隱私泄露危險(xiǎn)。使用云平臺(tái)處理數(shù)據(jù)是需要成本消耗并且在云平臺(tái)中處理數(shù)據(jù)會(huì)產(chǎn)生嚴(yán)重的隱私泄露問題。比如節(jié)點(diǎn)再識(shí)別攻擊。如果一個(gè)攻擊者知道云平臺(tái)中上傳圖中節(jié)點(diǎn)t的結(jié)構(gòu)信息，比如節(jié)點(diǎn)的度、一鄰居圖。根據(jù)已經(jīng)掌握的節(jié)點(diǎn)結(jié)構(gòu)信息對(duì)云環(huán)境中的圖進(jìn)行子圖匹配，如果在上傳圖中只有很少的節(jié)點(diǎn)匹配節(jié)點(diǎn)t，那么就可以以較高的概率在上傳圖中識(shí)別節(jié)點(diǎn)t，這樣就會(huì)造成關(guān)于節(jié)點(diǎn)t的敏感信息泄露。

面向子圖匹配的社會(huì)網(wǎng)絡(luò)隱私的目標(biāo)是在云平臺(tái)中進(jìn)行關(guān)于社會(huì)網(wǎng)絡(luò)的子圖匹配時(shí)保護(hù)社會(huì)網(wǎng)絡(luò)的隱私，并在客戶端得到正確子圖匹配結(jié)果。

4 云平臺(tái)中社會(huì)網(wǎng)絡(luò)隱私保護(hù)方法

為了保護(hù)云平臺(tái)中社會(huì)網(wǎng)絡(luò)圖的結(jié)構(gòu)隱私，使用DK-A 算法對(duì)上傳至云平臺(tái)中的社會(huì)網(wǎng)絡(luò)圖進(jìn)行匿名；根據(jù)K-自同構(gòu)圖的對(duì)稱性提出新的上傳方案降低云平臺(tái)中子圖匹配的成本。

4.1 分布式K-自同構(gòu)社會(huì)網(wǎng)絡(luò)隱私保護(hù)算法DK-A

分布式的K-自同構(gòu)算法DK-A 算法的基本思想是：利用Trinity框架[16]相鄰節(jié)點(diǎn)之間可以發(fā)送接收消息的特點(diǎn)，將社會(huì)網(wǎng)絡(luò)圖中的節(jié)點(diǎn)分布存儲(chǔ)于計(jì)算節(jié)點(diǎn)中，通過節(jié)點(diǎn)之間的標(biāo)記信息確定需要添加噪聲邊的節(jié)點(diǎn)。

DK-A算法由三部分構(gòu)成：

（1）使用MLP（multi-level label propagation）算法[17]通過多級(jí)別標(biāo)簽傳遞的方法對(duì)原始圖進(jìn)行分割，根據(jù)分割后的K塊圖得到AVT表；

（2）塊內(nèi)噪聲邊的添加；

（3）塊間噪聲邊的添加。

塊內(nèi)噪聲邊的添加主要基于AVT表的同列內(nèi)相鄰節(jié)點(diǎn)之間發(fā)送標(biāo)記信息。當(dāng)節(jié)點(diǎn)接受到標(biāo)記信息后對(duì)自己進(jìn)行標(biāo)記，并與同行節(jié)點(diǎn)進(jìn)行比較，如果同行有未被標(biāo)記節(jié)點(diǎn)，在此節(jié)點(diǎn)與發(fā)送行同列節(jié)點(diǎn)間添加邊。

算法1塊內(nèi)添加噪聲邊

輸入：AVT；Go。

輸出:Gk′。

塊間噪聲邊的添加主要基于AVT表的不同列相鄰節(jié)點(diǎn)之間發(fā)送標(biāo)記信息。

當(dāng)節(jié)點(diǎn)接收到標(biāo)記信息后對(duì)自己進(jìn)行標(biāo)記，并與同行節(jié)點(diǎn)進(jìn)行比較，如果同行有未被標(biāo)記節(jié)點(diǎn)，根據(jù)K-自同構(gòu)函數(shù)添加塊間邊。

算法2塊間添加噪聲邊

輸入：AVT；Gk′。

輸出:Gk。

DK-A 算法在最壞情況下時(shí)間復(fù)雜度為O(mn),m是AVT表的行數(shù)，n是AVT表的列數(shù)，可以發(fā)現(xiàn)算法需要的執(zhí)行時(shí)間與AVT表的規(guī)格相關(guān)。

例如首先對(duì)圖1進(jìn)行分割，得到如圖3（a）的AVT表；在計(jì)算節(jié)點(diǎn)中的節(jié)點(diǎn)按照AVT表傳遞標(biāo)記信息，如圖3（b），當(dāng)算法循環(huán)至p3節(jié)點(diǎn)所在行時(shí)，s4被標(biāo)記，但是s2未被標(biāo)記，因此添加邊p3s2；當(dāng)塊內(nèi)邊完成添加后，節(jié)點(diǎn)繼續(xù)按照AVT表傳遞信息并添加邊，如圖3（c），循環(huán)至p2所在行時(shí)，發(fā)現(xiàn)p3行只有p7被標(biāo)記。通過K-自同構(gòu)函數(shù)F1(p2)=p6，F(xiàn)1(p7)=p3，添加邊p6p3，當(dāng)塊間邊添加完成后得到2-自同構(gòu)匿名圖如圖2。

4.2 K-自同構(gòu)圖的上傳方案

直接將K-自同構(gòu)圖上傳到云平臺(tái)中會(huì)導(dǎo)致巨大的存儲(chǔ)成本。因此只上傳圖中的一部分和K-自同構(gòu)圖的K-自同構(gòu)函數(shù)Fi(i=0,1,…,k-1)至云平臺(tái)中進(jìn)行子圖匹配。因?yàn)镵-自同構(gòu)圖具有對(duì)稱性，所以在客戶端中仍然可以得到準(zhǔn)確的子圖匹配結(jié)果。這樣可以減少存儲(chǔ)空間，增加匹配速度，大幅降低成本。

定義5（上傳圖）對(duì)于K-自同構(gòu)圖Gk=(V(Gk)，E(Gk),T,Γ,L)，它的上傳圖為Gu=(V(Gu)，E(Gu),T,Γ,L)。（1）V(Gu)是自同構(gòu)圖Gk的第一塊圖中節(jié)點(diǎn)V(B1)和第一塊圖的一鄰居節(jié)點(diǎn)V(N1)的集合；（2）E(Gu)是無向邊E(Gk)的子集，并且它連接了V(B1)內(nèi)的節(jié)點(diǎn)以及V(B1)和V(N1)的節(jié)點(diǎn)，如圖4是圖2的上傳圖，M1～M4表示計(jì)算節(jié)點(diǎn)序號(hào)。

5 分布式子圖匹配方法

分布式的子圖匹配算法由搜索圖的分解、云平臺(tái)中子圖匹配、子圖匹配結(jié)果處理三部分構(gòu)成。

5.1 搜索圖的分解

定義6（搜索分解圖）設(shè)Q是搜索圖，設(shè)S={QSG1,QSG2,…,QSGn}，S是搜索分解圖QSG（query subgraph）的集合。Q的任意邊包含在并且僅包含在一個(gè)QSGi中。稱集合S是搜索圖Q的一個(gè)QSG 覆蓋。

如圖5（a）是一個(gè)搜索圖，表示搜索兩個(gè)有關(guān)系的人，他們的共同點(diǎn)是在北京上學(xué)，他們分別從事于互聯(lián)網(wǎng)和軟件行業(yè)的工作。P、S、C 分別表示的是節(jié)點(diǎn)的類型。

Fig.4 Upload graph Gu圖4 上傳圖Gu

Fig.5 Query graph圖5 搜索圖

QSG是一個(gè)層數(shù)為2的樹結(jié)構(gòu)。記QSG={r,L}，r表示的是根節(jié)點(diǎn)的標(biāo)簽，L是r的孩子節(jié)點(diǎn)的標(biāo)簽的集合，如圖5（b）。

最少Q(mào)SG覆蓋問題的目標(biāo)是找出搜索圖Q的最少Q(mào)SG 覆蓋。很明顯當(dāng)|S|越小時(shí)，子圖匹配結(jié)果所需要的連接次數(shù)越少，子圖匹配速度越快。

定理1最少Q(mào)SG覆蓋問題等價(jià)于最少節(jié)點(diǎn)覆蓋問題。

證明反證法：設(shè)S是Q最少Q(mào)SG 覆蓋，設(shè)V是所有QSGi(1≤i≤n)的根節(jié)點(diǎn)的集合。任意一邊至少與集合V中的一節(jié)點(diǎn)相連，因此V是Q的節(jié)點(diǎn)覆蓋。假設(shè)這里存在其他的覆蓋V，使|V′|<|V|，建立一個(gè)由集合V中節(jié)點(diǎn)做根節(jié)點(diǎn)的集合S，且v∈V′，使搜索圖內(nèi)與節(jié)點(diǎn)v相關(guān)的邊與節(jié)點(diǎn)v共同組成一個(gè)QSG。隨機(jī)刪除QSGs中的邊直到任意邊只屬于一個(gè)QSG，這樣集合S′中的QSG 都至少含有一條邊。很明顯|S′|≤|V′|<|V|=|S|，這說明S不是最少Q(mào)SG覆蓋?！?/p>

最少節(jié)點(diǎn)覆蓋問題是經(jīng)典的NP-hard 問題。根據(jù)定理1，最少Q(mào)SG 覆蓋問題也是NP-hard 問題。2-approximate算法是一個(gè)處理最少節(jié)點(diǎn)覆蓋問題的經(jīng)典算法。這個(gè)算法在每步隨機(jī)選擇一條邊(u,v)，將u、v加入結(jié)果集中，并在原圖刪除所有與u、v相連的邊，重復(fù)以上步驟直到圖中的邊都被刪除。對(duì)這個(gè)經(jīng)典算法進(jìn)行改進(jìn)，使這個(gè)算法適用于最少Q(mào)SG覆蓋問題。

算法主要修改了邊的選擇方法，通過節(jié)點(diǎn)的選擇度選擇邊進(jìn)行QSG 覆蓋。設(shè)函數(shù)表示節(jié)點(diǎn)的選擇度，deg(v)表示節(jié)點(diǎn)v的度，freq(v)表示節(jié)點(diǎn)v的標(biāo)簽在數(shù)據(jù)圖中出現(xiàn)的次數(shù)。

算法3搜索圖分解

輸入：Q。

輸出:QSGs。

如圖5 所示。首先選擇q2q3邊，因?yàn)閒(q2)=3,f(q3)=3,f(q2)+f(q3)值最高；然后產(chǎn)生QSG1={q2,(q1,q3,q4)}和QSG2={q3,(q1,q5)}。

定理2算法3 得到的QSG 的個(gè)數(shù)最多是最少Q(mào)SG覆蓋問題最優(yōu)解的兩倍。

證明設(shè)H*是最優(yōu)QSG覆蓋集合。設(shè)E是算法選擇的邊的集合。因?yàn)樵诩螮中的邊沒有公共點(diǎn)并且在一個(gè)QSG 中的所有邊一點(diǎn)存在一個(gè)公共點(diǎn)，因此每個(gè)QSG最多包含一條集合E中的邊。這表示|E|≤|H|。對(duì)于每條邊e∈E，最多會(huì)產(chǎn)生兩個(gè)QSG，因此|H|≤2|E|≤2|H*|。 □

5.2 云平臺(tái)中子圖匹配算法

子圖匹配需要對(duì)QSGs 的標(biāo)簽進(jìn)行泛化防止泄露隱私。在計(jì)算節(jié)點(diǎn)中對(duì)QSGs依次進(jìn)行算法3的子圖匹配操作。

算法4子圖匹配

輸入：QSGs，QSG={r,L};Gu'。

輸出：R。

1.Sr←Index.getID(r)/*找到標(biāo)簽為r的節(jié)點(diǎn)ID*/

2.R=?；

3.for eachninSrdo

4.c=Cloud.Load(n)/*載入節(jié)點(diǎn)ID為n

5.for eachliinLdo

7.R=R∪{{n}×Sl1×Sl2×…×Slk}；

8.ReturnR；

例如圖6 是圖5 中QSGs 在上傳圖圖4 中的匹配結(jié)果。

所有計(jì)算節(jié)點(diǎn)內(nèi)關(guān)于QSGs 的子圖匹配結(jié)果進(jìn)行連接得到最后的子圖匹配結(jié)果。例如將圖6 中所有結(jié)果連接后得到子圖匹配結(jié)果Rin，如圖7。

5.3 子圖匹配結(jié)果處理

Fig.6 Subgraph matching result of QSG圖6 搜索分解子圖匹配結(jié)果

Fig.7 Subgraph matching result Rin圖7 子圖匹配結(jié)果Rin

得到關(guān)于上傳圖Gu的子圖匹配結(jié)果不是完整K-自同構(gòu)圖的子圖匹配結(jié)果。將已經(jīng)得到的結(jié)果和云平臺(tái)中存儲(chǔ)的K-自同構(gòu)函數(shù)下載到客戶端。使用K-自同構(gòu)函數(shù)將下載到的結(jié)果恢復(fù)成關(guān)于K-自同構(gòu)圖的子圖匹配的結(jié)果。例如使用圖7的結(jié)果Rin并根據(jù)圖3的AVT表得到F1(c1)=c3,F1(p2)=p6,F1(p3)=p7,F1(c2)=c4,F1(s1)=s3，得到如圖8 的映射結(jié)果Rout。R(Gk)=Rin∪Rout是關(guān)于K-自同構(gòu)圖的子圖匹配結(jié)果。因此圖7和圖8是關(guān)于匿名圖的子圖匹配結(jié)果。

Fig.8 Mapping result Rout圖8 映射結(jié)果Rout

定理3設(shè)關(guān)于原始圖Go，K-自同構(gòu)圖Gk的子圖匹配結(jié)果R(Go)、R(Gk),R(Go)?R(Gk)。

關(guān)于K-自同構(gòu)圖的子圖匹配結(jié)果R(Gk)與在關(guān)于原始圖Go的子圖匹配結(jié)果R(Go)不同。由于對(duì)原始圖邊的添加使子圖匹配結(jié)果有可能增多。對(duì)于數(shù)據(jù)的擁有者來說，這造成了信息的可用性下降。因此客戶端在得到子圖匹配結(jié)果后，還應(yīng)進(jìn)行子圖匹配結(jié)果過濾，刪除含有在原始圖中不存在的節(jié)點(diǎn)或邊的子圖匹配結(jié)果；刪除節(jié)點(diǎn)標(biāo)簽與搜索圖中對(duì)應(yīng)節(jié)點(diǎn)標(biāo)簽不同的子圖匹配結(jié)果。

算法5匹配結(jié)果過濾

輸出：R(Gk),Go。

輸出:R(Go)。

例如在圖8 中，p7s3這條邊在原始圖中不存在，因此正確的子圖匹配結(jié)果為圖7的Rin。

6 實(shí)驗(yàn)與結(jié)果

在本章中對(duì)DK-A 隱私保護(hù)算法和子圖匹配方法的效率進(jìn)行實(shí)驗(yàn)分析。

6.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)采用真實(shí)數(shù)據(jù)集roadNet-CA和roadNet-PA。roadNet-CA 包含總共1 965 206 個(gè)節(jié)點(diǎn)和2 766 607條邊；roadNet-PA 包含1 088 092 個(gè)節(jié)點(diǎn)和1 541 898條邊。兩個(gè)數(shù)據(jù)集不含有標(biāo)簽，因此每個(gè)數(shù)據(jù)集中人工生成三種標(biāo)簽。

6.2 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)使用8 臺(tái)計(jì)算節(jié)點(diǎn)搭建的集群作為計(jì)算平臺(tái)。硬件配置為CPU 1.80 Hz，RAM 16 GB。實(shí)驗(yàn)使用WindowsServer2008 R2系統(tǒng)的Trinity計(jì)算框架實(shí)現(xiàn)。

6.3 實(shí)驗(yàn)結(jié)果

圖9展示了DK-A算法在8臺(tái)計(jì)算節(jié)點(diǎn)下的對(duì)原始圖的匿名時(shí)間。可以看出隨著K值增加，匿名時(shí)間增加。原因是因?yàn)楫?dāng)K值增加時(shí)，匿名圖需要添加的噪聲邊增多，因此算法運(yùn)行時(shí)間隨K值增大而增大。

Fig.9 Running time of DK-A algorithm圖9 DK-A算法運(yùn)行時(shí)間

如圖10 是當(dāng)計(jì)算節(jié)點(diǎn)為8 時(shí)，使用數(shù)據(jù)集roadNet-PA，DK-A 算法與傳統(tǒng)算法K-automorphism的運(yùn)行時(shí)間對(duì)比?？梢园l(fā)現(xiàn)分布并行算法與傳統(tǒng)算法對(duì)比運(yùn)行時(shí)間成本大幅度減少。

如圖11 是DK-A 算法的相對(duì)加速比。相對(duì)加速比公式為T(N)表示計(jì)算節(jié)點(diǎn)為N時(shí)的算法運(yùn)行時(shí)間。從圖11可以看出，DK-A算法具有很好的加速比。

圖12 將兩個(gè)數(shù)據(jù)集分割成5 份，按照1∶2∶3∶4∶5 重新組合成數(shù)據(jù)切片Split_1～Split_5。通過處理數(shù)據(jù)切片時(shí)間比評(píng)測算法的可擴(kuò)展性：

Fig.10 Running time comparison of algorithms圖10 算法運(yùn)行時(shí)間對(duì)比

Fig.11 Speedup ratio of DK-A algorithm圖11 DK-A算法的加速比

Fig.12 Scalability of DK-A algorithm圖12 DK-A算法的擴(kuò)展性

Scalability在理想狀態(tài)下不應(yīng)大于i，但是在Split_4之后出現(xiàn)了值大于i的情況，這是因?yàn)樗惴ǖ男阅苁艿焦?jié)點(diǎn)通信時(shí)間影響。

如圖13對(duì)比了完全匿名圖和上傳圖需要的空間大小。發(fā)現(xiàn)上傳圖可以節(jié)省大量的空間成本，同時(shí)隨著K的增加，上傳圖占用的空間越來越大，因?yàn)殡S著K值的增加，匿名圖需要添加的噪聲邊變多，所以上傳圖的空間成本變得越來越大。

Fig.13 Space cost of upload graph圖13 上傳圖的占用空間

圖14 是當(dāng)上傳圖是2-自同構(gòu)匿名圖的上傳圖，搜索圖節(jié)點(diǎn)數(shù)為4 時(shí)，進(jìn)行子圖匹配所需要的時(shí)間。可以看出在云平臺(tái)下，子圖匹配的速度非常快。

Fig.14 Subgraph matching time about number of compute nodes圖14 子圖匹配時(shí)間關(guān)于計(jì)算節(jié)點(diǎn)數(shù)

如圖15 是當(dāng)上傳圖是2-自同構(gòu)匿名圖的上傳圖，使用8臺(tái)計(jì)算節(jié)點(diǎn)時(shí)，隨著搜索圖的節(jié)點(diǎn)增加，子圖匹配時(shí)間增加。因?yàn)楫?dāng)搜索圖節(jié)點(diǎn)數(shù)增加時(shí)，QSGs的數(shù)量增多，導(dǎo)致QSGs匹配結(jié)果增加，需要更多的連接操作時(shí)間。

Fig.15 Subgraph matching time about number of query graph nodes圖15 子圖匹配時(shí)間關(guān)于搜索圖節(jié)點(diǎn)數(shù)

圖16 說明恢復(fù)子圖匹配結(jié)果所占用時(shí)間很少，幾乎不會(huì)影響子圖匹配所需要的總時(shí)間。

Fig.16 Recovery time of subgraph matching result圖16 子圖匹配結(jié)果恢復(fù)時(shí)間

7 結(jié)束語

傳統(tǒng)社會(huì)網(wǎng)絡(luò)隱私保護(hù)算法會(huì)對(duì)原始圖進(jìn)行大量修改，使得對(duì)7匿名圖進(jìn)行子圖匹配得到的結(jié)果不準(zhǔn)確。為此提出了DK-A 算法及分布式子圖匹配方法。這樣在保護(hù)上傳圖隱私的前提下，通過利用K-自同構(gòu)圖的對(duì)稱性，得到匿名圖子圖匹配結(jié)果，對(duì)子圖匹配結(jié)果恢復(fù)和過濾，得到正確的子圖匹配結(jié)果。

通過利用K-自同構(gòu)匿名圖的對(duì)稱性達(dá)到了在保護(hù)上傳圖隱私前提下，保證了子圖匹配結(jié)果的準(zhǔn)確性。下一步可以繼續(xù)研究利用其他匿名圖特性，來達(dá)到保證子圖匹配結(jié)果準(zhǔn)確性目的的子圖匹配方法。