大規(guī)模社會(huì)網(wǎng)絡(luò)K-出入度匿名方法

張曉琳,劉 嬌,畢紅凈,李 健,王永平

(1.內(nèi)蒙古科技大學(xué) 信息工程學(xué)院,內(nèi)蒙古 包頭 014010; 2.唐山師范學(xué)院 計(jì)算機(jī)科學(xué)系,河北 唐山 063000)

0 概述

隨著社會(huì)網(wǎng)絡(luò)的發(fā)展以及各種社交App的快速普及,網(wǎng)絡(luò)用戶人數(shù)不斷增加。目前,Facebook用戶總數(shù)約為21.7億,微信用戶總數(shù)約為9.8億,截至2018年3月31日,支付寶為約8.7億位活躍用戶提供服務(wù)。用戶在使用社會(huì)網(wǎng)絡(luò)的過程中產(chǎn)生了大量社會(huì)網(wǎng)絡(luò)數(shù)據(jù),對(duì)于實(shí)際社會(huì)網(wǎng)絡(luò)有向圖,一些具有相同愛好或者相似屬性的用戶還會(huì)形成各種特定的群體,即社會(huì)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。因此,對(duì)大規(guī)模社會(huì)網(wǎng)絡(luò)有向圖發(fā)布時(shí)的社區(qū)結(jié)構(gòu)進(jìn)行分析具有重要意義。文獻(xiàn)[1]指出由于社會(huì)網(wǎng)絡(luò)具有結(jié)構(gòu)特征,簡(jiǎn)單的刪除標(biāo)識(shí)屬性不能防止攻擊者通過其他背景知識(shí)識(shí)別出目標(biāo)用戶。因此,研究人員針對(duì)不同的隱私信息提出了不同的隱私保護(hù)模型,如圖修改模型[2-4]、聚類泛化模型[5-6]、數(shù)據(jù)擾動(dòng)模型[7]和差分隱私模型[8]等。但是,目前大部分隱私保護(hù)技術(shù)僅針對(duì)社會(huì)網(wǎng)絡(luò)無向圖來保護(hù)個(gè)人隱私信息,忽略了對(duì)社會(huì)網(wǎng)絡(luò)有向圖社區(qū)結(jié)構(gòu)的保護(hù)。

為滿足K-出入度匿名并有效保護(hù)大規(guī)模社會(huì)網(wǎng)絡(luò)有向圖的社區(qū)結(jié)構(gòu),本文基于GraphX圖數(shù)據(jù)處理平臺(tái),建立基于層次社區(qū)結(jié)構(gòu)的大規(guī)模社會(huì)網(wǎng)絡(luò)K-出入度匿名模型,并提出一種K-出入度匿名(KIODA)算法。

1 相關(guān)工作

目前,社會(huì)網(wǎng)絡(luò)隱私保護(hù)信息主要包括節(jié)點(diǎn)隱私、邊隱私和圖性質(zhì)隱私3種[9]。針對(duì)不同的社會(huì)網(wǎng)絡(luò)隱私保護(hù)信息,文獻(xiàn)[7]提出一種新的匿名方法,即拆分匿名化,通過拆分匿名處理的社交網(wǎng)絡(luò)可以抵御直接攻擊。文獻(xiàn)[10]提出無向圖的k-度匿名概念,其要求圖中任何節(jié)點(diǎn)都至少有k-1個(gè)節(jié)點(diǎn)與其度數(shù)相同,使用貪心策略增加邊來實(shí)現(xiàn)匿名,從而抵御節(jié)點(diǎn)度屬性攻擊。文獻(xiàn)[11]提出一種UMGA算法,其采用貪心算法和窮舉法生成匿名度序列,通過隨機(jī)邊選擇和鄰居中心性邊選擇方法修改無向圖從而實(shí)現(xiàn)k-度匿名。文獻(xiàn)[12]提出一種改進(jìn)的K-度匿名算法,該算法保留了個(gè)人隱私信息以及社交網(wǎng)絡(luò)結(jié)構(gòu)屬性。文獻(xiàn)[13]提出一種圖形結(jié)構(gòu)感知的分層k-匿名技術(shù),其根據(jù)冪律分布的特征劃分節(jié)點(diǎn),在隱私保護(hù)過程中分析圖形的結(jié)構(gòu)特征,根據(jù)圖形結(jié)構(gòu)特征調(diào)整邊緣。文獻(xiàn)[14]提出一種保持網(wǎng)絡(luò)結(jié)構(gòu)穩(wěn)定性的k-度匿名隱私保護(hù)模型SimilarGraph,該模型運(yùn)用動(dòng)態(tài)規(guī)劃方法對(duì)社會(huì)網(wǎng)絡(luò)按照節(jié)點(diǎn)度序列進(jìn)行最優(yōu)簇劃分,通過移動(dòng)邊操作方式重構(gòu)網(wǎng)絡(luò)圖以實(shí)現(xiàn)圖的k-度匿名化。文獻(xiàn)[15]針對(duì)有向圖提出了可達(dá)性保持圖匿名化方法,通過圖修改來防止隱私泄露,同時(shí)保證匿名圖在社會(huì)網(wǎng)絡(luò)分析和圖查詢方面的數(shù)據(jù)可用性。文獻(xiàn)[16]提出一種保護(hù)鏈接關(guān)系的分布式匿名方法PLRD-(k,m),其將互為N-hop鄰居的節(jié)點(diǎn)分為一組并進(jìn)行k-度匿名和m-標(biāo)簽?zāi)涿?保證攻擊者無法通過度和標(biāo)簽識(shí)別出目標(biāo)并保護(hù)鏈接關(guān)系不被泄露?，F(xiàn)有的隱私保護(hù)方法雖然減少了圖修改的信息損失,但改變了原始圖的網(wǎng)絡(luò)連通性,在匿名過程中沒有考慮社會(huì)網(wǎng)絡(luò)圖的社區(qū)結(jié)構(gòu),從而影響了社區(qū)結(jié)構(gòu)的性質(zhì)分析并降低了所發(fā)布數(shù)據(jù)的使用價(jià)值。

