一種遺傳算法實現的圖聚類匿名隱私保護方法

姜火文 曾國蓀 胡克坤

1(同濟大學計算機科學與技術系 上海 200092)2(江西科技師范大學數學與計算機科學學院 南昌 330038)3(嵌入式系統與服務計算教育部重點實驗室(同濟大學) 上海 200092) (hwjiang@tongji.edu.cn)

?

一種遺傳算法實現的圖聚類匿名隱私保護方法

姜火文1,2,3曾國蓀1,3胡克坤1,3

1(同濟大學計算機科學與技術系 上海 200092)2(江西科技師范大學數學與計算機科學學院 南昌 330038)3(嵌入式系統與服務計算教育部重點實驗室(同濟大學) 上海 200092) (hwjiang@tongji.edu.cn)

聚類匿名是一種典型的社交網數據發布隱私保護方案，其基礎工作是圖聚類.圖聚類為一類NP難的組合優化問題，便于使用搜索優化算法.現有圖聚類匿名方法缺少此類啟發式搜索算法.為此，研究一種利用遺傳算法實現的圖聚類匿名方法,利用貪心法進行結點聚類預劃分，以構造初始種群；依據關系擬合理論建立個體適應度函數；根據個體編碼特點，分別提出一種多點錯位的交叉算子和基因位交換的變異算子.圖聚類模型綜合考慮了結點的結構和屬性信息，而遺傳算法的全局化搜索優化能力保障了圖聚類質量，因此，該方法具有較強的隱私保護性.實驗表明了該方法在提高聚類質量和減小信息損失方面的有效性.

社交網絡；圖聚類；隱私保護；k-匿名；遺傳算法

隨著網絡社交平臺的迅猛發展，社交網絡里積累下海量個人及其社會關系信息，構成一類具有重大潛在價值的圖大數據.同時，這些圖數據也蘊含了大量用戶不愿意被公眾獲知的隱私.近年來，在維持社交網絡數據可用性的同時如何保護個人隱私，成為一個嚴峻的問題[1].社交網絡中隱私信息類型廣泛，例如用戶的難言性“疾患”、不愿披露的“薪酬”等屬性值,用戶間聯系頻度(一般意味著某種親密關系或伙伴關系)等.面對惡意的隱私盜取，那種僅將用戶身份信息隱去的簡單匿名方法并不能防止隱私泄露.因為網絡圖上結點和邊的屬性及拓撲結構等信息都可能被用于識別用戶身份[2].例如某結點的度或d-鄰域結構可能導致該結點被唯一或高概率地識別出來[3-4].另外，在屬性-社交網絡場景中，用戶即使未標記某隱私屬性，但也可能被推測出較大概率地具有該隱私屬性[5].例如，雖然某用戶沒有公開其宗教信仰，但根據其絕大多數朋友都喜歡聽佛教音樂，可以較大概率地推測其信奉佛教[6].劍橋大學一項研究也表明，Facebook上“likes”某些事物將會暴露用戶的智商、性取向、宗教信仰等重要信息[7].

k-匿名是一種已廣泛應用于關系表數據發布的隱私保護機制，目前也多被運用到社交網絡數據發布隱私保護，結點k-匿名即為一種應用機制.結點k-匿名的思想是將網絡圖中所有結點聚類成一些超點，每個超點至少包含k個結點，超點中結點相互之間不可區分，因此在該社交網絡中，受結點再識別攻擊而導致隱私泄露的概率小于1k[6].可見，結點k-匿名的實質是圖聚類匿名.如圖1所示，設圖1(a)為社交網絡模型圖，圖1(b)即為圖1(a)的結點2-匿名圖.圖聚類匿名的一個關鍵問題是圖聚類方法的選擇，因為聚類方法決定聚類結果，影響匿名效果.理論上求最佳聚類結果實質是一類NP難的組合優化問題，一般使用啟發式搜索算法更容易找到優質解.

Fig. 1 The social network graph and its anonymity graph.圖1 社交網絡模型圖及其匿名圖

現有圖聚類匿名方法中常見貪心聚類方法、有序聚類方法等，缺少智能搜索算法.為此，本文研究用遺傳算法實現網絡圖聚類匿名保護，綜合結構和屬性的相似性，對結點進行聚類劃分后匿名發布.本文的主要貢獻為:

1) 引入遺傳算法進行圖聚類匿名隱私保護；

2) 量化結點間結構和屬性的相似性，提出基于屬性加權圖聚類的種群初始化算法；

3) 根據機器學習中的關系擬合理論，提出個體適應度求值算法；

