基于k-度匿名的社會網(wǎng)絡(luò)隱私保護方法

龔衛(wèi)華，蘭雪鋒，裴小兵，楊良懷

(1.浙江工業(yè)大學計算機科學與技術(shù)學院，浙江杭州 310023； 2.華中科技大學軟件學院，湖北武漢 430074)

?

基于k-度匿名的社會網(wǎng)絡(luò)隱私保護方法

龔衛(wèi)華1，蘭雪鋒1，裴小兵2，楊良懷1

(1.浙江工業(yè)大學計算機科學與技術(shù)學院，浙江杭州 310023； 2.華中科技大學軟件學院，湖北武漢 430074)

針對當前社會網(wǎng)絡(luò)的匿名化隱私保護方法存在信息損失量巨大、網(wǎng)絡(luò)關(guān)系結(jié)構(gòu)被改變嚴重等問題，提出一種保持網(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-度匿名化.區(qū)別于傳統(tǒng)的數(shù)值擾亂或圖修改如隨機增加、刪除節(jié)點或邊等方法，該模型的優(yōu)勢在于既不增加網(wǎng)絡(luò)邊數(shù)和節(jié)點數(shù)，也不破壞網(wǎng)絡(luò)原有連通性和關(guān)系結(jié)構(gòu).實驗結(jié)果表明，SimilarGraph匿名化方法不僅能有效提高網(wǎng)絡(luò)抵御度屬性攻擊的能力，并且還能保持網(wǎng)絡(luò)結(jié)構(gòu)穩(wěn)定，同時具有較理想的信息損失代價.

社會網(wǎng)絡(luò)；隱私保護；k-度匿名；信息損失

1　引言

近年來，社會網(wǎng)絡(luò)的流行已深刻地改變了人們的日常生活和交流方式，國內(nèi)外著名社交網(wǎng)站如Facebook、QQ、人人網(wǎng)等注冊用戶數(shù)量不斷攀升，以Facebook為例，用戶總數(shù)在2013年已突破10億，其中包含1500億條朋友鏈接，這些社會網(wǎng)絡(luò)數(shù)據(jù)蘊含巨大的商業(yè)價值和應(yīng)用前景，例如可促進廣告、游戲、零售等業(yè)務(wù)迅速增長.然而，人們在使用基于社會網(wǎng)絡(luò)的應(yīng)用同時面臨著嚴重的隱私信息泄露和惡意攻擊問題.因此，研究社會網(wǎng)絡(luò)的隱私保護技術(shù)顯得尤為重要.

社會網(wǎng)絡(luò)屬于復雜網(wǎng)絡(luò)的研究范疇，關(guān)注的是社會個體及個體間的互動和聯(lián)系，同樣具有“小世界”現(xiàn)象和冪律分布特征[1～3]，但這使得社會網(wǎng)絡(luò)所包含的2類重要隱私信息(節(jié)點屬性數(shù)據(jù)和關(guān)系數(shù)據(jù))極易遭受節(jié)點度攻擊、鏈接攻擊等結(jié)構(gòu)化攻擊.目前針對社會網(wǎng)絡(luò)的隱私保護問題已取得一些研究成果，如從節(jié)點屬性數(shù)據(jù)角度出發(fā)的隱私保護類似于數(shù)據(jù)發(fā)布研究中的隱私保護方法[4～6]，側(cè)重保護標識或敏感屬性如姓名、電話、地址等，常采用已比較成熟的數(shù)據(jù)泛化[7～10]、擾動[5,11]或添加噪聲節(jié)點[12]等方法.而針對關(guān)系數(shù)據(jù)的隱私保護則是亟待人們深入探索的研究熱點，通常被建模為圖數(shù)據(jù)并采用數(shù)值擾亂法或圖修改法如隨機增加、刪除節(jié)點或邊[13]，以及修改邊權(quán)重值[14]來實現(xiàn)隱私保護.總體上看，現(xiàn)有的社會網(wǎng)絡(luò)隱私保護方法大多基于如何實現(xiàn)各種匿名化模型如節(jié)點k-匿名、子圖k-匿名等[15]，但他們都面臨由于匿名化而帶來巨大的信息損失問題，甚至還會嚴重破壞社會網(wǎng)絡(luò)關(guān)系結(jié)構(gòu)，顯著降低了網(wǎng)絡(luò)數(shù)據(jù)的效用.

本文針對社會網(wǎng)絡(luò)中關(guān)系數(shù)據(jù)這類隱私對象提出一種改進的基于圖的k-度匿名模型SimilarGraph，該模型首先運用動態(tài)規(guī)劃思想進行基于節(jié)點度的最優(yōu)簇劃分，然后，通過移動邊方式重構(gòu)網(wǎng)絡(luò)圖實現(xiàn)圖的k-度匿名化.該方法不僅能克服傳統(tǒng)匿名化算法所存在嚴重的信息損失缺點，還有效保持了社會網(wǎng)絡(luò)原有連通性和內(nèi)在關(guān)系結(jié)構(gòu)穩(wěn)定，并提高了抵御度屬性攻擊的能力.

2　相關(guān)工作

目前，現(xiàn)有針對網(wǎng)絡(luò)關(guān)系數(shù)據(jù)的隱私保護研究大多數(shù)都采用匿名化模型來防止隱私信息泄露和惡意攻擊，其主要途徑有基于聚類方法和圖修改方法.

基于聚類的匿名化方法是先對節(jié)點、邊或兩者同時聚類成簇，然后通過泛化方式來達到匿名化效果.文獻[16]提出將網(wǎng)絡(luò)中相似節(jié)點聚合為一簇，每個簇所包含的節(jié)點數(shù)≥k，這樣使得攻擊命中率降為1/k.Campan等[8]采用貪心策略對網(wǎng)絡(luò)中屬性相似的節(jié)點進行聚類并使用邊泛化方法實現(xiàn)k匿名的網(wǎng)絡(luò)，該方法考慮了匿名化過程中的信息損失問題.文獻[17]對加權(quán)無向網(wǎng)絡(luò)采用節(jié)點聚類和邊聚類相結(jié)合的泛化方式實現(xiàn)k-匿名模型，但缺點是嚴重改變了網(wǎng)絡(luò)結(jié)構(gòu)，同時還降低了匿名化后的網(wǎng)絡(luò)數(shù)據(jù)效用.

近年來，采用圖修改方法實現(xiàn)網(wǎng)絡(luò)匿名化已成為國內(nèi)外研究者關(guān)注的熱點，Liu等[18]提出圖的k-度匿名概念，即要求圖中任一頂點都至少有k-1個頂點與其度數(shù)相同，并運用貪心策略采用增加邊的方式來實現(xiàn)匿名圖，以抵御節(jié)點度屬性攻擊，該方法雖然考慮了圖修改的最小代價問題，但破壞了網(wǎng)絡(luò)連通性使得網(wǎng)絡(luò)內(nèi)在關(guān)系結(jié)構(gòu)發(fā)生重大變化.Yuan[19]和Zhou[20]都針對具有節(jié)點屬性標簽的社會網(wǎng)絡(luò)提出了k-度-l多樣化匿名模型，該模型在k度匿名的基礎(chǔ)上要求相同度數(shù)的k個節(jié)點必須有l(wèi)種不同標簽，并通過增刪邊和添加噪聲節(jié)點的方法實現(xiàn)屬性匿名，但他們都沒有考慮匿名化所造成的信息損失影響.Zheleva等[21]將關(guān)系邊區(qū)分為敏感邊和非敏感邊并提出通過刪除敏感邊的方式實現(xiàn)圖的匿名化，以防止鏈接再識別攻擊，其不足之處在于數(shù)據(jù)匿名化的效用由刪除邊的數(shù)量多少決定，缺乏對信息損失量的考慮，嚴重破壞原有網(wǎng)絡(luò)的連通性.此外，Zou等[22]運用圖同構(gòu)理論提出k-同構(gòu)匿名模型防御結(jié)構(gòu)化攻擊，要求網(wǎng)絡(luò)任一子圖至少有k-1個與其同構(gòu)的子圖，其缺點是同構(gòu)圖的匹配和重構(gòu)造代價較大，特別是圖轉(zhuǎn)化時需要復制邊的操作破壞了原有網(wǎng)絡(luò)的結(jié)構(gòu)特性.

綜上所述，基于聚類的匿名模型由于泛化后存在嚴重的信息損失問題，導致網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生巨大變化，數(shù)據(jù)效用急劇降低.而針對圖數(shù)據(jù)修改或轉(zhuǎn)化的匿名化方法大多都采用添加、刪除節(jié)點或邊以及子圖同構(gòu)等擾動方式實現(xiàn)k-度匿名，但這種圖隨機修改策略忽略了社會網(wǎng)絡(luò)內(nèi)在結(jié)構(gòu)特性，仍無法克服較大的信息損失問題.為此，本文提出的隱私保護模型SimilarGraph與傳統(tǒng)的數(shù)值擾亂或圖修改方法不同之處在于采用移邊方式替代隨機增、刪節(jié)點或邊等操作，并能在網(wǎng)絡(luò)節(jié)點數(shù)和邊數(shù)都保持不變條件下以最小的信息損失代價移動關(guān)系邊實現(xiàn)網(wǎng)絡(luò)的k-度匿名化，因而既不損害社會網(wǎng)絡(luò)原有連通性和關(guān)系結(jié)構(gòu)，還有效提高了抵御度屬性攻擊的能力.

3　相關(guān)定義

為了便于研究，本文將社會網(wǎng)絡(luò)建模為無權(quán)無向圖G=(V,E)，其中V表示為社會網(wǎng)絡(luò)中的節(jié)點集，E表示節(jié)點間的關(guān)系邊集，且E?V×V.一般情況下，圖中節(jié)點及其關(guān)系極易受到節(jié)點度攻擊、鏈接攻擊等結(jié)構(gòu)化攻擊，因此，實現(xiàn)圖中節(jié)點及關(guān)系邊的匿名化是一種重要的隱私保護方法，下面先給出一些基本定義.

圖的k-度匿名借鑒了傳統(tǒng)數(shù)據(jù)表中的k-匿名思想[11]，使得圖中節(jié)點間關(guān)系及其度分布趨于同構(gòu)，這將有效降低結(jié)構(gòu)化攻擊的概率，至少小于等于1/k.從另一角度看，社會網(wǎng)絡(luò)可看成由若干子圖構(gòu)成，每個子圖都滿足k-度匿名模型，這樣得出網(wǎng)絡(luò)的k-度匿名概念.

由定義2可知，社會網(wǎng)絡(luò)被劃分成滿足k-度匿名的各簇實際上可稱為匿名簇，同一簇內(nèi)的節(jié)點都具有相同的度屬性，而不同的匿名簇間滿足不同的k-度匿名要求.對于相同簇中的節(jié)點由于具有同構(gòu)特征而不易受攻擊，并且如果簇越大、簇數(shù)量越多，其遭受攻擊的難度也越大.因此，當社會網(wǎng)絡(luò)被劃分成滿足定義2的m個簇時，受到惡意攻擊的概率將進一步下降到1/(m·k).

為了便于社會網(wǎng)絡(luò)按照節(jié)點度特征劃分成各匿名簇，下面給出基于遞減度的序列結(jié)構(gòu).

定義3遞減度的節(jié)點序列Sq(〈v1…vi〉)：如果網(wǎng)絡(luò)圖G的節(jié)點集V={v1,…,vi}中所有節(jié)點按照遞減度的偏序關(guān)系排列，即滿足Dg(v1)≥…≥Dg(vi)，則該遞減度節(jié)點序列表示為Sq(〈v1…vi〉).

根據(jù)定義3，如果節(jié)點序列Sq(〈v1…vi〉)中所有節(jié)點的度數(shù)都相等，并且序列的節(jié)點數(shù)|Sq|≥k，則該序列Sq可看作一個符合k-匿名要求的簇序列.

(1)

定義4中，簇的信息損失量衡量了單個匿名簇內(nèi)節(jié)點度變化對網(wǎng)絡(luò)原有結(jié)構(gòu)造成的影響程度.在此基礎(chǔ)上，可進一步通過累加所有匿名簇的信息損失量獲得整個社會網(wǎng)絡(luò)匿名化的信息損失代價，即原始網(wǎng)絡(luò)G與匿名網(wǎng)絡(luò)G′間的節(jié)點度變化量為：

(2)

定義5信息損失率(R)：滿足k-度匿名的社會網(wǎng)絡(luò)G′的信息損失量與其原始網(wǎng)絡(luò)G中總度數(shù)的比值稱為信息損失率：

(3)

式(3)中，I(G′/G)表示整個社會網(wǎng)絡(luò)匿名化的信息損失量，由式(2)計算；而對于原始網(wǎng)絡(luò)G的節(jié)點總度數(shù)，由圖的握手定理可得：當網(wǎng)絡(luò)G的邊數(shù)為|E|時，其總度數(shù)和為2|E|.

4　圖的k-度匿名隱私保護方法

針對建模成圖結(jié)構(gòu)的社會網(wǎng)絡(luò)，本文提出基于移邊操作的k-度匿名隱私保護方法，基本思路是將整個匿名化過程分為兩個步驟：(1)基于度的最優(yōu)簇劃分；(2)移邊操作重構(gòu)網(wǎng)絡(luò)圖實現(xiàn)k-度匿名化.

4.1基于度的最優(yōu)簇劃分

最優(yōu)簇劃分是以信息損失量最小化代價為目標對網(wǎng)絡(luò)節(jié)點進行簇劃分，并確定簇內(nèi)每個節(jié)點滿足k-度匿名的度數(shù).為了實現(xiàn)該目標，本文先將社會網(wǎng)絡(luò)G=(V,E)中節(jié)點集V按照定義3排序成遞減度序列形式：

然后基于節(jié)點度劃分成m個匿名簇，并使其滿足定義2中的k-度匿名要求，這樣匿名簇的度序列轉(zhuǎn)變?yōu)槿缦陆Y(jié)構(gòu)：