在進(jìn)行大規(guī)模社會(huì)網(wǎng)絡(luò)隱私保護(hù)的同時(shí)保護(hù)社會(huì)網(wǎng)絡(luò)圖的社區(qū)結(jié)構(gòu)成為國內(nèi)外學(xué)者關(guān)注的熱點(diǎn)。文獻(xiàn)[17]在保持總體圖譜不變的前提下,通過節(jié)點(diǎn)之間相似度的比較來隨機(jī)增刪k條邊。文獻(xiàn)[18]利用基于圖分割理論的社區(qū)劃分算法計(jì)算拉普拉斯矩陣,設(shè)置譜約束條件,從而計(jì)算增刪邊的約束。文獻(xiàn)[19]提出一種局部擾動(dòng)的k-匿名技術(shù),在節(jié)點(diǎn)分組時(shí)使屬于相同社區(qū)的節(jié)點(diǎn)分到一個(gè)組內(nèi),根據(jù)節(jié)點(diǎn)相似性重構(gòu)社會(huì)網(wǎng)絡(luò)無向圖。文獻(xiàn)[20]利用粗糙集的上近似概念劃分社區(qū)并進(jìn)行匿名,匿名前后保持圖的社區(qū)結(jié)構(gòu)性質(zhì)。文獻(xiàn)[21]提出一種新的邊緣修改技術(shù),對(duì)圖表進(jìn)行匿名化時(shí)較好地保留了圖形社區(qū)結(jié)構(gòu),匿名后社會(huì)網(wǎng)絡(luò)K核數(shù)保持不變,即保持社區(qū)結(jié)構(gòu)不變。

目前,多數(shù)社會(huì)網(wǎng)絡(luò)隱私保護(hù)方法存在處理大規(guī)模社會(huì)網(wǎng)絡(luò)有向圖時(shí)數(shù)據(jù)效率低、忽略了對(duì)社會(huì)網(wǎng)絡(luò)有向圖社區(qū)結(jié)構(gòu)進(jìn)行保護(hù)的問題,因此,本文提出一種基于層次社區(qū)結(jié)構(gòu)的KIODA算法,以提高數(shù)據(jù)處理效率并保證數(shù)據(jù)發(fā)布時(shí)社區(qū)結(jié)構(gòu)分析結(jié)果的可用性。

2 預(yù)備知識(shí)與問題定義

將社會(huì)網(wǎng)絡(luò)表示為有向圖G=(V,E),其中,V(G)和E(G)分別表示圖G的節(jié)點(diǎn)集合和邊集合。邊表示從節(jié)點(diǎn)u指向v的一條邊,邊稱為u的出邊、v的入邊,節(jié)點(diǎn)u的入邊數(shù)目是u的入度數(shù),記作din(u),節(jié)點(diǎn)u的出邊數(shù)目是u的出度數(shù),記作dout(u),節(jié)點(diǎn)u的出入度用(din(u),dout(u))表示。

2.1 基于層次社區(qū)結(jié)構(gòu)的社區(qū)劃分

(1)

社會(huì)網(wǎng)絡(luò)有向圖G的HRG不是唯一的,因此,選擇最優(yōu)的HRG,進(jìn)而根據(jù)有向圖層次社區(qū)樹HG得到社會(huì)網(wǎng)絡(luò)有向圖的社區(qū)結(jié)構(gòu)。對(duì)于不同的HRG,可以采用似然函數(shù)L來評(píng)價(jià)其對(duì)社會(huì)網(wǎng)絡(luò)有向圖G的合適程度。

定義2(似然函數(shù)L) 似然函數(shù)L是社會(huì)網(wǎng)絡(luò)有向圖G產(chǎn)生HG的后驗(yàn)函數(shù),選取L值最大的HRG樹作為有向圖G的HG。L的計(jì)算公式為:

(2)

圖1(a)所示為社會(huì)網(wǎng)絡(luò)有向圖G0,圖1(b)～圖1(d)為社會(huì)網(wǎng)絡(luò)有向圖G0的3個(gè)可能HRG。

