一種基于差分隱私的頻繁有權(quán)子圖挖掘算法

陶曉玉 寧 博 李冠宇

(大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院 遼寧 大連 116026)

0 引 言

隨著信息網(wǎng)絡(luò)的發(fā)展，大量的網(wǎng)絡(luò)數(shù)據(jù)產(chǎn)生，如社交網(wǎng)絡(luò)、通信網(wǎng)絡(luò)和商業(yè)貿(mào)易網(wǎng)絡(luò)等。這些網(wǎng)絡(luò)數(shù)據(jù)一般采用圖來(lái)表示，圖中的節(jié)點(diǎn)可能表示的是個(gè)體及其屬性或是一個(gè)公司機(jī)構(gòu)等，邊用來(lái)表示節(jié)點(diǎn)間存在一定的關(guān)系，其中，一些圖的邊上還帶有一定的權(quán)重值，這些權(quán)重值可能代表著公司之間的交易金額或是關(guān)系的親密程度等。圖中的這些頂點(diǎn)和邊可能包含著大量敏感信息，例如：個(gè)人的身份證號(hào)碼、電話號(hào)碼、銀行賬戶和交易金額等信息。一直以來(lái)，從圖數(shù)據(jù)集中挖掘頻繁子圖是圖數(shù)據(jù)分析的重要任務(wù)。挖掘頻繁子圖可以發(fā)現(xiàn)一些公共的子結(jié)構(gòu)，從而為進(jìn)一步的研究分析提供幫助。然而，當(dāng)圖數(shù)據(jù)集中包含著敏感信息，直接發(fā)布挖掘到的頻繁子圖將會(huì)導(dǎo)致個(gè)人隱私的泄露。因此需要對(duì)頻繁子圖的挖掘過(guò)程采取保護(hù)措施。本文主要針對(duì)有權(quán)網(wǎng)絡(luò)圖的頻繁子圖挖掘過(guò)程中的隱私保護(hù)進(jìn)行研究。

近年來(lái)，針對(duì)隱私保護(hù)方面的研究，已有許多匿名方法被提出。其中，Dwork等[1-2]提出的差分隱私保護(hù)方法是基于數(shù)據(jù)失真的一種方法，對(duì)隱私泄露風(fēng)險(xiǎn)有嚴(yán)格定量化的定義和證明且極大地保證了數(shù)據(jù)的可用性。在此定義下，對(duì)數(shù)據(jù)庫(kù)的計(jì)算處理結(jié)果對(duì)于具體某個(gè)記錄的變化是不敏感的，單個(gè)記錄在數(shù)據(jù)集中或者不在數(shù)據(jù)集中，都對(duì)計(jì)算結(jié)果的影響微乎其微。所以，一個(gè)記錄因其加入到數(shù)據(jù)集中所產(chǎn)生的隱私泄露風(fēng)險(xiǎn)被控制在極小的、可接受的范圍內(nèi)，攻擊者無(wú)法通過(guò)觀察計(jì)算結(jié)果而獲取準(zhǔn)確的個(gè)體信息。目前，差分隱私技術(shù)已被越來(lái)越多地應(yīng)用于圖數(shù)據(jù)方面的研究，如社區(qū)發(fā)現(xiàn)、圖的節(jié)點(diǎn)和邊的保護(hù)、頻繁子圖挖掘。