4) 根據個體編碼特點，提出一種多點錯位的交叉算法和交換基因位的變異算子.

1 相關工作

目前，k-匿名機制在社交網絡數據隱私保護中占有重要地位.根據采用匿名方法的不同，k-匿名方案基本分為基于結構變換和基于超級結點的兩大類[8].基于結構的變換常見基于結點的度數或鄰居圖等結構特征，構造k-度匿名或k-子圖匿名，其采用的手段主要是邊、結點的增、刪修改.例如：為防范根據結點度的識別攻擊，Liu等人[1]分別設計了基于分治法和最大鄰差的2種度序列劃分算法，并籍以構建了k-度匿名圖；為抵御基于子圖結構的攻擊，Zou等人[9]提出一種匿名化算法，使匿名圖中總能找到k個不同的同構子圖；同樣為抵御基于結點1-鄰域子圖的識別攻擊， Zhou等人[3]借鑒關系數據隱私保護的(k,l)匿名模型，提出一種適用于社交網絡數據，滿足k-匿名和l多樣性的匿名方法，并證明其為NP難問題；為保證邊的匿名性，Cheng等人[10]提出一種k-同構匿名化算法，能夠防止對邊存在性的合理推測；為防止可能根據結構信息或共享敏感屬性的雙重攻擊，Yuan等人[4]通過在原圖中添加噪音結點的方法，構造了一種k-度-l-多樣性匿名模型.基于超級結點的變換實際就是結點k-匿名方案，最早由Zheleva等人[11]提出這一模型.其后，針對不同的防范背景或性能要求等情形，研究者對這一模型進行了不同的修改完善，提出了多種結點聚類匿名方法.Campan等人[12]首次提出一種結點聚類匿名的貪心算法SaNGreeA,可以同時保護結點非標識屬性和連接關系，同時針對匿名過程產生的結構信息損失給出了一種定量計算方法；Wang等人[13]提出一種貪心聚類算法MASN，對SaNGreeA算法進行了改進，使其具備保護敏感屬性的功能，可以抵御同質化攻擊；SaNGreeA[12]算法和MASN[13]算法都是對無權圖的聚類匿名，針對帶權圖的匿名保護， Skarkala等人[14]提出一種與SaNGreeA近似的方法，設置超邊權重為原連接邊的平均權重，將超邊間包含的具體邊權重隱藏起來，起到保護作用，其中超點結構能將用戶身份泄露概率降至1k以內.另外Tassa等人[15]提出基于有序聚類的匿名方法，可以實現集中式網絡環境下的數據隱私保護，同時首次針對結點間不完全可見的分布式圖數據的隱私保護，設計了有序聚類匿名算法；Yang等人[16]則提出一種基于安全協議的EM算法，針對非連接結點間互不可見的圖數據實現了結點聚類.

2 問題模型與定義

社交網絡表現為特定群體中多個個體及他們間相互聯系組成的集合，最適合用圖來表示.其中，結點表示個體；邊表示個體間的聯系；個體的特征信息，如職業、年齡、學歷等是刻畫個體的重要數據，統稱為結點屬性，通常以一個屬性值向量表示.常見的社交網絡結構模型為簡單的圖模型G(V,E)，這只是考慮了用戶結點及其連接關系，并沒有考慮結點屬性信息.為全面刻畫社交網絡數據，我們定義社交網絡圖如下：

定義1. 社交網絡圖. 對包含了用戶屬性數據和用戶間社交關系數據的社交網絡，用圖模型描述，形式化表示為一個三元組，即G=(V,E,A)，稱這個圖G為社交網絡圖.

在圖G中，V={v1,v2,…,vn}為圖中結點集；E={(vi,vj)|1≤i,j≤n,i≠j}為邊集；A={a1,a2,…,as}為結點的屬性集.圖中任何邊(vi,vj)表示結點之間的聯系，為結構邊.根據實際網絡中實體間聯系的緊密程度不同，結構邊可以賦予不同的權值.本文假定各結構邊具有相等的權值，均為1，則圖連接的拓撲結構可以表示為鄰接矩陣形式：

圖中所有n個結點的屬性值可用矩陣Attr=(αit)n×s表示，其中?i∈{1,2,…,n}，有αit∈at，t∈{1,2,…s}.屬性at可能為數值型或類別型，例如，型如(職業，年齡)的二維屬性集，“職業”屬性為類別型，其屬性值為離散型文本；“年齡”屬性為數值型，其屬性值為實數.屬性類型差異不便于統一度量其相似度，為此分開度量.?αit,αjt∈Attr，定義其屬性相似度計算為