圖1 G0的社區(qū)劃分示意圖Fig.1 Community division schematic diagram of G0

圖2 有向圖G0的社區(qū)劃分結(jié)果Fig.2 Community division results of directed graph G0

2.2 大規(guī)模社會(huì)網(wǎng)絡(luò)K-出入度匿名模型

在社會(huì)網(wǎng)絡(luò)無向圖中,攻擊者可以通過度攻擊識(shí)別出目標(biāo)節(jié)點(diǎn),但是對(duì)于社會(huì)網(wǎng)絡(luò)有向圖,節(jié)點(diǎn)具有出度數(shù)和入度數(shù)。因此,本文構(gòu)建一種出入度攻擊模型。

定義3(出入度攻擊) 假設(shè)攻擊者知道目標(biāo)節(jié)點(diǎn)的入(出)度數(shù),或者同時(shí)知道入度數(shù)和出度數(shù),攻擊者通過這些背景知識(shí)能夠識(shí)別出唯一目標(biāo)節(jié)點(diǎn),這種攻擊被稱為出入度攻擊。

如圖3所示,假設(shè)攻擊者知道目標(biāo)節(jié)點(diǎn)的出度數(shù)為2,可以識(shí)別出Alice、Kayla和Bob。如果攻擊者還知道目標(biāo)節(jié)點(diǎn)的入度數(shù)為1,則能識(shí)別出唯一目標(biāo)節(jié)點(diǎn)Alice,導(dǎo)致Alice節(jié)點(diǎn)的隱私信息泄露。

圖3 社會(huì)網(wǎng)絡(luò)有向圖GFig.3 Social network directed graph G

傳統(tǒng)的K-度匿名技術(shù)僅針對(duì)社會(huì)網(wǎng)絡(luò)無向圖,忽略了邊的方向性,但是實(shí)際的社會(huì)網(wǎng)絡(luò)圖中的邊存在方向,因此,本文針對(duì)社會(huì)網(wǎng)絡(luò)有向圖抵御出入度攻擊,構(gòu)造K-出入度序列進(jìn)行K-出入度匿名。

定義4(K-出入度匿名) 給定社會(huì)網(wǎng)絡(luò)有向圖G=(V,E)和正整數(shù)K,對(duì)于有向圖中任意節(jié)點(diǎn)v∈V(G),均存在m(m≥K-1)個(gè)其他節(jié)點(diǎn)與節(jié)點(diǎn)v的入度數(shù)和出度數(shù)相等,即din(v)=din(vi),dout(v)=dout(vi)(1≤i≤m),則稱有向圖G為K-出入度匿名圖。

定義5(基于層次社區(qū)結(jié)構(gòu)的大規(guī)模社會(huì)網(wǎng)絡(luò)K-出入度匿名模型) 給定社會(huì)網(wǎng)絡(luò)有向圖G=(V,E)和正整數(shù)K。根據(jù)如下3個(gè)步驟得到的匿名社會(huì)網(wǎng)絡(luò)有向圖G*=(V*,E*),即符合基于層次社區(qū)結(jié)構(gòu)的大規(guī)模社會(huì)網(wǎng)絡(luò)K-出入度匿名模型:

1)基于層次社區(qū)結(jié)構(gòu)劃分社區(qū),確定原始社會(huì)網(wǎng)絡(luò)有向圖G中節(jié)點(diǎn)所屬的社區(qū)。

2)對(duì)社會(huì)網(wǎng)絡(luò)有向圖G中節(jié)點(diǎn)的出入度序列進(jìn)行排序、分組并匿名,得到K-出入度匿名序列。

3)根據(jù)K-出入度匿名序列分布并行構(gòu)造匿名圖,基于GraphX傳遞節(jié)點(diǎn)間信息并迭代進(jìn)行虛擬節(jié)點(diǎn)對(duì)合并與刪除,提高數(shù)據(jù)發(fā)布時(shí)社區(qū)結(jié)構(gòu)分析結(jié)果的可用性。

如圖4所示,有向圖G*為社會(huì)網(wǎng)絡(luò)有向圖G的3-出入度匿名圖,其中,K=3,節(jié)點(diǎn)1～節(jié)點(diǎn)7屬于社區(qū)1,節(jié)點(diǎn)8～節(jié)點(diǎn)11屬于社區(qū)2,節(jié)點(diǎn)12～節(jié)點(diǎn)14屬于社區(qū)3。對(duì)于任意節(jié)點(diǎn)v,均存在至少2個(gè)節(jié)點(diǎn)與其具有相同的入度數(shù)和出度數(shù),即攻擊者不能以大于1/3的概率唯一識(shí)別出目標(biāo)節(jié)點(diǎn),從而滿足了K-出入度匿名并保證了數(shù)據(jù)發(fā)布時(shí)社區(qū)結(jié)構(gòu)分析結(jié)果的高可用性。

圖4 匿名社會(huì)網(wǎng)絡(luò)有向圖G*Fig.4 Anonymous social network directed graph G*