目前，差分隱私技術(shù)應(yīng)用到無(wú)權(quán)圖數(shù)據(jù)方面的保護(hù)工作已有很多且相對(duì)效果都比較好[3-5]。Xiao等[3]利用HRG( hierarchical random graph )模型將圖轉(zhuǎn)換成樹形結(jié)構(gòu)，以便處理圖的復(fù)雜結(jié)構(gòu)，并采用馬爾可夫蒙特卡羅(MCMC)方法對(duì)HRG模型空間進(jìn)行采樣，同時(shí)滿足差分隱私。該方法降低了噪聲的產(chǎn)生，有效地保留了基本的網(wǎng)絡(luò)結(jié)構(gòu)特性。Dong等[5]在Xiao等的工作基礎(chǔ)上做出了改進(jìn)，考慮大規(guī)模的圖數(shù)據(jù)集的保護(hù)，基于分而治之的思想，算法為每個(gè)社區(qū)構(gòu)建HRG，并將子級(jí)HRG合并為一個(gè)完整的HRG，從而消除了處理大型圖時(shí)原算法存在低效率的問(wèn)題。但是無(wú)權(quán)圖的保護(hù)工作中的算法不能直接用來(lái)保護(hù)有權(quán)重圖，由于將權(quán)重考慮到圖中的復(fù)雜性，在有權(quán)圖數(shù)據(jù)方面的隱私保護(hù)工作中，大多數(shù)研究采用k-匿名的方法[6-8]來(lái)保護(hù)隱私。此外，也有很多嘗試采用差分隱私的方法保護(hù)權(quán)重，但在保護(hù)邊的權(quán)重的過(guò)程中，許多工作未考慮圖的結(jié)構(gòu)保護(hù)。Li等[9]將圖中邊的權(quán)重序列轉(zhuǎn)化為未歸屬直方圖，進(jìn)而采用差分隱私保護(hù)圖中權(quán)重信息。具體的操作是將社交網(wǎng)絡(luò)圖中有相同的邊權(quán)重的桶合并到一個(gè)組，進(jìn)而減少噪聲的量，并采用k-indistinguishability方法保證差分隱私不孤立。最后，采用CI(Consistency Inference)保證最短路徑不改變。但這只考慮了圖中權(quán)重的隱私保護(hù)，沒有考慮圖中結(jié)構(gòu)的保護(hù)。

另外，已有一些工作在頻繁子圖挖掘過(guò)程中采用差分隱私這一保護(hù)技術(shù)，進(jìn)而保護(hù)頻繁子圖的隱私。Shen等[10]將頻繁圖模式挖掘算法與差分隱私的保證統(tǒng)一應(yīng)用于MCMC的框架中，是針對(duì)無(wú)權(quán)重頻繁子圖挖掘的保護(hù)。同時(shí)，為了保證隱私性和效用性，提出了一個(gè)有效的近鄰計(jì)數(shù)技術(shù)。Cheng等[11]在Shen等基礎(chǔ)上，解決了輸出空間太大而導(dǎo)致挖掘結(jié)果不精確以及弱差分隱私保護(hù)的問(wèn)題，提出了DFG算法。該算法主要分為兩個(gè)階段，在第一階段隱私地識(shí)別頻繁的子圖，并且在第二階段計(jì)算每個(gè)識(shí)別的頻繁子圖的噪聲支持，每個(gè)階段都有有效的方法被提出，整個(gè)算法滿足ε-差分隱私，很大程度地保證了數(shù)據(jù)效用性和隱私性。挖掘頻繁子圖的算法已有很多被提出，本文采用的gSpan算法[12]是基于圖的深度優(yōu)先搜索的一種頻繁子圖挖掘算法。該算法將圖集中的每個(gè)圖映射到DFS碼(一個(gè)邊的序列)，圖中的每條邊采用五元組的形式表示，根據(jù)DFS碼構(gòu)建詞典順序并制定規(guī)則選出最小DFS碼，從而篩選出頻繁子圖。

本文利用差分隱私這一嚴(yán)格隱私保護(hù)模型對(duì)有權(quán)頻繁子圖進(jìn)行挖掘，同時(shí)保護(hù)邊的權(quán)重值和圖的結(jié)構(gòu)。首先，對(duì)有權(quán)圖采用編碼方式，將邊的權(quán)重考慮到編碼中，構(gòu)建詞典序列，并對(duì)編碼中的權(quán)重值添加Laplace噪聲進(jìn)行數(shù)據(jù)干擾；在噪聲添加的過(guò)程中，合理地分配隱私預(yù)算。其次，在子圖挖掘過(guò)程中，同時(shí)采用差分隱私的Laplace機(jī)制和指數(shù)機(jī)制[1,13]，輸出滿足條件的擾動(dòng)后的頻繁子圖集，并在理論上分析算法的隱私性。最后，在多個(gè)真實(shí)數(shù)據(jù)集集上驗(yàn)證算法的效用性，并采用多個(gè)實(shí)驗(yàn)指標(biāo)與其他算法進(jìn)行對(duì)比分析。

1 相關(guān)定義

1.1 差分隱私