Sq′(〈v11v12…v1t1,v21v22…v2t2,vm1vm2…vmtm〉)

=〈vi1vi2…viti〉,

可以看出，對整個社會網(wǎng)絡(luò)節(jié)點的簇劃分等價于遞減度序列的簇劃分,并且要求信息損失量最少.我們采用動態(tài)規(guī)劃方法對遞減度序列結(jié)構(gòu)Sq進行簇劃分，動態(tài)規(guī)劃特別適合具有重疊子過程的多階段決策問題，要求出一個過程的最優(yōu)解必須求出其子過程的最優(yōu)解，這樣逐步遞推直到求出整個過程的最優(yōu)解.因此，本文提出最優(yōu)簇劃分的代價函數(shù)如式(4)所示.

(4)

約束為

(5)

算法1最優(yōu)簇劃分算法

輸入：網(wǎng)絡(luò)圖G中的節(jié)點遞減度序列Sq(v1,v2,…,vn)，匿名k度值.

輸出：最優(yōu)匿名簇Sq′的劃分序列號t1,…,tm.

1.ifn<2kthen

2.return簇序列Sq′(v1,v2,…,vn);

3.else//對于n≥2k情況

4.fori=n-k+1 tokdo

5.ifi>n-2k+1 then//當n-2k+1