Asim(αit,αjt)=

定義2. 屬性加權圖. 對圖G中任意2個結點vi和vj，如果Asim(vi,vj)≠0 ,認為在vi和vj間存在一條權值為Asim(vi,vj)的屬性邊，并將其和結構邊合并，合并后的邊權值取為原兩者權值和.由此得到的帶權圖，稱為屬性加權圖，記為GSA.

定義3. 圖聚類. 根據結點間的某種相近或相似性，利用聚類方法將社交網絡圖的所有結點劃分成一些聚類(簇)，這個過程成為圖聚類.

圖聚類可以表示為社交網絡圖G上的一種映射關系φ:(v1,v2,…,vn)→(V1,V2,…,Vm)，φ滿足2個條件：

2) 1≤?i,j≤m，i≠j，Vi∩Vj=?.

定義4.k-聚類匿名圖. 對社交網絡圖G進行圖聚類，使每個簇內結點數不小于k.隱匿各簇內所有結點的連接結構和屬性值，每一簇構成的子圖用一個超點取代.子圖內各結點的屬性值被統一概化成一個超點的屬性值；超點上標明所隱含的用戶結點個數和內部邊的條數；任意2個簇間，若原來共有t條邊相連，則只用一條帶權值t的超邊取代；若原來沒有任何邊相連，則沒有超邊相連.由此得到由m個超點構成的“濃縮”了的圖，稱為k-聚類匿名圖.

Fig. 2 The generalization hierarchy tree of “occupation” attribute.圖2 “職業”屬性的概化層次樹

圖1(b)即為圖1(a)聚類匿名后得到的一個2-聚類匿名圖.聚類匿名過程需要對各超點作屬性概化處理，將超點內所有結點的屬性值概化成一個屬性值.屬性類型不同其概化方法也不一樣，類別型屬性的屬性概化需要根據概化層次樹進行，為此需要預先為每一個類別型屬性建立概化層次樹，例如圖2即為一棵概化層次樹.樹中葉子結點為各個用戶結點的屬性值，各分支結點即為以其為根結點的子樹中各葉子結點的概化值，根結點表示圖中所有結點在該屬性上的概化值.記超點Vt中各結點在屬性ai上的取值集合為ai(Vt)，屬性概化方法為：如果ai是數值型，則其概化值為[minai(Vt),maxai(Vt)],如果ai是類別型，則其概化值取為ai(Vt)上所有葉子結點的最小上界結點.

ail(Vi,t)=

圖G的若干相似結點聚類為一超點，對外只發布超點的某些統計特性，表現為一個結點和屬性值，隱藏了超點內的連接結構和各用戶結點的屬性信息，這體現為泛化技術的思想，能夠防范常見的結構化攻擊.可見，k-聚類匿名過程融合了隱私保護技術中的泛化技術和k-匿名技術，能夠有效防范基于圖結構或結點屬性等背景知識的隱私推理攻擊，將其攻擊成功率至少降至1k以內，因而具有很強的隱私保護效果.對于大型社交網絡，其k-聚類匿名只是在全局范圍內作了一些微觀“濃縮”，只要k不很大(一般取3～5即可保證隱私強度)，原社交網絡圖的宏觀結構與特性及蘊含的主要信息得以基本保持，故匿名后的圖數據仍然具有較高的可用性.

3 圖K-聚類匿名化遺傳算法

遺傳算法是一種模擬自然界生物進化過程的隨機化搜索算法，特別適用于處理需要在復雜而龐大的搜索空間中尋找最優解的問題.圖聚類匿名保護方法主要工作基礎是圖聚類，為一類典型的NP難問題，適合用遺傳算法搜索最優解.本文研究利用遺傳算法對圖G進行k-聚類匿名化操作，以達到圖數據隱私保護目的，方法的主要特點體現在種群初始化、適應度函數和交叉算子等3個計算部分.本節按算法流程先分節闡述各主要步驟，然后給出算法的整體描述.以下均假定圖結點個數為n、每個結點包含s個屬性、聚類個數為m、種群規模為q.

3.1 個體編碼

種群中的每個個體都對應問題的一個解，假定對圖中n個結點編號，問題的解適合用一個n維整數向量P=(p1,p2,…,pn)表示.這里，P中的任意一個pi表示結點vi所在的簇號，即：?i∈{1,2,…,n}，pi∈{1,2,…,m}.顯然，?i,j∈{1,2,…,n}，i≠j，pi=pj表示結點vi和vj聚類在同一簇內.為此，我們采用這個十進制n維整數向量P作為個體編碼，也稱為染色體.例如，對7個結點的圖，個體編碼(1,2,1,3,2,1,3)表示聚類結果為{V1={v1,v3,v6}，V2={v2,v5}，V3={v4,v7}}.為表述方便，規定pi也記為P(i)，如種群中某個染色體Px的第i個基因值，記為Px(i).