差分隱私(Differential Privacy，DP)目前被廣泛地應(yīng)用于推薦系統(tǒng)、基于位置的服務(wù)等領(lǐng)域。該模型不需要特殊的攻擊假設(shè)，不關(guān)心攻擊者具有的背景知識(shí)，并對(duì)隱私泄露風(fēng)險(xiǎn)給出了定量化分析。下面給出差分隱私的相關(guān)定義及性質(zhì)。

定義1ε-差分隱私。設(shè)隨機(jī)算法M，Range(M)為算法M所有可能輸出結(jié)果的集合。對(duì)于任意兩個(gè)鄰近數(shù)據(jù)集D和D′以及Range(M)的任何子集S，若滿足Pr(M(D)∈S)≤Pr(M(D′)∈S)×exp(ε)，則稱算法M滿足ε-差分隱私。

其中，ε是隱私預(yù)算，用來(lái)控制概率分布的相似性，當(dāng)ε越小時(shí)，exp(ε) 越接近于1，保護(hù)強(qiáng)度越大，擾動(dòng)也就越多，因此，ε值的選取通常需要衡量信息安全性與數(shù)據(jù)可用性。

差分隱私主要有兩個(gè)實(shí)現(xiàn)機(jī)制：Laplace機(jī)制和指數(shù)機(jī)制[13]。

該機(jī)制通常用于數(shù)值型的保護(hù)，可以用到有權(quán)圖中權(quán)重值的擾動(dòng)上，相當(dāng)于是對(duì)權(quán)重添加一個(gè)符合Laplace函數(shù)的噪聲。

該機(jī)制通常用于非數(shù)值型的保護(hù)，如分類值或是一個(gè)結(jié)構(gòu)。可以用來(lái)保護(hù)網(wǎng)絡(luò)圖數(shù)據(jù)的結(jié)構(gòu)。在指數(shù)機(jī)制的實(shí)現(xiàn)過(guò)程中，最重要的是確定效用函數(shù)u，得分越高的結(jié)果越容易被選中。

差分隱私在使用的過(guò)程中最重要的兩個(gè)方面如下。① 隱私預(yù)算。決定了隱私保護(hù)強(qiáng)度，ε值越小，隱私保護(hù)水平越高。② 噪聲機(jī)制。決定了查詢準(zhǔn)確性。

此外，差分隱私具有序列組合性和并行組合性兩種特性[1]，序列組合性強(qiáng)調(diào)隱私預(yù)算可以在方法的不同步驟進(jìn)行分配，而并行組合性則是保證滿足差分隱私的算法在其數(shù)據(jù)集的不相交子集的隱私性。

1.2 頻繁子圖挖掘(Frequent Subgraph Mining,FSM)

無(wú)向有權(quán)圖可以表示為G=，其中，V是圖中節(jié)點(diǎn)的集合，E是邊的集合，W對(duì)應(yīng)于圖中的邊的權(quán)重值。本文考慮的圖是無(wú)向、無(wú)自循環(huán)和無(wú)多個(gè)邊的圖。數(shù)據(jù)挖掘就是從圖數(shù)據(jù)集中發(fā)現(xiàn)一組公共的子結(jié)構(gòu)，即子圖結(jié)構(gòu)。下面給出圖的一些相關(guān)定義。

定義3如果圖G′的頂點(diǎn)集V′是V的子集，并且它的邊集E′是E的子集，則圖G′=(V′,E′)是另一個(gè)圖G=(V，E)的子圖，子圖關(guān)系記作G′∈sG。

定義4給定圖集GD，圖G的支持support為GD中G存在子圖同構(gòu)的圖G′的個(gè)數(shù)。

定義5給定圖集GD，GD={G1,G2,…,Gn},最小支持為min_sup。若圖g是頻繁圖，當(dāng)且僅當(dāng)sup(g)≥min_sup。

定義6給定圖數(shù)據(jù)集GD和閾值T，頻繁子圖挖掘就是為了找到數(shù)據(jù)集GD中所有支持不小于T的頻繁子圖。

如圖1所示，圖數(shù)據(jù)集GD的大小為3，其中，G1是G2的子圖，若閾值T=2，則可以得到圖數(shù)據(jù)GD中的頻繁子圖是g。

圖1 頻繁子圖挖掘圖