3 K-出入度匿名算法

基于層次社區(qū)結(jié)構(gòu)的大規(guī)模社會(huì)網(wǎng)絡(luò)K-出入度匿名算法KIODA結(jié)合了為大規(guī)模數(shù)據(jù)處理而設(shè)計(jì)的計(jì)算引擎Spark,算法在分布式并行環(huán)境下執(zhí)行,對(duì)大規(guī)模社會(huì)網(wǎng)絡(luò)數(shù)據(jù)實(shí)現(xiàn)并行高效的隱私保護(hù)。

3.1 基于層次社區(qū)結(jié)構(gòu)的社區(qū)劃分算法

基于層次社區(qū)結(jié)構(gòu)的社區(qū)劃分算法首先得到社會(huì)網(wǎng)絡(luò)有向圖的HRG,然后借助馬爾科夫蒙特卡洛抽樣方法[22]收斂篩選出較優(yōu)的層次隨機(jī)圖HG,進(jìn)而得到社會(huì)網(wǎng)絡(luò)圖的社區(qū)結(jié)構(gòu)。HRG生成算法描述如下:

算法1Construst_HRG(G,ε1)算法

輸入原始圖G,差分隱私參數(shù)ε1

輸出HG

1.根據(jù)Markov chain隨機(jī)生成原始圖G的一個(gè)HRG,作為T0;

2.t←1;

3.while Markov chain is not converged do

4.Randomly select an internal node n in Tt-1

5.Generate HRG T′ by randomly transforming

adjacent subtrees of node n

//通過隨機(jī)交換節(jié)點(diǎn)n的相鄰HRG生成T′

6.if the probability of transformation satisfies

7.Tt=T′;

8.else

9.Tt=Tt-1;

10.end if

11.t=t+1;

12.end while

13.return HG=Tt;

圖5 基于層次結(jié)構(gòu)的社區(qū)劃分示意圖Fig.5 Community division schematic diagram based on hierarchical structure

3.2 K-出入度序列分組匿名算法

針對(duì)社會(huì)網(wǎng)絡(luò)有向圖,本文提出Sequence Partition(G,k)算法,同一組中目標(biāo)出入度的入(出)度數(shù)為該分組中所有入(出)度數(shù)的最大值,即goal(in_deg,out_deg)=(max{分組中所有元素的in_deg},max{分組中所有元素的out_deg})。K-出入度序列分組匿名算法描述如下:

算法2Sequence Partition(G,k)算法

輸入原始有向圖G,匿名參數(shù)k

輸出K-出入度匿名序列d～

1.MF_Seq=[];

2.for each node do

3.Insert in MF_Seq;

4.end for

5.Sort(MF_Seq) by ;

6.last_partition_index=0;

7.for vi∈MF_Seq do

8.for l=last to i-1 do

9.goal_1(in_deg,out_deg)=max(in_deg[i],out_deg[i]);

10.end for

11.for m=i to i+k do

12.goal_2(in_deg,out_deg)=max(in_deg[m+1],out_deg[m+1]);

13.goal_3(in_deg,out_deg)=max(in_deg[m],out_deg[l]);

14.end for

15.SPC1=goal_1-MF_Seq[i],SPC2=0;

16.for j=i+1 to i+k do

17.SPC1=SPC1+goal_3-deg[j-1];

18.SPC2=SPC2+goal_2-deg[j];

19.end for

20.if SPC2

21.last_partition_index=i;

22.i=i+k;

23.else

24.i++;

25.end if

26.end for

算法2第2行～第14行根據(jù)節(jié)點(diǎn)出入度進(jìn)行排序,求出目標(biāo)出入度。第16行～第25行判斷SPC1、SPC2值的大小并進(jìn)行分組。其中,SPC1表示將當(dāng)前元素合并到上一組中的匿名化成本,SPC2表示將當(dāng)前元素和后面k-1個(gè)元素形成新組的成本。如果SPC2

圖6 分組匿名過程Fig.6 Group anonymity process

圖6(a)表示初始出入度序列d。假設(shè)k=3,前3個(gè)元素先被放入一個(gè)組中,如圖6(b)所示。判斷第4個(gè)元素的分組情況,如圖6(c)所示,此時(shí)goal_1=(3,3),goal_2=(2,3),goal_3=(2,3),SPC1=cost1+cost2=3,SPC2=cost3=1。SPC1>SPC2,因此,第4個(gè)元素和后面2個(gè)元素形成新組,再判斷第7個(gè)元素的分組情況。最終分組結(jié)果如圖6(d)所示,得到的K-出入度匿名序列d～如圖6(e)所示。

3.3 選擇虛擬節(jié)點(diǎn)對(duì)合并刪除算法

根據(jù)K-出入度匿名序列分布并行構(gòu)造匿名圖,添加虛擬節(jié)點(diǎn)得到圖7所示的匿名社會(huì)網(wǎng)絡(luò)有向圖G′。為了減少信息損失,本文基于GraphX圖數(shù)據(jù)處理平臺(tái),通過節(jié)點(diǎn)間的信息傳遞實(shí)現(xiàn)虛擬節(jié)點(diǎn)對(duì)的合并刪除,提高所發(fā)布數(shù)據(jù)的可用性。