3.2 種群初始化

算法1. 個體初始化算法Initchrom(WSA).

輸入：屬性加權圖鄰接矩陣WSA；

輸出：染色體P.

① P=(0,0,…,0)；

②clus=1；*clus表示聚類編號*

③nodes=n；*nodes表示未劃分的結點數*

④ ?i∈{1,2,…,n}，P(i)=clus，C={i}；

⑤ Whilenodes≥2kdo*逐個劃分聚類*

⑥ While |C|

⑦maxsum=0;

⑧ Fori=1 tondo*選取結點添加*

then

3.3 個體適應度

適應度用于評價個體的優劣，直接影響下一代種群的產生，從而引導種群進化方向，在遺傳算法中起到舉足輕重的重要.給定任意一個染色體Px，Px對應圖結點集V上的一種聚類劃分結果，而集合V上的任意一種劃分結果可以確定V上元素間的一個等價關系.設Px確定的等價關系為Rx，顯然，Px對應的劃分結果就是商集VRx；?vi,vj∈V，若〈vi,vj〉∈Rx，則等價類[vi]Rx=[vj]Rx，即vi和vj在同一簇中.抽象層面看，圖聚類是一個對圖結點集合劃分成多個簇的過程，劃分的依據就是相似性，這種相似性可以被看成定義在圖結點集上的一個二元關系，稱為相似關系，不妨記為S.如屬性加權圖鄰接矩陣WSA即定量反映其一種相似程度，設定一個閾值l，規定：若vi和vj的相似度大于l，即>l時，vi和vj的相似關系成立，即序偶〈vi,vj〉∈S.根據WSA的定義特點，不難理解，這個相似關系是自反的、對稱的，但并非可傳遞的.

從機器學習角度理解，聚類是一種無監督的學習過程，S代表學習前的先驗知識，Rx是學習后的后驗知識.根據機器學習理論，好的聚類結果應該是最高程度擬合S的那個Rx.為此，我們定義|Rx∩S||Rx|為適應度函數，其中，Rx∩S表示關系Rx和S的交集，|Rx|表示Rx中的序偶個數.顯然|Rx∩S||Rx|∈[0,1]，|Rx∩S||Rx|越大，Px越好.下面給出|Rx∩S||Rx|的求解算法.

算法2. 染色體Px的適應度求解算法Fitval(WSA,l,Px).

輸入：矩陣WSA、閾值l、染色體Px；

輸出：適應度函數值.

①rs=0，r=0；*初始化*

② For eachc[i] do*初始化*

③c[i]=0；

④ End For

⑤ Fori=1 tondo

⑥c[Px(i)]=c[Px(i)]+1；

⑦ Forj=1 tondo*計算|Rx∩S|*

⑨rs=rs+1；

⑩ End If

算法2的計算量主要在于計算|Rx∩S|，其計算過程是一個雙層循環，內層循環次數和外層循環次數均為結點個數n，故算法2的時間復雜度為O(n2).

3.4 遺傳算子

3.4.1 選擇

選擇算子直接把優良的個體遺傳到下一代，是對種群的優勝劣汰操作.選擇算子需要在評估各個個體適應度的基礎上進行，為此，對種群的每一個染色體Pi，先計算其適應度函數值Fitval(WSA,l,Pi).本文采用經典的賭輪選擇法進行選擇操作，方法是：

1) 根據式:

g(i)=Fitval(WSA,l,Pi)

計算每個染色體Pi的選擇概率g(i)；

3) 在[0,1]區間內產生一個均勻分布的隨機數rand，若rand≤prob1，則染色體P1被選中；若probi-1

以上步驟3重復執行q遍，即重新構成規模為q的種群.

3.4.2 交叉

由3.1節可知，染色體編碼值只是簇的一個相對編號，不同染色體間的編碼值并無必然關聯，沒有可比性.即同一染色體中的相同編碼值可表示對應的結點在同一簇中，但不同染色體間的相同編碼值可能表示不同簇.故這里交叉操作不能簡單地采用2個染色體間對應基因位的一點或多點交叉，因為交叉后2個染色體間相同的編碼號會產生混淆，也幾乎必定會導致簇的大小不合規定.