2 基于差分隱私挖掘有權(quán)頻繁子圖

在頻繁子圖挖掘的過(guò)程中，大致包括的幾個(gè)環(huán)節(jié)是圖的合理表示→候選集的產(chǎn)生→候選集的修剪→篩選出頻繁子圖。適當(dāng)?shù)膱D的表示，將有助于頻繁子圖的輸出。在對(duì)圖進(jìn)行統(tǒng)一編碼之后，會(huì)產(chǎn)生對(duì)應(yīng)的候選集，通常候選集是非常大的，而其中的頻繁子圖所占的比例是很小的，因此，需要對(duì)產(chǎn)生的候選集進(jìn)行修剪，以減少搜索空間，再對(duì)子圖進(jìn)行支持計(jì)算并判斷，輸出頻繁子圖集。

2.1 網(wǎng)絡(luò)圖中的權(quán)重保護(hù)

有權(quán)網(wǎng)絡(luò)圖中邊的權(quán)重通常包含著重要的信息，這些權(quán)重值可能代表著交易的金額、朋友關(guān)系的親密程度等。例如，在對(duì)社交網(wǎng)絡(luò)進(jìn)行分析時(shí)，通常把社交網(wǎng)絡(luò)可以看成一個(gè)圖的結(jié)構(gòu)，圖中節(jié)點(diǎn)表示個(gè)體，邊表示著個(gè)體之間的關(guān)系，權(quán)重值可能是具體的隱私信息或是用戶之間的關(guān)系程度等。當(dāng)這些權(quán)重值攜帶著敏感信息，若不在圖發(fā)布之前對(duì)邊的權(quán)重值進(jìn)行處理則很容易造成用戶的個(gè)人信息暴露，因而保護(hù)圖中邊的權(quán)重的隱私是很有必要的。

2.1.1圖的編碼算法EDFS(ExtendedDFSAlgorithm)

首先，本文是在擴(kuò)展gSpan算法[12]的基礎(chǔ)上表示圖的，把權(quán)重值考慮到編碼中，將擴(kuò)展的算法稱之為EDFS。對(duì)同一圖進(jìn)行深度優(yōu)先搜索(DFS)時(shí)，可以得到多個(gè)不同結(jié)果，即可以有多個(gè)同構(gòu)的DFS樹，例如，圖2中的(b)-(d)與(a)是同構(gòu)的。

圖2 深度優(yōu)先搜索樹圖

對(duì)圖中的頂點(diǎn)深度優(yōu)先搜索會(huì)形成一個(gè)線性順序，根據(jù)查詢時(shí)間先后來(lái)設(shè)置下標(biāo)。i

假設(shè)e1=(i1,j1)，e2=(i2,j2)。1) 若i1=i2且j1

那么就可以根據(jù)深度優(yōu)先搜索的時(shí)間先后對(duì)圖進(jìn)行DFS編碼。EDFS算法在構(gòu)造DFS編碼的過(guò)程中，將圖中的邊表示成六元組的形式，即，其中，i、j是標(biāo)號(hào)，Wij是邊的權(quán)重，li、l(i,j)、lj是頂點(diǎn)和邊的標(biāo)簽，i可以表示成 <0，1，3，X，Y>。DFS碼的一個(gè)定義如下：

另外，生殖醫(yī)學(xué)中心中的其他潔凈輔助用房（冷凍室、工作室、潔凈走廊等）可按Ⅳ級(jí)潔凈用房設(shè)計(jì)，局部集中送風(fēng)。所有裝修材料均不應(yīng)有對(duì)工作造成不良影響的化學(xué)源和放射源，不得使用有刺激性氣味的設(shè)備和材料。取卵室應(yīng)按Ⅱ級(jí)潔凈用房設(shè)計(jì)，并采用局部集中送風(fēng)；以上噪聲均應(yīng)不大于50dB（A）。

給定一個(gè)圖G的DFS樹，可以基于

因此，可以得到的DFS碼如表1所示。

表1 DFS碼

可以看出，同一個(gè)圖可以有多個(gè)DFS碼。因此，對(duì)DFS碼構(gòu)造詞典順序。EDFS算法在構(gòu)造詞典順序時(shí)應(yīng)遵循的規(guī)則如下：假設(shè)當(dāng)前有兩個(gè)邊e1=(vi,vj,Wij,l(vi),l(vj))，e2=(vx,vy,Wxy,l(vx),l(y))。 若e1