6.form=itondo

8.endfor

9.elseifi>kthen //當k

10.由式(1)計算I(〈vi…vn〉);

11.endif

12.endfor

13.fort=kton-kdo

14.由式(1)計算I(〈v1…vt〉);

16.endfor

18.return最優(yōu)簇序列Sq′的劃分序號[t1,…,ti]；

19.endif

4.2網(wǎng)絡(luò)圖重構(gòu)算法

經(jīng)過最優(yōu)簇序列劃分后，網(wǎng)絡(luò)圖中每個節(jié)點將獲得實現(xiàn)k-度匿名化所屬簇的平均度數(shù).本文采用移邊方式實現(xiàn)匿名化操作，即將高于簇平均度的節(jié)點上的邊移動到低于簇平均度的節(jié)點上.實際上，移邊操作可等價于先刪除邊再增加邊這兩步原子操作，成功的移邊操作應(yīng)使其兩端節(jié)點都同時滿足度匿名的變化方向.

(6)

對于網(wǎng)絡(luò)中的任意邊來說，其兩端節(jié)點vi和vj的函數(shù)γ狀態(tài)共同決定了該邊是否符合增刪操作要求，如圖1所示6種狀態(tài)，除了圖1(f)中邊上兩端節(jié)點都已滿足匿名化要求外，剩余5種情況圖1(a)～(e)都需要通過增刪邊來改變節(jié)點度數(shù).不難得知，由于圖1(b)、(c)和(e)都至少有一端存在度關(guān)系“<”，因而不滿足移邊操作中需先刪除邊的前提條件，而只有圖1(a)和(d)滿足該前提條件，且節(jié)點度符合匿名變化方向.