針對本文染色體編碼特點，我們提出一種多點錯位交叉法：設2個交叉染色體為Px和Py，首先，分別從1到n位掃描兩者的所有編碼，如果聚類數m為奇數，將所有值為偶數的不同編碼值按出現順序排列，得到分別對應Px和Py的2個整數序列A=(a1,a2,…,at)和B=(b1,b2,…,bt)，這里t=(m-1)2，A或B中的各整數都為互不相同的偶數；如果m為偶數，則將所有值為奇數的不同編碼值按出現順序排列，得到的整數序列A或B中都為互不相同的奇數值，且t=m2.然后，對Px和Py中從1到n位中的所有偶數值編碼(如果m為奇數)或奇數值編碼(若m為偶數)，分別用B和A逐遍取代.下面給出該交叉算法.

算法3. 染色體交叉算法Crossover(Px，Py).

輸入：2個待交叉操作的染色體Px和Py；

輸出：交叉算子后的2個染色體Px和Py.

①m=nk;*初始化，m取整除后的整數商*

② A=(0,0,…,0);

B=(0,0,…,0);

e=0;

f=0;*初始化*

③ Ifodd(m) then*m為奇數時偶數編碼值交叉*

④ Fori=1 tondo*Px(Py)中相異偶數編

⑤ If (Px(i)為偶數且不在A中) then

⑥ Px(i)放入A中；*Px中相異偶數編

⑦ End If

⑧ If (Py(i)為偶數且不在B中) then

⑨ Py(i)放入B中；*Py中相異偶數

⑩ End If

Px(Py) 中偶數編碼值*

取代Px中偶數編碼值*

取代Py中偶數編碼值*

類上；

算法3的計算量主要在將Px(和Py)中所有不同的偶數編碼值放入A(和B)中，通過一個執行次數為n的for循環語句完成.循環體主要是判斷某個Px(i)是否在A中和Py(i)是否在B中，其執行次數分別等于變化中的A和B的元素個數，其上限為m2,故算法3的時間復雜度為O(n×m).交叉算子是產生新個體的主要方法，藉由交叉算子，遺傳算法的全局搜索能力得以巨大提高.

3.4.3 變異

變異操作一般是根據變異概率對染色體的某些基因值作變動，以形成一個新的個體.根據本文染色體編碼特點，變異操作并不能簡單地選定某些基因位作編碼值改變，因為可能導致相關簇的元素個數小于k.為按變異概率(取1‰)改變個體某些基因值，又不產生錯誤染色體，本文提出變異算子是：從種群中任選半數(q2個)染色體，對選出的每個染色體的所有基因位，每隔1 000位(包括最后不足1 000個的基因位)選取首尾2個基因位，交換其編碼值.如當n=1600時，對染色體Px，分別是Px(1)和Px(1000)交換數值、Px(1001)和Px(1600)交換數值.可以計算出變異基因位的數目為：(q2)×(n1000×2)，因為q2和n1000都只能取整數值，我們取不小于其相應實數值的最小整數，故變異概率(變異基因位數總基因位數)等于或略大于1‰.變異算子是產生新個體的輔助方法，它決定了遺傳算法的局部搜索能力.交叉和變異相互配合，共同完成對解空間的全局和局部搜索.

3.5 圖聚類匿名隱私保護的遺傳算法

遺傳算法的主體包括染色體編碼、種群初始化、適應度求值和遺傳算子4個重要部分.基于上述3.1～3.4節的內容，本節提出一種圖聚類匿名隱私保護的遺傳算法(genetic algorithm for clustering-anonymity graph privacy preservation, GA-CAG).算法步驟是：1)初始化種群；2)計算各染色體的適應度；3)判斷當2次迭代平均適應度值小于某個閾值λ(取0.0001)或迭代次數t大于預設值T(取200)時結束迭代，否則繼續遺傳迭代；4)依次執行選擇-交叉-變異這3個遺傳算子后返回步驟2)；5)根據適應度值最大的染色體進行聚類匿名后輸出結果，算法結束.GA-CAG算法描述如下：

算法4. 圖聚類匿名隱私保護的遺傳算法GA-CAG(G).

輸入: 社交網絡圖G；

輸出:k-聚類匿名圖G′.

①t=0；*t為當前迭代次數*

②FS=0；*FS為各個體適應度和*

③dif=0；*dif為相鄰兩代FS值差*

④ 按θ=0.5求出屬性加權圖鄰接矩陣WSA；

⑤ Fori=1 toqdo*初始化種群*

⑥Initchrom(WSA)；

⑦ End For

⑧ Fori=1 toqdo*求個體的適應度和*