(1) (vi,vj)<(vx,vy)。

(2) (vi,vj)=(vx,vy)且Wij>Wxy。

(3) (vi,vj)=(vx,vy)且Wij=Wxy且(l(vi),l(vj))<(l(vx),l(vj))

若是有邊標(biāo)簽的圖，則條件3為(vi,vj)=(vx,vy)且Wij=Wxy且(l(vi),l(i,j),l(vj))<(l(vx),l(x,y),l(vj))。

考慮到權(quán)重值通常表示著關(guān)系的親密程度或是交易金額，權(quán)重越大的應(yīng)該被選擇出來(lái)，因而定義權(quán)重越大的邊越早被選擇出來(lái)。根據(jù)上述建立的詞典順序可以得到最小的DFS碼是圖2(c)對(duì)應(yīng)的DFS碼，這樣每一個(gè)圖都可以對(duì)應(yīng)一個(gè)唯一的最小DFS碼。

2.1.2邊的權(quán)重保護(hù)算法Diff-WS

算法1Diff-WS

輸入：邊的權(quán)重序列集WS，隱私預(yù)算ε1；每個(gè)圖中的邊數(shù)為Ei，圖集GD，大小為N，總邊數(shù)為E

輸出：擾動(dòng)后的邊的權(quán)重序列集WS’

1：fori=1 toNdo

2： for eachWSi∈WSdo

3： forj=1 toM

/*對(duì)每個(gè)序列WSi中的每個(gè)權(quán)重wj添加Laplace噪聲*/

5： if (w′j<0) then

//對(duì)擾動(dòng)后的權(quán)重判斷

6: back to Line 4;

7：WSi′←w′j

//將每個(gè)擾動(dòng)后的權(quán)重w′j存入到WSi′

8: end for

9： end for

10:end for

11: returnWS′

2.1.3隱私效用分析

噪聲添加的數(shù)量將會(huì)取決于隱私預(yù)算的分配以及敏感度的計(jì)算。由于對(duì)數(shù)據(jù)集中的權(quán)重添加噪聲的過(guò)程中是將每個(gè)圖中的邊的權(quán)重看成一個(gè)個(gè)序列，即一個(gè)大小為N的圖集對(duì)應(yīng)N個(gè)權(quán)重序列。在此過(guò)程中每一個(gè)序列依次獨(dú)立進(jìn)行處理，所以，敏感度依然是ΔQ=Wmax-Wmin，Wmax是最大的權(quán)重值，Wmin是最小的權(quán)重值。

2.2 頻繁有權(quán)子圖挖掘

圖集GD中的每個(gè)大小為i的圖，記作i-graph。i表示圖中含有邊的數(shù)量。頻繁子圖的挖掘過(guò)程是將1-graph作為候選集并從中篩選出滿足閾值判定條件的候選集，重復(fù)此過(guò)程直到篩選出最理想的符合條件的頻繁子圖集。差分隱私在此過(guò)程中有兩處被用到，一是閾值條件篩選候選子圖時(shí)利用Laplace機(jī)制擾動(dòng)候選子圖的支持，二是在噪聲閾值條件篩選出的候選子圖集的基礎(chǔ)上，利用指數(shù)機(jī)制再篩選，從而保證數(shù)據(jù)效應(yīng)性和隱私性。具體過(guò)程如算法2所示。

算法2Subgraph_Mining

輸入： i-subgraph候選集Ci；隱私預(yù)算ε2、ε3；閾值T；頻繁i-graph的數(shù)量ni

輸出：Frequenti-subgraphFi

1：ifs≠min_DFS (s) then

//先判斷子圖s是否滿足最小DFS碼條件

2：return

3：FS←FS∪{s}

4: forj=1 tonido

for eachs∈Cido

5： enumerates∈G?GDand count its children

6： for eachc，ciss’child with one edge growth in GD do

8：Ci′←c

9： end if

10： end for

11： ifCi′≠ then

13： RemovegjfromCi

14：Fi←gj

15： Subgraph_Mining(GD，ε2，ε3，F(xiàn)G，s)

16： end if