圖7 匿名社會(huì)網(wǎng)絡(luò)有向圖G′Fig.7 Anonymous social network directed graph G′

信息傳遞的數(shù)據(jù)結(jié)構(gòu)用五元組(dstid,srcid,hops,community,tags)表示,稱五元組為n-跳鄰居列表(n-Hops Neighborhood Table,HNT),其中,dstid表示目的節(jié)點(diǎn)ID,srcid表示源節(jié)點(diǎn)ID,hops表示跳數(shù),community表示源節(jié)點(diǎn)所屬社區(qū),tags表示節(jié)點(diǎn)標(biāo)志位(初始時(shí)tags=0),tags=1表示源節(jié)點(diǎn)和目的節(jié)點(diǎn)均為虛擬節(jié)點(diǎn)。

初始化匿名圖G′的結(jié)果如圖8所示(僅列出部分虛擬節(jié)點(diǎn)初始HNTE(n-Hops Neigh-borhood Table Entry))。在初始時(shí),節(jié)點(diǎn)的dstid和srcid都是節(jié)點(diǎn)的ID,hops=0,tags=0,如節(jié)點(diǎn)f2的HNTE={f2,f2,0,1,0}。

圖8 有向圖G′的初始化結(jié)果Fig.8 Initialization result of directed graph G′

定義6(有向圖層次社區(qū)熵) 用有向圖層次社區(qū)熵(DGHCE)量化添加邊操作對(duì)社區(qū)層次結(jié)構(gòu)的影響,記作DGHCE(G,HG),其計(jì)算公式為:

DGHCE(G,HG)=

(3)

定義7(有向圖層次社區(qū)熵變化值) 用DGHCE的變化值UL衡量虛擬節(jié)點(diǎn)對(duì)合并刪除后添加的邊操作造成的信息損失,其計(jì)算公式為:

UL(G,G′)=|DGHCE(G,HG)-

DGHCE(G′,H′G)|

(4)

定義8(虛擬節(jié)點(diǎn)對(duì)合并刪除條件VNMDC)設(shè)存在邊和邊,虛擬節(jié)點(diǎn)對(duì)(fw,fx)能夠進(jìn)行合并刪除,當(dāng)且僅當(dāng)?(fw,fx)∈VirtualSet滿足以下3個(gè)條件:

1)fw,fx?VirtualRDD。

2)?EdgeRDD。

3)u≠v。

定理1對(duì)于虛擬節(jié)點(diǎn)對(duì)(fw,fx),VNMDC條件是(fw,fx)能夠合并刪除的充分條件。

證明如圖9(a)所示,合并刪除虛擬節(jié)點(diǎn)對(duì)(fw,fx),需刪除邊、并添加邊,但是有向圖G中已經(jīng)存在邊,故(fw,fx)不能合并刪除。同理,如圖9(b)所示,虛擬節(jié)點(diǎn)fw、fx均與節(jié)點(diǎn)u相連,不能添加邊,故(fw,fx)不能合并刪除。因此,當(dāng)且僅當(dāng)虛擬節(jié)點(diǎn)對(duì)(fw,fx)滿足VNMDC條件時(shí),(fw,fx)能夠合并刪除,如圖9(c)所示。

圖9 虛擬節(jié)點(diǎn)對(duì)之間的3種情況Fig.9 Three cases between virtual node pairs

通過節(jié)點(diǎn)間的信息傳遞得到每次迭代的虛擬節(jié)點(diǎn)對(duì)集合VirtualSet,判斷?(fw,fx)∈VirtualSet是否滿足VNMDC條件,將滿足條件的虛擬節(jié)點(diǎn)對(duì)放入候選虛擬節(jié)點(diǎn)集合CandidateSet中。選擇虛擬節(jié)點(diǎn)對(duì)合并刪除算法Select Merge_Delete(CandidateSet)描述如下:

算法3Select Merge_Delete(CandidateSet)算法

輸入候選合并刪除節(jié)點(diǎn)集合CandidateSet

輸出虛擬節(jié)點(diǎn)對(duì)(fw,fx)

1.M = Number of same community in CandidateSet;

2.N = CandidateSet.size;

3.if (N >1) then

4.if (M >1 || M==0) then

5.(fw,fx)=the min(UL) from CandidateSet;

6.return (fw,fx);

7.end if

8.if (M=1) then

9.return (fw,fx);

10.end if

11.else

12.return (fw,fx)

若候選虛擬節(jié)點(diǎn)對(duì)集合CandidateSet中虛擬節(jié)點(diǎn)對(duì)個(gè)數(shù)大于1,執(zhí)行算法3第4行～第7行,對(duì)于同一社區(qū)(或均為不同社區(qū))的虛擬節(jié)點(diǎn)對(duì)計(jì)算DGHCE值,選擇UL值小的虛擬節(jié)點(diǎn)對(duì)進(jìn)行合并刪除。如果虛擬節(jié)點(diǎn)對(duì)個(gè)數(shù)為1,執(zhí)行算法3的第8行～第12行直接選擇虛擬節(jié)點(diǎn)對(duì)(fw,fx)。