⑨FS=FS+Fitval(WSA,l,Pi)；

⑩ End For

上述算法4描述表明，GA-CAG算法的主要工作在迭代搜索最優圖聚類結果，而完成每次迭代的主要計算量在于求各個體適應度和執行“選擇-交叉-變異”遺傳算子.根據3.3節論述，算法2求各適應度的時間復雜度為O(n2)；根據3.4節的論述，3種遺傳算子的主要工作在于算法3的交叉算子，其時間復雜度為O(n×m).故GA-CAG算法的時間復雜度大致為T×(O(n2)+O(n×m))，由于T為預設的迭代次數常量(本文取為50)，可以認為GA-CAG算法的時間復雜度仍然為O(n2).

4 實驗與結果分析

本節通過實驗分析本文所提GA-CAG算法的性能，實驗過程與功能相似的SaNGreeA[12]算法和MASN[13]算法進行比較，考慮可比性更好，對其中的參數α，β和l均分別設定為0.5,0.5和2.實驗數據來自UC Irvine Machine Learning Repository[12]①http://www.ics.uci.edu/～mlearn/MLRepository.html的Adult數據集，分別從中任意取500個結點和800個結點構成的社交網絡，記為DS1和DS2，各組實驗均分別在這2組數據集上進行.實驗環境為：Intel?CoreTMi5-4210U CPU @ 1.70 GHz(2394 MHz)；4.00 GB(1600 MHz)內存；希捷ST ST500LM000-SSHD-8 GB(500 GB)主硬盤；Microsoft Windows 8.1中文版 (64 b)操作系統；算法均采用Microsoft Visual C++ 7.0實現.由于算法的每次執行結果可能會略有不同，每組實驗重復進行5次，結果取其平均值.

4.1 聚類質量分析

GA-CAG算法的關鍵工作是圖聚類，為此，本節引入聚類密度和聚類熵2個評價指標[17]，各自通過1組實驗，以對比分析算法的聚類質量.聚類密度和聚類熵可以分別反映結構上和屬性上的聚類效果[17].本節2組實驗均在DS1和DS2數據集上進行.第1組實驗是聚類密度的對比分析，定義聚類密度為

圖3(a)和圖3(b)分別給出了在兩者數據集上3種算法的聚類密度對比及其隨k值變化的規律.從圖3可見：在兩者數據集上，3種算法的聚類密度值都比較接近，總體上GA-CAG算法的density值略高.相比圖3(a)，在圖3(b)上density值落差略大，反映出在結構上的聚類效果，當數據量不大時，3種算法非常相近，當數據規模變大，差別也有所變大，但總體差距不大.圖3(a)(b)均顯示隨k值增大，聚類密度趨大變化，這是因為k值變大則聚類數目減少，聚類之間的聯系將減少，即各超邊所隱匿的外部邊總數減少，相應地所有簇中的內部邊總數增加，因而聚類密度變大.

Fig. 3 The comparison of cluster density in datasets of DS1 and DS2.圖3 在DS1和DS2數據集上的聚類密度比較

第2組實驗是聚類熵的對比分析，聚類熵定義為

Fig. 4 The comparison of cluster entropy in datasets of DS1 and DS2.圖4 在DS1和DS2數據集上的聚類熵比較

Fig. 5 The comparison of the information loss of attribute in datasets of DS1 and DS2.圖5 在DS1和DS2數據集上的屬性信息損失比較

4.2 信息損失分析

匿名帶來的數據信息損失可以大致反映匿名后的數據可用性，一般信息損失越大意味著數據可用性越差.本節我們通過2組實驗分別比較分析算法的屬性信息損失和結構信息損失.各算法執行過程中，屬性信息損失值AIL和結構信息損失值NSIL均按第2節所討論到的計算方法求得，各類別屬性的概化層次樹均參照文獻[12]給出.

圖5給出了屬性信息損失值AIL隨k值變化的實驗結果，從圖5中可見，隨著k值的變大，屬性信息損失呈增大趨勢.究其原因是：k值變大則每個聚類中的結點個數增多，各超點內部可能有更多的相異屬性值被概化成同一個屬性值，這個概化屬性值對數值屬性而言可能將有更廣的域值范圍，對類別屬性而言可能將有更高的概化層次，故每個原結點的概化程度都可能變大，導致AIL值變大.圖5還顯示GA-CAG與MASN分別有最小和最大的AIL值，但總體差別不顯著，說明GA-CAG通過遺傳算法強大的搜索功能找到了更優解，而MASN在SaNGreeA的基礎上通過l值使各聚類中的結點避免出現單一屬性值，導致結點的概化程度可能增大，故其AIL值又比SaNGreeA算法略大.對比圖5(a)和圖5(b)可見，后者的屬性信息損失略微增大.這個結果可以從2個方面得到解釋，首先，因為AIL主要與屬性個數和體現隱私保護強度的k值有關，而DS1與DS2上的屬性個數相等，故兩者在同等k值上的AIL值接近；其次由于后者數據規模大時，平均每個聚類中可能有更大比例的不同屬性值被隱匿，以致AIL略有增大.