17： end for

18：returnFi

算法2用來(lái)挖掘頻繁有權(quán)子圖。首先，判斷子圖的編碼是否為最小編碼，若是滿足最小碼條件，則找出每個(gè)子圖的孩子(child)，以每次增長(zhǎng)一條邊的形式生成child。對(duì)子圖的孩子的支持添加Laplace機(jī)制形成噪聲支持，由于相差只有一個(gè)圖的圖數(shù)據(jù)集，則添加Laplace噪聲的敏感度為1，分配的隱私預(yù)算為ε2。隨后，判斷該噪聲支持是否滿足閾值條件，不斷地重復(fù)子圖挖掘過(guò)程。最后，篩選出的子圖滿足差分隱私指數(shù)機(jī)制。

2.3 Diff-Wfsm 算法

算法3是本文提出的Diff-Wfsm算法，用于在頻繁有權(quán)子圖的挖掘過(guò)程中保護(hù)隱私。

算法3Diff-Wfsm

輸入：圖數(shù)據(jù)集GD，閾值T，隱私預(yù)算(ε1,ε2,ε3ε1+ε2+ε3≤ε)

輸出：擾動(dòng)后的頻繁子圖集合FS

1: Diff-WS(WS,ε1，WS′) /*邊的權(quán)重進(jìn)行擾動(dòng)*/

2: sort labels of the vertices and edges in GD by their frequency

/*對(duì)圖集進(jìn)行預(yù)處理操作*/

3：remove infrequent vertices and edges

/*移除非頻繁節(jié)點(diǎn)和非頻繁邊*/

4：relabel the remaining vertices and edges in descending frequency forGD

5: sortFS1 in DFS lexicographic order

6：FS←FS1

7：for each edgee∈FS1 do

8： initialize 1-edge graphswithe

9： Subgraph_Mining(GD，ε2，ε3，F(xiàn)S，s)

/*頻繁子圖挖掘過(guò)程*/

10：GD←GD-e

11: if |GD|

12: break

13: end if

14: end for

算法3首先對(duì)圖數(shù)據(jù)集的每個(gè)圖中的邊權(quán)重進(jìn)行擾動(dòng)，也就是2.1.2節(jié)中的 Diff-WS 算法，根據(jù)每個(gè)圖中的邊數(shù)不同，分配不同大小的隱私預(yù)算，避免了隱私預(yù)算分配一致的問(wèn)題。處理完權(quán)重后，繼續(xù)對(duì)圖進(jìn)行預(yù)處理和編碼操作，根據(jù)頂點(diǎn)和邊的頻繁度，移除非頻繁節(jié)點(diǎn)和非頻繁邊，再對(duì)剩下的邊和頂點(diǎn)以頻繁度由大到小的順序重新標(biāo)簽。最后對(duì)篩選出的1-edge圖進(jìn)行頻繁子圖挖掘，在挖掘過(guò)程中先對(duì)候選集的支持添加Laplace噪聲，再對(duì)篩選出的噪聲候選子圖集采用指數(shù)機(jī)制，篩選出相對(duì)理想的頻繁子圖集，也就是2.2節(jié)中的 Subgraph_Mining算法，直到不滿足閾值條件時(shí)算法結(jié)束。

2.4 隱私保護(hù)分析

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

本節(jié)將結(jié)合實(shí)驗(yàn)結(jié)果來(lái)分析和評(píng)估算法的效用。在不同真實(shí)數(shù)據(jù)集下，采用RE和F1-score這兩個(gè)效用指標(biāo)評(píng)估隱私預(yù)算大小、閾值大小對(duì)算法的影響。實(shí)驗(yàn)結(jié)果顯示本文提出的方法是有效的，隱私預(yù)算添加得越多，數(shù)據(jù)效用越高，誤差越小。閾值設(shè)置的越大，數(shù)據(jù)效用越高，即F1-score值越大；閾值越小，誤差越大，即RE越大。

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

算法在1.60 GHz CPU，內(nèi)存為4 GB RAM，Windows7 64位操作系統(tǒng)的PC中采用Java語(yǔ)言實(shí)現(xiàn)。