為了保持圖結(jié)構(gòu)的連通性，移邊操作中的刪除邊與增加邊間存在必要的關(guān)聯(lián)條件是這兩條邊的端點在圖中體現(xiàn)互為連通鄰居.具體地，針對圖1(a)和圖1(d)的移邊方法分別對應(yīng)圖2(a)和圖2(b)，圖中移邊的先后步驟等于①刪除邊+②增加邊(虛線表示).圖2(a)中新增邊的兩節(jié)點vp和vq分別是被刪邊上節(jié)點vi和vj的連通鄰居，并且都有增加節(jié)點度要求.而圖2(b)中為了維持被刪邊上的節(jié)點vj度不變的要求，新增邊的一端必須從vj出發(fā)，而另一端則是vi中需增加節(jié)點度的連通鄰居.

為了實現(xiàn)基于移邊的網(wǎng)絡(luò)圖匿名化，本文給出滿足k-度匿名的重構(gòu)網(wǎng)絡(luò)圖算法2，算法中假設(shè)已知原始圖中各節(jié)點vi的度數(shù)Dg(vi).

算法2重構(gòu)網(wǎng)絡(luò)圖算法

輸出：重構(gòu)后的k-度匿名網(wǎng)絡(luò)圖G′

1.for each edge(vi,vj)∈Edo

3.forvp∈N(vi的連通分量) do

5.forvq∈N(vj的連通分量) do

7.{刪除edge(vi,vj)后兩端節(jié)點度-1;

8.增加edge(vp,vq)后兩端節(jié)點度+1;}

9.endif

10.endfor

11.endif

12.endfor

14.forvp∈N(vi的連通分量) do