3.4 KIODA算法步驟

本文基于層次社區(qū)結(jié)構(gòu)的大規(guī)模社會(huì)網(wǎng)絡(luò)K-出入度匿名算法KIODA描述如下:

算法4KIODA算法

輸入原始圖G,匿名參數(shù)k

輸出匿名圖G*

1.基于Construst HRG算法生成HG;

2.基于Sequence Partition(G,k)算法生成K-出入度匿名序列d～;

3.根據(jù)匿名序列添加虛擬節(jié)點(diǎn),得到匿名圖G′;

4.初始化匿名圖G′,CandidateSet=?,VirtualRDD=?;

5.for SuperStep=1 to 6 do

6.Dst.Message ← Src.Message;//源節(jié)點(diǎn)將更新的//HNTE信息發(fā)送到目的節(jié)點(diǎn)

7.for (Message from Dst.HNTE) do

8.if (Message.Tags==1) then

9.Dst.VirtualSet ← Message;

10.end if

11.end for

12.for (Message from Dst.VirtualSet) do

13.fw=Message.srcid,fx=Message.disid;

14.if (fw,fx) satify VNMDC then

15.CandidateSet ← (fw,fx);

16.end if

17.end for

18.if CandidateSet.size > 0 then

19.(fw,fx)=Select Merge_Delete(CandidateSet);

20.G′.EdgeRDD.Remove ;

21.G′.EdgeRDD.Remove ;

22.G′.EdgeRDD.Add ;

23.VirtualRDD.Add (fw,fx);

24.VoteToHalt (fw,fx);

25.end if

26.end for

27.return G*

KIODA算法具體步驟如下:

1)在Superstep=0時(shí),節(jié)點(diǎn)初始化得到初始邊集合EdgeRDD。

2)在Superstep=1時(shí),進(jìn)行第1次迭代。節(jié)點(diǎn)收到自己的1跳鄰居信息,生成1-跳鄰居列表。第1次迭代標(biāo)志位均為0,VirtualSet=?,CandidateSet=?。

3)在Superstep=2時(shí),進(jìn)行第2次迭代,2-跳鄰居列表如表1所示(僅列出部分虛擬節(jié)點(diǎn)),查看是否存在tags=1。迭代得到VirtualSet={(f2,f1)},由于虛擬節(jié)點(diǎn)f2、f1均與節(jié)點(diǎn)1相連,不滿足VNMDC條件,故不能進(jìn)行合并刪除,CandidateSet=?。

表1 2-跳鄰居列表Table 1 2-hops neighbor list

4)在Superstep=3時(shí),進(jìn)行第3次迭代,3-跳鄰居列表如表2所示(僅列出tags=1的節(jié)點(diǎn)),迭代得到VirtualSet={(f10,f11),(f9,f1),(f6,f5),(f6,f11)}。

表2 3-跳鄰居列表Table 2 3-hops neighbor list

虛擬節(jié)點(diǎn)對(duì)(f10,f11)不滿足VNMDC條件,不能合并刪除,故CandidateSet={(f9,f1),(f6,f5),(f6,f11)}。執(zhí)行KIODA算法第20行～第24行合并刪除虛擬節(jié)點(diǎn)對(duì)(f9,f1),將邊<3,1>添加到EdgeRDD中,刪除邊、<3,f9>;虛擬節(jié)點(diǎn)f9、f1添加到VirtualRDD中,狀態(tài)設(shè)為InActive,停止迭代。虛擬節(jié)點(diǎn)對(duì)(f6,f5)、(f6,f11)執(zhí)行算法3計(jì)算DGHCE的變化情況,選擇UL值小的虛擬節(jié)點(diǎn)對(duì)進(jìn)行合并刪除。若合并刪除(f6,f5),有向圖層次社區(qū)樹HG的連接概率P1由1/2變?yōu)?;若合并刪除(f6,f11),P2由1/2變?yōu)?/4,如圖10所示。

圖10 層次社區(qū)熵示意圖Fig.10 Schematic diagram of hierarchical community entropy

經(jīng)計(jì)算,原始圖的DGHCE=3.574 15,DGHCEf6,f5=3.593 27,ULf6,f5=0.019 12,DGHCEf6,f11=3.563 07,ULf6,f11=0.011 08,因此,選擇合并刪除虛擬節(jié)點(diǎn)對(duì)(f6,f11),此時(shí)VirtualRDD={f9,f1,f6,f11}。第3次迭代停止,結(jié)果如圖11所示。

圖11 第3次迭代結(jié)果Fig.11 Results of the third iteration

KIODA算法在迭代6次后停止虛擬節(jié)點(diǎn)對(duì)合并刪除,得到如圖12所示的匿名社會(huì)網(wǎng)絡(luò)有向圖G*。

圖12 最終匿名社會(huì)網(wǎng)絡(luò)有向圖G*Fig.12 Eventually anonymous social network directed graph G*

