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

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

0 概述

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

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

1 相關(guān)工作

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

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

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

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

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

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

(1)

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

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

(2)

圖1(a)所示為社會網(wǎng)絡(luò)有向圖G0,圖1(b)～圖1(d)為社會網(wǎng)絡(luò)有向圖G0的3個可能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ī)模社會網(wǎng)絡(luò)K-出入度匿名模型

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

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

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

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

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

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

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

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

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

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

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

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

3 K-出入度匿名算法

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

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

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

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

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

輸出HG

1.根據(jù)Markov chain隨機生成原始圖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

//通過隨機交換節(jié)點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-出入度序列分組匿名算法

針對社會網(wǎng)絡(luò)有向圖,本文提出Sequence Partition(G,k)算法,同一組中目標出入度的入(出)度數(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é)點出入度進行排序,求出目標出入度。第16行～第25行判斷SPC1、SPC2值的大小并進行分組。其中,SPC1表示將當前元素合并到上一組中的匿名化成本,SPC2表示將當前元素和后面k-1個元素形成新組的成本。如果SPC2

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

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

3.3 選擇虛擬節(jié)點對合并刪除算法

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

圖7 匿名社會網(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é)點ID,srcid表示源節(jié)點ID,hops表示跳數(shù),community表示源節(jié)點所屬社區(qū),tags表示節(jié)點標志位(初始時tags=0),tags=1表示源節(jié)點和目的節(jié)點均為虛擬節(jié)點。

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

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

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

DGHCE(G,HG)=

(3)

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

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

DGHCE(G′,H′G)|

(4)

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

1)fw,fx?VirtualRDD。

2)?EdgeRDD。

3)u≠v。

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

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

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

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

算法3Select Merge_Delete(CandidateSet)算法

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

輸出虛擬節(jié)點對(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é)點對集合CandidateSet中虛擬節(jié)點對個數(shù)大于1,執(zhí)行算法3第4行～第7行,對于同一社區(qū)(或均為不同社區(qū))的虛擬節(jié)點對計算DGHCE值,選擇UL值小的虛擬節(jié)點對進行合并刪除。如果虛擬節(jié)點對個數(shù)為1,執(zhí)行算法3的第8行～第12行直接選擇虛擬節(jié)點對(fw,fx)。

3.4 KIODA算法步驟

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

算法4KIODA算法

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

輸出匿名圖G*

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

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

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

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

5.for SuperStep=1 to 6 do

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

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時,節(jié)點初始化得到初始邊集合EdgeRDD。

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

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

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

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

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

虛擬節(jié)點對(f10,f11)不滿足VNMDC條件,不能合并刪除,故CandidateSet={(f9,f1),(f6,f5),(f6,f11)}。執(zhí)行KIODA算法第20行～第24行合并刪除虛擬節(jié)點對(f9,f1),將邊<3,1>添加到EdgeRDD中,刪除邊、<3,f9>;虛擬節(jié)點f9、f1添加到VirtualRDD中,狀態(tài)設(shè)為InActive,停止迭代。虛擬節(jié)點對(f6,f5)、(f6,f11)執(zhí)行算法3計算DGHCE的變化情況,選擇UL值小的虛擬節(jié)點對進行合并刪除。若合并刪除(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)計算,原始圖的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é)點對(f6,f11),此時VirtualRDD={f9,f1,f6,f11}。第3次迭代停止,結(jié)果如圖11所示。

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

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

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

4 實驗結(jié)果與分析

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

4.1 實驗設(shè)置

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

4.2 算法性能分析

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

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

4.3 信息損失分析

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

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

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

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

(5)

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

圖15所示為3種算法匿名后ACC的變化率情況,從圖15可以看出,KDA算法和VA算法在匿名后ACC的變化率均大于KIODA算法。這是因為KDA算法對圖的修改最少,VA算法添加節(jié)點實現(xiàn)最佳K-匿名化。KDA算法和VA算法在匿名時僅考慮滿足K-匿名,而不考慮節(jié)點所屬社區(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)是其重要的一個特征值,用來表示社區(qū)的分離方式。圖16所示為隨著k值的增加,3種算法在不同數(shù)據(jù)集中的μ2值與原始圖的相似性比較結(jié)果。

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

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

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

(6)

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

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

5 結(jié)束語

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