16.{刪除edge(vi,vj)后節(jié)點Dg(vi)-1;

17.增加edge(vp,vj)后節(jié)點Dg(vp)+1;}

18.endif

19.endfor

20.endif

21.endfor

22.return重構(gòu)后的網(wǎng)絡(luò)G′

5　仿真實驗及結(jié)果分析

本文采用CA-GrQc數(shù)據(jù)集構(gòu)建社會網(wǎng)絡(luò)進行實驗與分析，該數(shù)據(jù)集包括5242個節(jié)點，14496條無向邊，度分布服從冪律分布.為了便于實驗比較和說明，我們將第4節(jié)所提出的社會網(wǎng)絡(luò)基于圖的k-度匿名隱私保護方法稱為SimilarGraph模型，算法代碼用Python編程實現(xiàn)，實驗環(huán)境為Intel(R) CoreTMi5 CPU 2.3GHz，4GB內(nèi)存，操作系統(tǒng)為Windows7.實驗方法是先由算法1對原始網(wǎng)絡(luò)數(shù)據(jù)集進行最優(yōu)的k-度匿名簇劃分，再用算法2進行移邊操作來重構(gòu)匿名化的網(wǎng)絡(luò)圖，然后采用Gephi工具對其可視化并對比網(wǎng)絡(luò)匿名化前后節(jié)點度變化及分布特征.

圖3(a)展示了原始社會網(wǎng)絡(luò)的節(jié)點度分布圖，節(jié)點度數(shù)越多則呈現(xiàn)越大，圖中共標注了8種度區(qū)間的節(jié)點分布情況.圖3(b)則顯示當k=50時匿名化網(wǎng)絡(luò)的分布圖，其度特征明顯下降，節(jié)點共被劃分成21個簇，與圖3(a)對比后發(fā)現(xiàn)，原始社會網(wǎng)絡(luò)中節(jié)點度大于70的顯著節(jié)點只有4個，對其成功攻擊的概率有1/4，而在匿名后的圖3(b)中，至少有50個以上節(jié)點與其相似，這樣攻擊概率便降至1/50以下.

圖4顯示了不同匿名k值下社會網(wǎng)絡(luò)度的冪律分布規(guī)律，圖中k=0時表示原始社會網(wǎng)絡(luò)的度服從冪律分布，其度數(shù)介于10到80之間的節(jié)點分布不均勻且同構(gòu)節(jié)點數(shù)偏少，度數(shù)大的節(jié)點最容易遭受攻擊，而實現(xiàn)不同k-度匿名化后的網(wǎng)絡(luò)度分布雖然也滿足冪律特征，但其結(jié)構(gòu)趨于均勻，最大節(jié)點度數(shù)隨著匿名k值增大而逐漸減少，節(jié)點聚集特性也越明顯，特別是當k值越大時匿名網(wǎng)絡(luò)中節(jié)點度大于10以上的同構(gòu)節(jié)點數(shù)越多，這樣大大增加了針對網(wǎng)絡(luò)度屬性攻擊的難度.

下面，將本文提出的模型SimilarGraph與經(jīng)典的k-度匿名方法SuperGraph[18]和最近Yuan等[19]提出的模型KDLD進行各項實驗指標對比，三者區(qū)別在于SimilarGraph采用移邊方法而SuperGraph則采用隨機增加邊方式實現(xiàn)網(wǎng)絡(luò)匿名化，對于KDLD則是通過增加噪聲節(jié)點來實現(xiàn)k-度匿名化.圖5比較了三種方法在實現(xiàn)不同k-度匿名化網(wǎng)絡(luò)過程中發(fā)生邊移動、增加或因噪聲節(jié)點而增加邊的變化數(shù)量，當匿名k值增大時，SimilarGraph實現(xiàn)匿名化所需移動的邊數(shù)增長較小且比較平穩(wěn)，而SuperGraph所需改變的邊數(shù)從222增加到2675條，KDLD也與其較一致，增長幅度都很顯著.總體上看，SimilarGraph的邊變化數(shù)遠小于SuperGraph和KDLD.

圖6進一步統(tǒng)計了三種方法實現(xiàn)匿名化后帶來的信息損失率結(jié)果，該指標由式(3)計算.圖6中SimilarGraph在實現(xiàn)不同k值匿名化網(wǎng)絡(luò)時由移邊操作所引起的信息損失率非常小，而SuperGraph和KDLD兩者都增加了大量邊而造成較大的信息損失率且增長趨勢較明顯，由此可見，SimilarGraph方法具有最理想的移邊代價.