4 實(shí)驗(yàn)結(jié)果與分析

本節(jié)將KIODA算法與快速K-度匿名(KDA)算法[10]、VA(VertexAddition)算法[23]進(jìn)行性能分析與比較。

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

本次實(shí)驗(yàn)采用斯坦福大學(xué)公開的2個(gè)真實(shí)社會(huì)網(wǎng)絡(luò)有向圖數(shù)據(jù)集Eu-Email和Epinions。Eu-Email網(wǎng)絡(luò)是歐洲大型研究機(jī)構(gòu)在2003年10月—2005年5月期間的電子郵件數(shù)據(jù),其中,給定一組電子郵件消息,每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)電子郵件地址,有向邊表示節(jié)點(diǎn)i向j發(fā)送一條消息。Epinions網(wǎng)絡(luò)是一個(gè)消費(fèi)者的在線評(píng)論社交網(wǎng)絡(luò),網(wǎng)站成員可以決定是否“互相信任”,有向邊表示用戶u信任用戶v。表3所示為數(shù)據(jù)集相關(guān)統(tǒng)計(jì)數(shù)據(jù)。實(shí)驗(yàn)使用的處理工具是GraphX,算法運(yùn)行環(huán)境為15個(gè)計(jì)算節(jié)點(diǎn),1.8 GHz CPU,16 GB RAM,Hadoop 2.7.2,Spark2.2.0,采用Scala 2.11.12編程。

表3 數(shù)據(jù)集相關(guān)統(tǒng)計(jì)數(shù)據(jù)Table 3 Statistical data of datasets

4.2 算法性能分析

圖13所示為隨著隱私值k的變化,算法的運(yùn)行時(shí)間對(duì)比結(jié)果。從圖13可以看出,隨著k值的增加,各算法的運(yùn)行時(shí)間也隨之增加,其中,KDA算法運(yùn)行時(shí)間最短,KIODA算法運(yùn)行時(shí)間最長。這是因?yàn)镵IODA算法首先要基于層次社區(qū)結(jié)構(gòu)對(duì)原始圖進(jìn)行社區(qū)劃分,然后再對(duì)出入度序列分組匿名,最后合并刪除虛擬節(jié)點(diǎn)對(duì),隨著k值的增加,需要添加更多的虛擬節(jié)點(diǎn),同時(shí)為了減少信息損失,要對(duì)更多的虛擬節(jié)點(diǎn)對(duì)進(jìn)行合并刪除操作。因此,KIODA算法的執(zhí)行時(shí)間略大于KDA算法和VA算法,但是總體而言,KIODA算法的運(yùn)行時(shí)間在可接受范圍內(nèi)。

圖13 3種算法的運(yùn)行時(shí)間對(duì)比結(jié)果Fig.13 Running time comparison results of three algorithms

4.3 信息損失分析

為了比較算法在匿名過程中的信息損失,測(cè)試算法匿名后平均出/入度數(shù)的變化情況。圖14所示為隨著k值的增加,3種算法在不同數(shù)據(jù)集中的平均出/入度數(shù)對(duì)比結(jié)果。從圖14可以看出,隨著k值的增加,VA算法在匿名后節(jié)點(diǎn)的平均度數(shù)變化較大,而KDA算法和KIODA算法匿名后節(jié)點(diǎn)的平均度數(shù)更接近于原始平均度數(shù)。這是因?yàn)閂A算法通過添加節(jié)點(diǎn)來實(shí)現(xiàn)K-匿名,匿名后造成節(jié)點(diǎn)的平均度數(shù)變化大,對(duì)圖結(jié)構(gòu)的影響較大,信息損失大;KDA算法和KIODA算法盡可能減少圖的修改,因此,匿名后平均節(jié)點(diǎn)度數(shù)變化較小,圖信息損失較小。

圖14 3種算法的平均出/入度數(shù)變化情況Fig.14 Changes of average out/in degrees of three algorithms

聚集系數(shù)(Clustering Coefficient,CC)是用來描述一個(gè)圖中頂點(diǎn)之間聚集程度的系數(shù)。匿名后平均聚集系數(shù)(Average Clustering Coefficient,ACC)變化越小,匿名過程對(duì)社區(qū)變化的影響越小。為了衡量算法匿名過程中在圖結(jié)構(gòu)方面的信息損失,測(cè)試匿名圖ACC的變化率如下:

Changeradio=|ACC*-ACC|/ACC×100%

(5)

其中,ACC*表示匿名后的平均聚類系數(shù)值。

圖15所示為3種算法匿名后ACC的變化率情況,從圖15可以看出,KDA算法和VA算法在匿名后ACC的變化率均大于KIODA算法。這是因?yàn)镵DA算法對(duì)圖的修改最少,VA算法添加節(jié)點(diǎn)實(shí)現(xiàn)最佳K-匿名化。KDA算法和VA算法在匿名時(shí)僅考慮滿足K-匿名,而不考慮節(jié)點(diǎn)所屬社區(qū)情況,因此,ACC變化率較大,匿名后社區(qū)結(jié)構(gòu)可用性低。隨著k值的增加,KIODA算法的ACC變化率很小,因此,KIODA算法更好地保證了有向圖的圖結(jié)構(gòu)性質(zhì),減少了社區(qū)結(jié)構(gòu)的信息損失。