實(shí)驗(yàn)中采用三個(gè)數(shù)據(jù)集驗(yàn)證算法的有效性，如表2所示。Grd[14]是含有340個(gè)圖、9 317條邊的圖集，權(quán)重在0到5之間，邊的分布相對(duì)不均勻，最小的邊數(shù)為7條，最大邊數(shù)達(dá)到179條，IBM[15]中邊的分布相對(duì)均勻，平均邊數(shù)為21，權(quán)重值在0到10之間。EIB是在原有非權(quán)重?cái)?shù)據(jù)集的基礎(chǔ)上，利用正態(tài)分布隨機(jī)產(chǎn)生的權(quán)重值，權(quán)重值范圍在0到50之間。閾值Threshold和隱私預(yù)算ε的選擇根據(jù)實(shí)際情況決定，通常ε的設(shè)置不會(huì)太大，若ε設(shè)置過(guò)大，保護(hù)工作基本無(wú)效。Threshold設(shè)置過(guò)大，可能導(dǎo)致挖掘結(jié)果只有一個(gè)或零個(gè)，是沒有實(shí)際意義的。因此為了更好地觀察兩個(gè)參數(shù)對(duì)算法效果的影響，實(shí)驗(yàn)中隱私預(yù)算ε取0到30之間，按照ε1∶ε2∶ε3=5∶3∶2的比例分配，閾值Threshold取值為0.1～0.6。

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

本文采用RE和F1-score兩個(gè)評(píng)估指標(biāo)來(lái)檢驗(yàn)算法的性能，分別定義如下：

RE (相對(duì)誤差)是用來(lái)衡量挖掘結(jié)果的可信度，如式(1)所示。

(1)

F1-score是用來(lái)衡量挖掘結(jié)果的數(shù)據(jù)可用性，如式(2)所示。

(2)

3.2 結(jié)果分析

圖3顯示對(duì)三個(gè)數(shù)據(jù)集的權(quán)重序列添加不同隱私預(yù)算的噪聲后權(quán)重序列誤差的變化。隱私預(yù)算ε 越大，權(quán)重序列誤差WSE就越小，保護(hù)程度就越高。噪聲的添加是根據(jù)Laplace函數(shù)產(chǎn)生的，具有一定的隨機(jī)性，實(shí)驗(yàn)中圖集中的邊數(shù)越多，保護(hù)程度越高，擾動(dòng)的結(jié)果由數(shù)據(jù)集中邊的分布、隱私預(yù)算的大小決定的。

圖3 Grd：不同數(shù)據(jù)集下邊權(quán)重的WSE變化

由于當(dāng)前還沒有與挖掘有權(quán)頻繁子圖的相關(guān)算法，所以實(shí)驗(yàn)中在挖掘過(guò)程中只采用Laplace機(jī)制的算法作為實(shí)驗(yàn)對(duì)比，記作Basic算法。

如圖4-圖6所示，隨著閾值Threshold的增加，F(xiàn)1-score呈上升趨勢(shì)，這是因?yàn)殚撝翟O(shè)置得越大，可滿足的頻繁子圖的候選就越少，挖到真實(shí)的子圖的可能性越大，因而數(shù)據(jù)效用就越高，即F-score越大；在三個(gè)數(shù)據(jù)集上，本文算法Diff-Wfsm都優(yōu)于Basic算法，F(xiàn)1-score至少可以達(dá)到0.7以上，最高可以達(dá)到0.9，而Basic算法一般都是在0.6～0.7，總體來(lái)看都是Diff-Wfsm算法相對(duì)較好。

圖4 Grd：不同閾值下F1-score的變化

圖5 IBM：不同閾值下F1-score的變化

圖6 EIB：不同閾值下F1-score的變化

如圖7-圖9所示，在三個(gè)數(shù)據(jù)集上，RE都是隨著閾值的增加而減少，當(dāng)閾值選取很小時(shí)，可滿足條件的頻繁子圖個(gè)數(shù)就越大，那么可能存在的非真實(shí)的頻繁子圖就越多，這樣就會(huì)導(dǎo)致相對(duì)誤差越大。Diff-Wfsm算法一般最多不超過(guò)0.2，Basic算法甚至要達(dá)到0.3，而且最低也一般在0.1左右，而Diff-Wfsm算法可以達(dá)到0.02左右。

圖7 Grd：不同閾值下RE的變化