另外，為了對比網(wǎng)絡(luò)匿名化前后的結(jié)構(gòu)特性變化，圖7、圖8和圖9分別給出了三種方法在不同k-度匿名化網(wǎng)絡(luò)中的聚類系數(shù)(CC)、節(jié)點平均度和平均路徑長度(APL)等指標結(jié)果，圖中用虛線表示了原始網(wǎng)絡(luò)的相關(guān)指標值，它不隨匿名k值而變化.由圖7可知，KDLD方法當k在50～70區(qū)間時由于增加了一些噪聲節(jié)點以及需增加、刪除相關(guān)邊，導致其CC指標出現(xiàn)較明顯的先升后降趨勢，整體網(wǎng)絡(luò)結(jié)構(gòu)變化較大，表現(xiàn)不穩(wěn)定，而SuperGraph方法隨k值增大而所增邊數(shù)越多造成CC指標逐漸下降.總體上看，本文的SimilarGraph方法在不同k值下一直最接近于原始網(wǎng)絡(luò)的聚類系數(shù)值，對匿名化后的網(wǎng)絡(luò)結(jié)構(gòu)影響最小.

圖8中當匿名k值增大時，SimilarGraph產(chǎn)生的匿名化網(wǎng)絡(luò)中節(jié)點平均度數(shù)與原始網(wǎng)絡(luò)基本相同，而KDLD方法使得不同k值匿名化的網(wǎng)絡(luò)節(jié)點平均度逐漸下降，對網(wǎng)絡(luò)結(jié)構(gòu)影響較小，SuperGraph則使匿名后的節(jié)點平均度增幅較大，表明該匿名方法比較嚴重地破壞了原始網(wǎng)絡(luò)結(jié)構(gòu).

圖9比較了網(wǎng)絡(luò)匿名化前后的平均路徑長度(APL)指標，三者之中本文的SimilarGraph表現(xiàn)最好，該方法使得匿名化的網(wǎng)絡(luò)APL在不同k值下都保持較小幅的下降且比較平穩(wěn)，而KDLD在匿名化后由于增加了一些噪聲節(jié)點導致APL指標有小幅度上升，SuperGraph則采用隨機增加邊方式引起匿名化網(wǎng)絡(luò)的APL指標有較大的下降.由此表明，SimilarGraph能保持比較穩(wěn)定的網(wǎng)絡(luò)內(nèi)在關(guān)系結(jié)構(gòu).

最后，由于本文實驗所選取的數(shù)據(jù)集CA-GrQc中節(jié)點無屬性標簽，因此，KDLD模型無法在相同條件下與SimilarGraph和SuperGraph比較抗惡意攻擊能力，圖10和圖11分別對比了SimilarGraph和SuperGraph兩種方法在不同k-度匿名值下的網(wǎng)絡(luò)劃分簇數(shù)量和遭受度攻擊的平均概率.從圖10統(tǒng)計的匿名簇數(shù)量對比來看，當匿名k值增大時，SimilarGraph和SuperGraph兩者在實現(xiàn)匿名化網(wǎng)絡(luò)時所劃分的簇數(shù)量都是逐漸減少且大致接近.另一方面，圖11中的平均攻擊概率等于對所有簇節(jié)點攻擊的概率平均值，概率值越小表示匿名化網(wǎng)絡(luò)抵御節(jié)點度攻擊的能力越強，由圖11結(jié)果可知，兩種方法都使得匿名化網(wǎng)絡(luò)遭受度攻擊的概率大大減小，而SimilarGraph抵御惡意攻擊的能力總體上優(yōu)于SuperGraph.

6　總結(jié)

現(xiàn)有社會網(wǎng)絡(luò)的隱私保護方法普遍存在比較嚴重的信息損失，以及匿名化后網(wǎng)絡(luò)結(jié)構(gòu)特征發(fā)生巨大改變的問題.針對這些不足，本文提出一種保護社會網(wǎng)絡(luò)關(guān)系數(shù)據(jù)的k-度匿名模型SimilarGraph，該模型先從網(wǎng)絡(luò)節(jié)點度序列出發(fā)運用動態(tài)規(guī)劃方法進行最優(yōu)簇劃分，然后，采用移動邊方式對網(wǎng)絡(luò)進行擾動，并進一步重構(gòu)網(wǎng)絡(luò)實現(xiàn)基于圖的k-度匿名化的隱私保護.最后，采用CA-GrQc數(shù)據(jù)集構(gòu)建社會網(wǎng)絡(luò)進行實驗與分析，各項實驗結(jié)果表明SimilarGraph方法能在網(wǎng)絡(luò)節(jié)點數(shù)和邊數(shù)都保持不變條件下以最小的信息損失代價移動關(guān)系邊實現(xiàn)網(wǎng)絡(luò)的k-度匿名化，克服了傳統(tǒng)匿名化算法存在嚴重的信息損失缺點，而且還有效保持了社會網(wǎng)絡(luò)結(jié)構(gòu)和內(nèi)在聯(lián)系的穩(wěn)定，同時提高了網(wǎng)絡(luò)抵御度屬性攻擊的能力.限于篇幅，我們下一步研究工作是改進本文所提出的匿名化模型實現(xiàn)并行化以求改變?nèi)謨?yōu)化過程計算復雜的局面，并考慮在更大的實際網(wǎng)絡(luò)數(shù)據(jù)集上進行實驗驗證其有效性.

