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

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

1 引言

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

可以看出K-自同構算法能很好地抵御結構攻擊。但這種方法因為添加了噪聲邊，導致了子圖匹配結果的不準確以及在云平臺中進行子圖匹配大量的空間時間消耗。

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

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

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

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

2 相關工作

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

Fig.2 2-automorphism anonymous graph of original graph圖2 原始圖的2-自同構匿名圖

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

文獻[14]提出LP（linear programming）模型可以匿名權重社會網(wǎng)絡圖并且保留圖中節(jié)點間的最短路徑，但是攻擊者具有任意拓撲背景信息時可以對匿名圖進行重識別，而且不能保護客戶端內(nèi)子圖匹配結果的準確。文獻[7，15]提出了保護子圖匹配結果正確性的社會網(wǎng)絡隱私保護方法，這些思想通過使用圖的索引進行子圖匹配，保證結果的正確性但是不適用于大規(guī)模社會網(wǎng)絡環(huán)境。

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

3 背景知識及問題定義

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

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

定義3（K-自同構函數(shù)）[5]v是K-自同構圖Gk中的一個節(jié)點，v和它的k-1 個對稱節(jié)點組成了序列AVI（alignment vertex instance），所有的序列組成了表AVT（alignment vertex table），AVT表中每一行表示一組AVI，如圖3?；谧酝瑯媹DGk的AVT表建立K-自同構函數(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=(V(G),E(G),T,Γ,L)，一個搜索圖Q=(V(Q),E(Q),T,Γ,L)，如果存在至少一個映射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的同構子圖。如果Q是G的同構子圖，子圖匹配是找出在圖G中所有與Q同構的子圖，這些子圖的集合就是搜索圖Q關于數(shù)據(jù)圖G的子圖匹配結果。搜索圖Q關于數(shù)據(jù)圖G的子圖匹配結果記為R(Go)。

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

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

面向子圖匹配的社會網(wǎng)絡隱私的目標是在云平臺中進行關于社會網(wǎng)絡的子圖匹配時保護社會網(wǎng)絡的隱私，并在客戶端得到正確子圖匹配結果。

4 云平臺中社會網(wǎng)絡隱私保護方法

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

4.1 分布式K-自同構社會網(wǎng)絡隱私保護算法DK-A

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

DK-A算法由三部分構成：

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

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

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

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

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

輸入：AVT；Go。

輸出:Gk′。

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

當節(jié)點接收到標記信息后對自己進行標記，并與同行節(jié)點進行比較，如果同行有未被標記節(jié)點，根據(jù)K-自同構函數(shù)添加塊間邊。

算法2塊間添加噪聲邊

輸入：AVT；Gk′。

輸出:Gk。

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

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

4.2 K-自同構圖的上傳方案

直接將K-自同構圖上傳到云平臺中會導致巨大的存儲成本。因此只上傳圖中的一部分和K-自同構圖的K-自同構函數(shù)Fi(i=0,1,…,k-1)至云平臺中進行子圖匹配。因為K-自同構圖具有對稱性，所以在客戶端中仍然可以得到準確的子圖匹配結果。這樣可以減少存儲空間，增加匹配速度，大幅降低成本。

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

5 分布式子圖匹配方法

分布式的子圖匹配算法由搜索圖的分解、云平臺中子圖匹配、子圖匹配結果處理三部分構成。

5.1 搜索圖的分解

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

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

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

Fig.5 Query graph圖5 搜索圖

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

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

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

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

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

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

算法3搜索圖分解

輸入：Q。

輸出:QSGs。

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

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

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

5.2 云平臺中子圖匹配算法

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

算法4子圖匹配

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

輸出：R。

1.Sr←Index.getID(r)/*找到標簽為r的節(jié)點ID*/

2.R=?；

3.for eachninSrdo

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

5.for eachliinLdo

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

8.ReturnR；

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

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

5.3 子圖匹配結果處理

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

Fig.7 Subgraph matching result Rin圖7 子圖匹配結果Rin

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

Fig.8 Mapping result Rout圖8 映射結果Rout

定理3設關于原始圖Go，K-自同構圖Gk的子圖匹配結果R(Go)、R(Gk),R(Go)?R(Gk)。

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

算法5匹配結果過濾

輸出：R(Gk),Go。

輸出:R(Go)。

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

6 實驗與結果

在本章中對DK-A 隱私保護算法和子圖匹配方法的效率進行實驗分析。

6.1 實驗數(shù)據(jù)集

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

6.2 實驗環(huán)境

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

6.3 實驗結果

圖9展示了DK-A算法在8臺計算節(jié)點下的對原始圖的匿名時間?？梢钥闯鲭S著K值增加，匿名時間增加。原因是因為當K值增加時，匿名圖需要添加的噪聲邊增多，因此算法運行時間隨K值增大而增大。

Fig.9 Running time of DK-A algorithm圖9 DK-A算法運行時間

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

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

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

Fig.10 Running time comparison of algorithms圖10 算法運行時間對比

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

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

Scalability在理想狀態(tài)下不應大于i，但是在Split_4之后出現(xiàn)了值大于i的情況，這是因為算法的性能受到節(jié)點通信時間影響。

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

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

圖14 是當上傳圖是2-自同構匿名圖的上傳圖，搜索圖節(jié)點數(shù)為4 時，進行子圖匹配所需要的時間?？梢钥闯鲈谠破脚_下，子圖匹配的速度非?？?。

Fig.14 Subgraph matching time about number of compute nodes圖14 子圖匹配時間關于計算節(jié)點數(shù)

如圖15 是當上傳圖是2-自同構匿名圖的上傳圖，使用8臺計算節(jié)點時，隨著搜索圖的節(jié)點增加，子圖匹配時間增加。因為當搜索圖節(jié)點數(shù)增加時，QSGs的數(shù)量增多，導致QSGs匹配結果增加，需要更多的連接操作時間。

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

圖16 說明恢復子圖匹配結果所占用時間很少，幾乎不會影響子圖匹配所需要的總時間。

Fig.16 Recovery time of subgraph matching result圖16 子圖匹配結果恢復時間

7 結束語

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

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