圖15 3種算法的平均聚集系數(shù)變化率情況Fig.15 Change ratio of average clustering coefficient of three algorithms

4.4 數(shù)據(jù)可用性分析

μi(0=μ1≤μ2≤…≤μm≤m)是拉普拉斯矩陣L的特征值,L的第二小特征值(μ2)是其重要的一個(gè)特征值,用來表示社區(qū)的分離方式。圖16所示為隨著k值的增加,3種算法在不同數(shù)據(jù)集中的μ2值與原始圖的相似性比較結(jié)果。

圖16 3種算法的μ2相似性比較結(jié)果Fig.16 μ2 similarity comparison results of three algorithms

從圖16可以看出,KIODA算法的μ2值與原始圖更相似。這是因?yàn)镵IODA算法在合并刪除虛擬節(jié)點(diǎn)對(duì)時(shí)考慮了原始圖的社區(qū)結(jié)構(gòu),而KDA算法和VA算法在匿名時(shí)忽略了對(duì)社區(qū)結(jié)構(gòu)的保護(hù),給社區(qū)結(jié)構(gòu)造成了很大的損失。

在匿名過程中,為了衡量算法在社區(qū)結(jié)構(gòu)方面的可用性,引入精度指標(biāo)(Precision index)[24]衡量節(jié)點(diǎn)所屬社區(qū)變化情況。若節(jié)點(diǎn)在原始圖所屬社區(qū)與匿名后的社區(qū)相同,則ρltv(v)=lpv(v)值為1;若節(jié)點(diǎn)在原始圖所屬社區(qū)與匿名后的社區(qū)不同,則ρltv(v)=lpv(v)的值為0。精度指標(biāo)的范圍在[0,1]之間,若精度指標(biāo)的值為0,則原始圖與匿名圖的社區(qū)劃分完全不同;若精度指標(biāo)的值為1,則原始圖與匿名圖的社區(qū)劃分相同。精度指標(biāo)計(jì)算公式如下:

(6)

圖17所示為3種算法匿名后節(jié)點(diǎn)所屬社區(qū)的變化情況。從圖17可以看出,KDA算法和VA算法在匿名過程中沒有考慮節(jié)點(diǎn)的社區(qū)情況,因此匿名后節(jié)點(diǎn)所屬社區(qū)變化率很大。KIODA算法在合并刪除虛擬節(jié)點(diǎn)對(duì)時(shí)盡可能保證了節(jié)點(diǎn)所屬社區(qū)不變,因此匿名后社區(qū)的精度指標(biāo)更接近于1,其更好地保持了匿名圖在社區(qū)劃分方面的數(shù)據(jù)可用性。

圖17 3種算法的節(jié)點(diǎn)所屬社區(qū)變化情況Fig.17 Change of community of nodes of three algorithms

5 結(jié)束語

針對(duì)大規(guī)模社會(huì)網(wǎng)絡(luò)有向圖的隱私保護(hù)問題,本文構(gòu)建一種新的出入度攻擊模型并提出基于層次社區(qū)結(jié)構(gòu)的大規(guī)模社會(huì)網(wǎng)絡(luò)K-出入度匿名算法。該算法基于層次社區(qū)結(jié)構(gòu)劃分社區(qū),根據(jù)貪心算法分組并匿名出入度序列,對(duì)虛擬節(jié)點(diǎn)對(duì)進(jìn)行合并刪除以減少信息損失,在合并刪除虛擬節(jié)點(diǎn)對(duì)的過程中保持原始圖中節(jié)點(diǎn)所屬社區(qū)不變?；谡鎸?shí)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明,在分布式并行環(huán)境下執(zhí)行該算法,能夠?qū)Υ笠?guī)模社會(huì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行并行高效的隱私保護(hù),與傳統(tǒng)K-度匿名算法相比,其提高了大規(guī)模社會(huì)網(wǎng)絡(luò)有向圖數(shù)據(jù)的處理效率,更好地保證了數(shù)據(jù)發(fā)布時(shí)社區(qū)結(jié)構(gòu)分析結(jié)果的可用性,在節(jié)點(diǎn)平均出/入度數(shù)變化、平均聚類系數(shù)、拉普拉斯矩陣第二小特征值(μ2)以及社區(qū)結(jié)構(gòu)保護(hù)等方面都取得了很好的效果。本文算法在保證社區(qū)結(jié)構(gòu)分析結(jié)果可用性的基礎(chǔ)上保護(hù)了節(jié)點(diǎn)的隱私信息,但是,目前該算法僅針對(duì)具有相同隱私保護(hù)等級(jí)的用戶,下一步將針對(duì)不同隱私保護(hù)等級(jí)的用戶,研究個(gè)性化的K-出入度匿名方法。