圖8 IBM：不同閾值下RE的變化

圖9 EIB：不同閾值下RE的變化

圖10-圖12中，受隱私預(yù)算的影響，F(xiàn)1-score依然在不斷增加，Diff-Wfsm算法可以基本上保持在0.8以上，這是因?yàn)殡[私預(yù)算添加得越多，保護(hù)程度就越低，也就是干擾影響越少，因而數(shù)據(jù)效用性就越高。另外，Diff-Wfsm算法在子圖挖掘過(guò)程中對(duì)候選采用指數(shù)機(jī)制再篩選，這樣就保證選出來(lái)的頻繁子圖集的數(shù)據(jù)效用性更大，即F1-score更大。

圖10 Grd：不同隱私預(yù)算下F1-score的變化

圖11 IBM：不同隱私預(yù)算下F1-score的變化

圖12 EIB：不同隱私預(yù)算下F1-score的變化

圖13-圖15中，隨著隱私預(yù)算的不斷增加，干擾影響就越大，RE在減少，Diff-Wfsm算法相對(duì)穩(wěn)定，總體上都要優(yōu)于Basic算法，尤其在IBM、EIB中，Diff-Wfsm算法的RE基本上都在0.1之下，誤差是很小的。

圖13 Grd：不同隱私預(yù)算下RE的變化

圖14 IBM：不同隱私預(yù)算下RE的變化

圖15 EIB：不同隱私預(yù)算下RE的變化

圖16是算法在三個(gè)數(shù)據(jù)集上挖掘頻繁子圖所需要的時(shí)間。閾值的設(shè)置影響著所需要的時(shí)間，總體來(lái)看，閾值越大，需要的時(shí)間越小，尤其在數(shù)據(jù)集EIB上較為明顯。主要是因?yàn)殚撝翟O(shè)置越大，可以滿足條件的頻繁子圖就越少，需要花費(fèi)的挖掘時(shí)間也就越少。在數(shù)據(jù)集IBM中用的時(shí)間較多，可以看出圖越復(fù)雜，花費(fèi)的時(shí)間就越多。

圖16 不同數(shù)據(jù)集中的運(yùn)行時(shí)間

因此，通過(guò)以上多個(gè)實(shí)驗(yàn)驗(yàn)證可以看出，本文算法Diff-Wfsm無(wú)論是F1-score還是RE指標(biāo)下，相對(duì)效果都要更好，不僅保護(hù)了頻繁有權(quán)子圖的隱私，而且提高了頻繁有權(quán)子圖挖掘結(jié)果的效用性。其次，隱私預(yù)算大小選取和閾值大小的設(shè)定都對(duì)實(shí)驗(yàn)結(jié)果有著很大影響，具體要根據(jù)實(shí)際的需求來(lái)設(shè)定。另外，在三個(gè)分布略有不同的數(shù)據(jù)集上，本文算法的相對(duì)效用都很高。

4 結(jié) 語(yǔ)

本文采用差分隱私的保護(hù)技術(shù)挖掘頻繁有權(quán)子圖，提出了Diff-Wfsm算法，同時(shí)保證了頻繁子圖的結(jié)構(gòu)與邊權(quán)重的隱私。先是擴(kuò)展原有的頻繁子圖挖掘算法，把邊的權(quán)重值考慮到DFS編碼中，即EDFS算法，并在頻繁子圖挖掘之前對(duì)圖的權(quán)重值干擾，為了保證添加噪聲不一致，采用了按邊分配預(yù)算的策略，即Diff-WS算法。挖掘過(guò)程中同時(shí)采用Laplace機(jī)制和指數(shù)機(jī)制來(lái)提高挖掘結(jié)果的隱私性和效用性，先對(duì)候選子圖的支持添加Laplace噪聲干擾，再采用指數(shù)機(jī)制進(jìn)一步篩選理想的頻繁子圖集。最后，在不同的真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證，實(shí)驗(yàn)結(jié)果證明本文方法是可行和有效的。未來(lái)研究方向是進(jìn)一步提高算法的效率和挖掘結(jié)果的精確度，并減少噪聲量的添加，同時(shí)爭(zhēng)取擴(kuò)展到整個(gè)有權(quán)網(wǎng)絡(luò)圖的隱私保護(hù)。