圖6給出了結構信息損失值NSIL隨k值變化的實驗結果，可以發現，NSIL值隨k值增大而增大，這是因為：k值增大則各超點構成的子圖規模將變大，子圖隱匿時將明顯造成更多的邊被隱藏，故導致NSIL值增大明顯.另一方面，宏觀上說，各聚類的規模增大而聚類數減少，意味著圖結點劃分更粗糙，整體圖結構的局部“濃縮”程度更為顯著，自然對整個圖結構的損失更大.圖6也可見，GA-CAG有相對最小的NSIL值，這也反映本文遺傳算法能搜索到較好解；而SaNGreeA和MASN的NSIL值基本沒有差別，這是因為這2種算法本身在功能上的差別對邊的隱藏數目沒有實質影響，即相等k值下兩者匿名所造成的隱匿邊的數目理論上沒有差別，具有一定的隨機性.比較圖6(a)和圖6(b)的結果，發現兩者基本沒有差別，考慮到聚類結果具有微小范圍內的隨機差異性，可以說明結點個數對整體圖結構的平均信息損失沒有影響.

Fig. 6 The comparison of the structural information loss in datasets DS1 and DS2.圖6 在DS1和DS2數據集上的結構信息損失比較

5 結束語

針對社交網絡圖數據的聚類匿名發布，考慮利用啟發式優化算法搜索最優解，本文提出一種圖聚類匿名遺傳算法.按照遺傳算法的流程框架，在依次描述了種群初始化算法、個體適應度值求解算法、賭輪法選擇算子、多點錯位的交叉算法和交換基因位的變異算子后，完整地給出了該GA-CAG算法.最后，多組實驗驗證了算法性能的優越性.當前，各類匿名保護方案以實現所有用戶等程度模糊為主，缺乏考慮用戶的個性化隱私保護需求.因此，下一步，我們將繼續就社交網絡的個性化隱私保護方案展開深入研究.

[1]Liu Peng, Li Xianxian. An improved privacy preserving algorithm for publishing social network data[C] //Proc of 2013 IEEE HPCC&EUC. Los Alamitos, CA: IEEE Computer Sociaty, 2013: 888-895

[2]Peng Wei, Li Feng, Zou Xukai, et al. A two-stage deanonymization attack against anonymized social networks[J]. IEEE Trans on Computers, 2014, 63(2): 290-302

[3]Zhou Bin, Pei Jian. Thek-anonymity andl-diversity approaches for privacy preservation in social networks against neighborhood attacks[J]. Knowledge and Information System, 2011, 28(1): 47-77

[4]Yuan Mingxuan, Chen Lei, Yu P S, et al. Protecting sensitive labels in social network data anonymization[J]. IEEE Trans on Knowledge and Data Engineering, 2013, 23(3): 633-647

[5]Gong N Z, Talwalkar A, Mackey L, et al. Jointly predicting links and inferring attributes using a social-attribute network (san)[C] //Proc of the 6th SNA-KDD. New York: ACM, 2012

[6]Liu Xiangyu, Wang Bin, Yang Xiaochun. Survey on privacy preserving techniques for publishing social network data[J]. Journal of Software, 2014, 25(3): 576-590 (in Chinese)(劉向宇, 王斌, 楊曉春. 社交網絡數據發布隱私保護技術綜述[J]. 軟件學報, 2014, 25(3): 576-590)

[7]Guo Longfei. A study on the dynamic influence and behavior regularities of user’ privacy concern about social network[D]. Beijing: Beijing University of Posts and Telecommunications, 2013 (in Chinese)(郭龍飛. 社交網絡用戶隱私關注動態影響因素及行為規律研究[D]. 北京: 北京郵電大學, 2013)

[8]Fu Yanyan, Fu Hao, Xie Xing, et al. Anonymity and privacy-protecting for social network[J]. The Communications of the China Computer Federation, 2014, 10(6): 51-58 (in Chinese)(付艷艷, 付浩, 謝幸, 等. 社交網絡匿名與隱私保護[J]. 中國計算機學會通訊, 2014, 10(6): 51-58)

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