[1]Boccaletti S,Latora V,Moreno Y,et al.Complex networks:structure and dynamics[J].Physics Reports,2006,424(4):175-308.

[2]Wang X F,Chen G R.Complex networks:small-world,scale-free and beyond[J].IEEE Circuits and Systems Magazine,2003,3(1):6-20.

[3]Faloutsos M,Faloutsos P,Faloutos C.On power-law relationships of the internet topology[A].ACM SIGCOMM'99[C].Cambridge,Massachusetts:ACM,1999.251-262.

[4]童云海,陶有東,唐世渭,等.隱私保護數(shù)據(jù)發(fā)布中身份保持的匿名方法[J].軟件學報,2010,21(4):771-781.Tong Yun-hai,Tao You-dong,Tang Shi-wei,et al.Identity-reserved anonymity in privacy preserving data publishing[J].Journal of Software,2010,21(4):771-781.(in Chinese)

[5]黃茂峰,倪巍偉,王佳俊,等.一種面向聚類的對數(shù)螺線數(shù)據(jù)擾動方法[J].計算機學報,2012,35(11):2275-2282.

Huang Mao-feng,Ni Wei-wei,Wang Jia-jun,et al.A logarithmic spiral based data perturbation method for clustering[J].Chinese Journal of Computers.2012,35(11):2275-2282.(in Chinese)

[6]張嘯劍,孟小峰.面向數(shù)據(jù)發(fā)布和分析的差分隱私保護[J].計算機學報,2014,37(4):927-949.

Zhang Xiao-jian,Meng Xiao-feng.Differential privacy in data publication and analysis[J].Chinese Journal of Computers,2014,37(4):927-949.(in Chinese)

[7]Campan A,Truta T M,Cooper N.P-sensitive K-anonymity with generalization constraints[J].Transactions on Data Privacy,2010,3(2):65-89.