[10]Cheng J, Fu A W, Liu J. K-isomorphism: Privacy preserving network publication against structural attacks[C] //Proc of the ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2010: 459-470

[11]Zheleva E, Getoor L. Preserving the privacy of sensitive relationships in graph data[G] //Privacy, Security, and Trust in KDD. Berlin: Springer, 2008: 153-171

[12]Campan A, Truta T M. Data and structuralk-anonymity in social networks[G] //Privacy, Security, and Trust in KDD. Berlin: Springer, 2009: 33-54

[13]Wang Rong, Zhang Min, Feng Dengguo, et al. A clustering approach for privacy-preserving in social networks[C] //Proc of ISC’14. Berlin: Springer, 2014: 193-204

[14]Skarkala M E, Maragoudakis M, Gritzalis S, et al. Privacy preservation byk-anonymization of weighted social networks[C] //Proc of IEEE Int Conf on Advances in Social Networks Analysis and Mining. Los Alamitos, CA: IEEE Computer Sociaty, 2012: 423-428

[15]Tassa T, Cohen D J. Anonymization of centralized and distributed social networks by sequential clustering[J]. IEEE Trans on Knowledge and Data Engineering. 2013, 25(2): 311-324

[16]Yang Bin, Sato I, Nakagawa H. Privacy-preserving EM algorithm for clustering on social network[C] //Advances in Knowledge Discovery and Data Mining. Berlin: Springer, 2012: 542-553

[17]Han Qilong, Zhou Hongbin, Pan Haiwei, et al. Research on spatio-temporal object graph clustering algorithm based on structure and attribute[J]. Journal of Computer Research and Development. 2013, 50(增刊): 154-162 (in Chinese)(韓啟龍, 趙洪斌, 潘海為, 等. 基于結構-屬性的時空對象圖聚類算法的研究[J].計算機研究與發展, 2013, 50(Suppl): 154-162)

Jiang Huowen, born in 1974. PhD candidate. Associate professor. Student Member of China Computer Federation. His main research interests include privacy preservation and software evolution.

Zeng Guosun, born in 1964. Professor and PhD supervisor. Senior Member of China Computer Federation. His main research interests include parallel computing, trusted software and information security.

Hu Kekun, born in 1987. PhD candidate. His main research interests include parallel computing and graph big-data processing (5hkk@tongji.edu.cn).

A Graph-Clustering Anonymity Method Implemented by Genetic Algorithm for Privacy-Preserving

Jiang Huowen1,2,3, Zeng Guosun1,3, and Hu Kekun1,3

1(DepartmentofComputerScienceandTechnology,TongjiUniversity,Shanghai200092)2(CollegeofMathematics&ComputerScience,JiangxiScience&TechnologyNormalUniversity,Nanchang330038)3(KeyLaboratoryofEmbeddedSystemandServiceComputing(TongjiUniversity),MinistryofEducation,Shanghai200092)

Clustering anonymity is a typical kind of privacy preservation scheme for social network data-publishing, which is based on graph-clustering. Graph-clustering is a kind of NP-hard combinatorial optimization problem and it’s appropriate to use search optimization algorithm. While, the existing graph-clustering anonymity methods are lack of heuristic search algorithm. Therefore, in this paper, a graph-clustering anonymity method implemented by genetic algorithm is proposed. Firstly, the population is initialized by pre-dividing the nodes based on greedy clustering strategy. Then the individual fitness function is defined based on the relation fitting theory. Next, the crossover operator of multi-point dislocation and the mutation operator of exchanging gene-bits are designed respectively, according to individual’s coding feature. The model we presented takes the information of both structure and attribute of nodes into consideration, and the global searching of genetic algorithm can guarantee good quality for graph-clustering. Therefore, the method can provide great privacy preservation. Experimental results also demonstrate that our method is effective in improving the clustering quality and reducing the loss of information.

social network; graph-clustering; privacy preservation;k-anonymity; genetic algorithm

2016-06-16；

2016-08-12

國家自然科學基金項目(61272107,71561013)；華為創新研究計劃項目(IRP-2013-12-03)；高效能服務器和存儲技術國家重點實驗室開放基金項目(2014HSSA10)

曾國蓀(gszeng@tongji.edu.cn)

TP309

This work was supported by the National Natural Science Foundation of China (61272107,71561013), the Huawei Innovation Research Program (IRP-2013-12-03), and the Project Funded by the State Key Laboratory of High-End Server & Storage Technology (2014HSSA10).