[8]Campan A,Truta TM.A clustering approach for data and structural anonymity in social networks[A].2nd ACM SIGKDD International Workshop on Privacy,Security,and Trust in KDD(PinKDD'08)[C].Las Vegas,NV:ACM,2008.33-54.

[9]王智慧,許儉,汪衛(wèi),等.一種基于聚類的數(shù)據(jù)匿名方法[J].軟件學報,2010,21(4):680-693.

Wang Zhi-hui,Xu Jian,Wang Wei,et al.Clustering-Based approach for data anonymization[J].Journal of Software,2010,21(4):680-693.(in Chinese)

[10]張健沛,謝靜,楊靜,等.基于敏感屬性值語義桶分組的t-closeness隱私模型[J].計算機研究與發(fā)展,2014,51(1):126-137.

Zhang Jianpei,Xie Jing,Yang Jing,et al.At-closeness privacy model based on sensitive attribute values semantics bucketization[J].Journal of Computer Research and Development,2014,51(1):126-137.(in Chinese)

[11]付艷艷,張敏,馮登國,等.基于節(jié)點分割的社交網(wǎng)絡(luò)屬性隱私保護[J].軟件學報,2014,25(4):768-780.

Fu Yan-yan,Zhang Min,Feng Deng-guo,et al.Attribute privacy preservation in social networks based on node anatomy[J].Journal of Software,2014,25(4):768-780.(in Chinese)

[12]Wu W T,Xiao Y H,Wang W,et al.k-symmetry model for identity anonymization in social networks[A].13th International Conference on Extending Database Technology(EDBT’10)[C].Lausanne,Switzerland:ACM,2010.111-122.

[13]Ying X,Wu X.On link privacy in randomizing social networks[J].Knowledge and Information Systems,2011,28(3):645-663.

[14]劉華玲,鄭建國,孫辭海.基于貪心擾動的社交網(wǎng)絡(luò)隱私保護研究[J].電子學報,2013,41(8):1586-1591.Liu Hua-ling,Zheng Jian-guo,Sun Ci-hai.Privacy preserving in social networks based on greedy perturbation[J].Acta Electronica Sinica,2013,41(8):1586-1591.(in Chinese)

[15]劉向宇,王斌,楊曉春.社會網(wǎng)絡(luò)數(shù)據(jù)發(fā)布隱私保護技術(shù)綜述[J].軟件學報,2014,25(3):576-590.

Liu Xiang-yu,Wang Bin,Yang Xiao-chun.Survey on privacy preserving techniques for publishing social network data[J].Journal of Software,2014,25(3):576-590.(in Chinese)

[16]Hay M,Miklau G,Jensen D,et al.Resisting structural re-identification in anonymized social networks[J].The VLDB Journal,2010,19(6):797-823.

[17]Skarkala M E,Maragoudakis M,Gritzalis S,et al.Privacy preservation by k-anonymization of weighted social networks[A].Proceedings of the 2012 International Conference on Advances in Social Networks Analysis and Mining(ASONAM)[C].Istanbul,Turkey:IEEE Computer Society,2012.423-428.

[18]Liu K,Terzi E.Towards identity anonymization on graphs[A].2008 ACM SIGMOD International Conference on Management of Data(SIGMOD’08)[C].New York:ACM,2008.93-106.

[19]Yuan M X,Chen L,Yu P S,et al.Protecting sensitive labels in social network data anonymization[J].IEEE Transactions on Knowledge and Data Engineering,2013,25(3):633-647.

[20]Zhou B,Pei J.The K-anonymity and L-diversity approaches for privacy preservation in social networks against neighborhood attacks[J].Knowledge and Information Systems,2011,28(1):47-77.

[21]Zheleva E,Getoor L.Preserving the privacy of sensitive relationships in graph data[A].1st ACM SIGKDD Workshop on Privacy,Security,and Trust in KDD (PinKDD'07)[C].San Jose,CA:ACM,2007.153-171.

[22]Zou L,Chen L,?zsu M T.K-automorphism:a general framework for privacy preserving network publication[J].Proceedings of the VLDB Endowment,2009,2(1):946-957.

龔衛(wèi)華男，1977年生于湖北武漢，博士，現(xiàn)為浙江工業(yè)大學計算機學院副教授.主要研究方向：數(shù)據(jù)挖掘、社會網(wǎng)絡(luò)、大數(shù)據(jù)計算等.

E-mail:whgong@sohu.com

蘭雪鋒男，1990年生于浙江麗水，浙江工業(yè)大學碩士生.主要研究方向：社會網(wǎng)絡(luò)、隱私保護.

裴小兵男，1971年生于湖北，博士，現(xiàn)為華中科技大學軟件學院副教授.主要研究方向：機器學習、數(shù)據(jù)挖掘、軟件工程、電信網(wǎng)絡(luò)管理.

E-mail:xiaobingp@hust.edu.cn

楊良懷男，1967年生于浙江新昌，博士，現(xiàn)為浙江工業(yè)大學計算機學院教授，主要研究方向：數(shù)據(jù)庫系統(tǒng)、數(shù)據(jù)挖掘、大數(shù)據(jù)計算等.

E-mail:yanglh@zjut.edu.cn

Privacy Preservation Method Based on k-Degree Anonymity in Social Networks

GONG Wei-hua1,LAN Xue-feng1,PEI Xiao-bing2,YANG Liang-huai1

(1.SchoolofComputerScienceandTechnology,ZhejiangUniversityofTechnology,Hangzhou，Zhejiang310023,China;2.SchoolofSoftwareEngineering,HuazhongUniversityofScienceandTechnology,Wuhan，Hubei430074,China)

To preserve the privacy of social networks,most existing methods are applied to satisfy different anonymity models,but some serious problems are involved such as often incurring large information losses and great structural modifications of original social network after being anonymized.Therefore,an improved privacy protection model called SimilarGraph is proposed,which is based onk-degree anonymous graph derived fromk-anonymity to keep the network structure stable.Where the main idea of this model is firstly to partition network nodes into optimal number of clusters according to degree sequences based on dynamic programming,and then to reconstruct the network by means of moving edges to achievek-degree anonymity with internal relations of nodes considered.To differentiate from traditional data disturbing or graph modifying method used by adding and deleting nodes or edges randomly,the superiority of our proposed scheme lies in which neither increases the number of nodes and edges in network,nor breaks the connectivity and relational structures of original network.Experimental results show that our SimilarGraph model can not only effectively improve the defense capability against malicious attacks based on node degrees,but also maintain stability of network structure.In addition,the cost of information losses due to anonymity is minimized ideally.

social network；privacy preservation；k-degree anonymity；information loss

2015-01-25；修回日期：2015-10-23；責任編輯：梅志強

浙江省自然科學基金(No.LY13F020026,No.Y1080102,No.LY14F020017,No.LY14C130005)；國家自然科學基金(No.61571400,No.61070042)；中國博士后科學基金(No.2015M581957)；浙江省博士后科研項目擇優(yōu)資助(No.BSH1502019)

TP309.2

A

0372-2112 (2016)06-1437-08