基于信息損失量估計(jì)的匿名圖構(gòu)造方法

蘇潔，劉帥，羅智勇，孫廣路

?

基于信息損失量估計(jì)的匿名圖構(gòu)造方法

蘇潔，劉帥，羅智勇，孫廣路

（哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱150080）

首先分析了在進(jìn)化的社會(huì)網(wǎng)絡(luò)序列中，攻擊者利用節(jié)點(diǎn)度信息，通過(guò)識(shí)別目標(biāo)節(jié)點(diǎn)的方法對(duì)局部社會(huì)網(wǎng)絡(luò)進(jìn)行攻擊過(guò)程，分析了利用匿名方法對(duì)該類攻擊進(jìn)行隱私保護(hù)時(shí)存在的信息損失問(wèn)題，針對(duì)該問(wèn)題，提出了一種基于信息損失量估計(jì)的匿名圖流構(gòu)造方法，通過(guò)子圖節(jié)點(diǎn)屬性泛化、子圖內(nèi)部結(jié)構(gòu)的泛化控制圖重構(gòu)的信息損失，通過(guò)禁止子圖內(nèi)部擾動(dòng)阻止網(wǎng)絡(luò)攻擊。定義匿名過(guò)程中由于圖重構(gòu)造成的節(jié)點(diǎn)和結(jié)構(gòu)信息損失的估算方法，建立了基于貪婪聚類算法的網(wǎng)絡(luò)節(jié)點(diǎn)的匿名聚類算法，根據(jù)信息損失估計(jì)實(shí)現(xiàn)匿名分組，在進(jìn)化的社會(huì)網(wǎng)絡(luò)中以最小信息損失量構(gòu)造匿名社會(huì)網(wǎng)絡(luò)，在醫(yī)療診斷數(shù)據(jù)集上的實(shí)驗(yàn)表明所提方法能夠較理想地控制信息損失量。

社會(huì)網(wǎng)絡(luò)；隱私保護(hù)；匿名；信息損失估計(jì)

1 引言

隨著社會(huì)網(wǎng)絡(luò)分析方法在各個(gè)社會(huì)研究領(lǐng)域中的廣泛應(yīng)用，越來(lái)越多的研究人員開(kāi)始關(guān)注社會(huì)網(wǎng)絡(luò)相關(guān)問(wèn)題[1]，其中，社會(huì)網(wǎng)絡(luò)的隱私保護(hù)成為該研究領(lǐng)域的關(guān)鍵問(wèn)題之一。發(fā)布社會(huì)網(wǎng)絡(luò)時(shí)，需要保護(hù)私人的敏感信息和社會(huì)關(guān)系，而社會(huì)網(wǎng)絡(luò)的攻擊方試圖通過(guò)數(shù)據(jù)挖掘等技術(shù)發(fā)現(xiàn)社會(huì)網(wǎng)絡(luò)中的敏感信息。社會(huì)網(wǎng)絡(luò)通常以圖的形式發(fā)布，網(wǎng)絡(luò)中的節(jié)點(diǎn)表示個(gè)體，邊表示個(gè)體間的關(guān)系。在社會(huì)網(wǎng)絡(luò)圖中，每個(gè)節(jié)點(diǎn)由實(shí)體—屬性集合描述，有唯一的標(biāo)識(shí)符，由于對(duì)社會(huì)網(wǎng)絡(luò)的研究可以利用圖工具實(shí)現(xiàn)，越來(lái)越多的研究人員通過(guò)研究圖匿名方法來(lái)解決隱私保護(hù)問(wèn)題。文獻(xiàn)[2]將匿名方法進(jìn)行了分類，分析了圖的匿名方法，指出由于動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)需要定期發(fā)布網(wǎng)絡(luò)數(shù)據(jù)來(lái)支持動(dòng)態(tài)分析，因此會(huì)造成信息的泄露。文獻(xiàn)[3, 4]提出了基于群和分類的匿名圖，文獻(xiàn)[5]提出了一種社會(huì)網(wǎng)絡(luò)中數(shù)據(jù)和結(jié)構(gòu)化匿名的聚類方法，文獻(xiàn)[6]介紹了在圖中怎樣保護(hù)敏感關(guān)系，文獻(xiàn)[7]提出一種基于差分隱私模型的隨機(jī)擾動(dòng)方法，實(shí)現(xiàn)邊及邊權(quán)重的強(qiáng)保護(hù)，文獻(xiàn)[8]驗(yàn)證了匿名圖中節(jié)點(diǎn)的再識(shí)別問(wèn)題，文獻(xiàn)[9]提出了通過(guò)發(fā)布和分析合成圖的方法來(lái)保護(hù)社會(huì)網(wǎng)絡(luò)中的個(gè)人社會(huì)關(guān)系，文獻(xiàn)[10]提出一種在共享有意義的圖形數(shù)據(jù)集的同時(shí)保護(hù)個(gè)人隱私的解決方案，文獻(xiàn)[11, 12]研究了進(jìn)化社會(huì)網(wǎng)絡(luò)中的匿名圖問(wèn)題。然而，隱私保護(hù)技術(shù)仍然處于研究的初級(jí)階段，網(wǎng)絡(luò)的攻擊方仍然能夠在發(fā)布的匿名圖中根據(jù)背景知識(shí)找到社會(huì)網(wǎng)絡(luò)中感興趣的個(gè)體和相關(guān)信息，文獻(xiàn)[13, 14]證明現(xiàn)有的圖匿名方法并未取得匿名方法的理想結(jié)果。

現(xiàn)有的圖的匿名方法分為3類：1）基于匿名的方法，通過(guò)調(diào)整圖的結(jié)構(gòu)保護(hù)敏感信息[15, 16]，采用匿名方法，網(wǎng)絡(luò)節(jié)點(diǎn)無(wú)法識(shí)別子圖內(nèi)的?1個(gè)節(jié)點(diǎn)；2）基于概率的方法，通過(guò)隨機(jī)添加/刪除邊或切換邊的方法保護(hù)敏感信息[17]；3）基于泛化的方法，通過(guò)隱藏個(gè)人細(xì)節(jié)信息的隱私保護(hù)方法[4,5]。在社會(huì)網(wǎng)絡(luò)發(fā)布過(guò)程中，通過(guò)更換節(jié)點(diǎn)的識(shí)別信息或者通過(guò)增加/刪減邊來(lái)改變結(jié)構(gòu)信息，實(shí)現(xiàn)社會(huì)網(wǎng)絡(luò)隱私保護(hù)。由于存在大量可獲取的歷史發(fā)布數(shù)據(jù)和節(jié)點(diǎn)度信息，社會(huì)網(wǎng)絡(luò)攻擊者會(huì)在某一時(shí)刻插入一個(gè)目標(biāo)節(jié)點(diǎn)，在發(fā)布網(wǎng)絡(luò)序列中利用背景信息識(shí)別該目標(biāo)節(jié)點(diǎn)，實(shí)現(xiàn)網(wǎng)絡(luò)攻擊。針對(duì)該類攻擊的匿名方法包括：1）采用節(jié)點(diǎn)度泛化的匿名方法，針對(duì)攻擊者利用指定個(gè)體社會(huì)關(guān)系的先驗(yàn)知識(shí)對(duì)網(wǎng)絡(luò)進(jìn)行的攻擊，通過(guò)插入或刪除邊的方法實(shí)現(xiàn)基于度匿名圖的重構(gòu)，使每個(gè)節(jié)點(diǎn)至少與?1個(gè)節(jié)點(diǎn)有相同的度；2）采用鄰域匿名方法，利用貪婪圖調(diào)整算法生成節(jié)點(diǎn)標(biāo)簽，插入邊，使每個(gè)鄰接節(jié)點(diǎn)能夠區(qū)分?1個(gè)節(jié)點(diǎn)，該方法避免了攻擊者根據(jù)已知目標(biāo)節(jié)點(diǎn)的鄰接子圖進(jìn)行的網(wǎng)絡(luò)攻擊；3）利用子圖同構(gòu)的匿名方法，重構(gòu)圖至少包含個(gè)子圖的同構(gòu)子圖，避免攻擊者通過(guò)識(shí)別指定個(gè)體的任意子圖進(jìn)行的網(wǎng)絡(luò)攻擊。利用此類方法保護(hù)社會(huì)網(wǎng)絡(luò)需要重構(gòu)社會(huì)網(wǎng)絡(luò)圖，在此過(guò)程中產(chǎn)生的信息損失既包括節(jié)點(diǎn)屬性信息損失，又包括結(jié)構(gòu)信息損失。

在分析匿名方法的基礎(chǔ)上，針對(duì)社會(huì)網(wǎng)絡(luò)發(fā)布過(guò)程中潛在的安全問(wèn)題及匿名過(guò)程中的信息損失問(wèn)題，本文利用匿名圖工具，提出了在進(jìn)化的社會(huì)網(wǎng)絡(luò)中通過(guò)信息損失估計(jì)的方法，利用邊的泛化構(gòu)造匿名圖。本文創(chuàng)新之處如下。

1) 在社會(huì)網(wǎng)絡(luò)發(fā)布過(guò)程中，利用信息損失估計(jì)方法構(gòu)建匿名子圖，在節(jié)點(diǎn)信息損失、結(jié)構(gòu)信息損失和社會(huì)網(wǎng)絡(luò)安全級(jí)別方面取得折衷的最優(yōu)值。

2) 利用節(jié)點(diǎn)信息、子圖結(jié)構(gòu)信息泛化構(gòu)建的匿名子圖，避免了擾動(dòng)攻擊對(duì)網(wǎng)絡(luò)安全的威脅。

3) 在發(fā)布的社會(huì)網(wǎng)絡(luò)中，通過(guò)判斷網(wǎng)絡(luò)結(jié)構(gòu)圖的變化選擇構(gòu)建子圖方法，提出以極小的信息損失代價(jià)平衡網(wǎng)絡(luò)子圖構(gòu)建的時(shí)間復(fù)雜性的方法，最大程度保證動(dòng)態(tài)網(wǎng)絡(luò)的穩(wěn)定性。

2 基于節(jié)點(diǎn)度的社會(huì)網(wǎng)絡(luò)攻擊

上述分析表明，利用邊擾動(dòng)的方法實(shí)現(xiàn)動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)匿名，攻擊者可以利用收集到的節(jié)點(diǎn)信息實(shí)現(xiàn)局部網(wǎng)絡(luò)攻擊。雖然Facebook、Twitter等社會(huì)網(wǎng)絡(luò)已經(jīng)限定網(wǎng)絡(luò)用戶的訪問(wèn)范圍，但是基于應(yīng)用的需要，攻擊者仍然能夠利用上述方法攻擊局部開(kāi)放網(wǎng)絡(luò)。

采用鄰域匿名方法能夠有效控制攻擊者利用已知目標(biāo)節(jié)點(diǎn)的鄰接子圖信息進(jìn)行的網(wǎng)絡(luò)攻擊，但是構(gòu)建匿名圖的過(guò)程中會(huì)有大量信息損失，3.1節(jié)中給出了利用貪婪圖調(diào)整算法生成節(jié)點(diǎn)標(biāo)簽，通過(guò)構(gòu)建信息損失量估計(jì)算法，預(yù)估計(jì)構(gòu)建匿名子圖的損失量，實(shí)現(xiàn)最小信息損失匿名圖構(gòu)造。

3 構(gòu)建社會(huì)網(wǎng)絡(luò)的匿名子圖

3.1 基于泛化的匿名

匿名是隱私保護(hù)的經(jīng)典方法，每個(gè)數(shù)據(jù)組至少包含個(gè)無(wú)法區(qū)分的節(jié)點(diǎn)。傳統(tǒng)方法通過(guò)插入或刪除邊的擾動(dòng)方法保護(hù)節(jié)點(diǎn)不被識(shí)別，該匿名方法構(gòu)造過(guò)程中會(huì)造成信息損失，影響數(shù)據(jù)的可信性。基于屬性泛化的方法能夠降低對(duì)原圖結(jié)構(gòu)的破壞，降低信息損失。

為了構(gòu)建匿名子圖，既要對(duì)節(jié)點(diǎn)信息泛化，也要對(duì)子圖內(nèi)部結(jié)構(gòu)和子圖間的聯(lián)系泛化。表示子圖之間的關(guān)系的邊顯示了網(wǎng)絡(luò)的結(jié)構(gòu)特征，以實(shí)現(xiàn)某些應(yīng)用。匿名網(wǎng)絡(luò)結(jié)構(gòu)中，子圖內(nèi)部不允許使用擾動(dòng)方法，有效防止了基于節(jié)點(diǎn)度的攻擊。利用節(jié)點(diǎn)信息、子圖內(nèi)部關(guān)系和子圖間的關(guān)系，通過(guò)估計(jì)信息損失，構(gòu)造匿名圖。

1) 每個(gè)分組至少包含個(gè)節(jié)點(diǎn)；

2) 估計(jì)聚類的信息損失，降低匿名過(guò)程的信息損失量。

因此，需要定義一種信息損失的估算方法。

3.2 基于信息損失估計(jì)的匿名圖重構(gòu)方法

基于信息損失估計(jì)的匿名圖重構(gòu)方法將具有相似屬性且具有最小信息損失的個(gè)節(jié)點(diǎn)聚為一個(gè)集合，聚類分組過(guò)程中，用于損失估計(jì)的信息包括圖重構(gòu)信息和節(jié)點(diǎn)與分組的結(jié)構(gòu)信息。

(2)

其中，節(jié)點(diǎn)間的距離、節(jié)點(diǎn)與聚類集合間的距離取值為[0, 1]。

在圖中選擇度最大的節(jié)點(diǎn)作為聚類集合的中心節(jié)點(diǎn)，選擇?1個(gè)與當(dāng)前聚類集合有最小距離但未分配的節(jié)點(diǎn)來(lái)構(gòu)造新的聚類集合。節(jié)點(diǎn)間的距離和結(jié)構(gòu)距離分別表示為和。

根據(jù)節(jié)點(diǎn)屬性計(jì)算聚類分組過(guò)程的信息損失包括泛化信息損失和結(jié)構(gòu)信息損失[14]。泛化信息損失用于計(jì)算節(jié)點(diǎn)描述性信息的損失[20]，定義泛化信息損失為

(4)

(6)

(7)

算法1 基于信息損失估計(jì)的匿名聚類算法

輸入 圖；

參數(shù)、參數(shù)和參數(shù)；

1)=||=0; // 聚類分組數(shù)

2)=||; //初始值

//遍歷節(jié)點(diǎn)找出最大度節(jié)點(diǎn)作為聚類的種子節(jié)點(diǎn)

4) Seed= v,v有當(dāng)前最大度d;

5)s={ v}; //v加入到分組中

6)=?v;

7) while(|s|<)

12) return;

13) end if

14) end while

15) if(|s|<)

18) else

20)=+1;

21) end if

22) end while

社會(huì)網(wǎng)絡(luò)在進(jìn)化過(guò)程中，會(huì)有新用戶加入，或者舊用戶退出，在網(wǎng)絡(luò)圖中表現(xiàn)為插入新的節(jié)點(diǎn)和邊或者刪除某些節(jié)點(diǎn)和邊，由此造成的社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)的變化定期更新發(fā)布。更新時(shí)間間隔表示為，圖流序列表示為0,1,…,G，時(shí)刻的圖結(jié)構(gòu)變化定義為如式（8）所示。

圖G中節(jié)點(diǎn)及邊的結(jié)構(gòu)變化定義如式（9）和式（10）所示。

(9)

(11)

3.3 匿名子圖信息損失評(píng)價(jià)

利用基于信息損失估計(jì)的匿名聚類算法將社會(huì)網(wǎng)絡(luò)圖劃分成分組集合，結(jié)構(gòu)信息損失由類內(nèi)結(jié)構(gòu)損失和類間結(jié)構(gòu)損失2部分組成[21]，定義如(12)所示。

(13)

(15)

3.4 基于圖的變化率的圖流聚類算法

對(duì)于初始的社會(huì)網(wǎng)絡(luò)，采用聚類算法得到分組后，聚類分組對(duì)應(yīng)的節(jié)點(diǎn)核記為，，是類內(nèi)生成對(duì)，，。匿名社會(huì)網(wǎng)定義為

算法2 基于圖的變化率的圖流聚類算法

輸入G?1,G；

7) end for

11) if(|s|<)

14) end if

15) end for

16) end if

17) end if

18) else

19) 網(wǎng)絡(luò)結(jié)構(gòu)變化明顯，對(duì)整體網(wǎng)絡(luò)匿名分組

20) end else

在社會(huì)網(wǎng)絡(luò)更新過(guò)程中，采用基于圖的變化率的圖流聚類算法，計(jì)算圖流的結(jié)構(gòu)變化，通過(guò)估算最小信息損失量方法實(shí)現(xiàn)匿名聚類。

4 仿真實(shí)驗(yàn)

表1提供了用于急性髓細(xì)胞白血病診斷的病歷數(shù)據(jù)。0時(shí)刻圖0的節(jié)點(diǎn)集合為。病患資料的個(gè)人信息中，SSN和駕駛證等已經(jīng)被隱藏，表中給出了年齡、性別、郵政編碼、婚姻狀況等近似標(biāo)識(shí)符。為了保護(hù)病人的隱私，采用本文匿名方法，屬性集定義為，，，={Gender, Zip code, Marriage}。

表1 診斷的病歷數(shù)據(jù)

圖2為根據(jù)診斷數(shù)據(jù)和社會(huì)關(guān)系構(gòu)建的社會(huì)網(wǎng)絡(luò)，0時(shí)刻的網(wǎng)絡(luò)表示為圖0，1時(shí)刻的網(wǎng)絡(luò)表示為圖1，層次結(jié)構(gòu)屬性1、2、3，如圖3所示。表2給出了取3、6，分別取0、0.6、1時(shí)的聚類分組結(jié)果。

表2 基于信息損失估計(jì)的聚類分組

圖4給出了取2~10，取0~1時(shí)節(jié)點(diǎn)的泛化信息損失和結(jié)構(gòu)信息損失情況。圖4數(shù)據(jù)表明，最終發(fā)布的匿名數(shù)據(jù)集中包含的匿名組數(shù)目越多，值越小，信息損失越少，匿名化的數(shù)據(jù)越接近真實(shí)數(shù)據(jù)，該數(shù)據(jù)集的可信任度越高。=1時(shí)的節(jié)點(diǎn)泛化信息損失高于=0時(shí)的泛化信息損失；=0時(shí)的結(jié)構(gòu)信息損失低于=1時(shí)的結(jié)構(gòu)信息損失。

在1時(shí)刻插入新的節(jié)點(diǎn)如圖2(b)所示。,1結(jié)構(gòu)變化率，，取=4，分別為0和1時(shí)，采用算法2聚類分組結(jié)果為A1，對(duì)1采用基于完全信息算是估計(jì)的聚類分組結(jié)果為A2，如表3所示，A1和A2的聚類分組信息損失如圖5所示。

聚類分組誤差定義為

(19)

該數(shù)據(jù)表明，最終發(fā)布的匿名數(shù)據(jù)集中包含的匿名組越多，該數(shù)據(jù)集包含的信息越豐富，且數(shù)據(jù)集的平均匿名組規(guī)模越小，信息損失越小，匿名化的數(shù)據(jù)越接近原來(lái)的真實(shí)數(shù)據(jù)，該數(shù)據(jù)集的可用性越高。

表3 基于聚類分組信息損失估計(jì)的聚類分組(k=4)

5 結(jié)束語(yǔ)

針對(duì)社會(huì)網(wǎng)絡(luò)發(fā)布過(guò)程中的安全問(wèn)題，本文分析了基于擾動(dòng)的攻擊過(guò)程及相應(yīng)的解決方法，建立了基于信息損失估計(jì)的匿名方法，通過(guò)子圖節(jié)點(diǎn)屬性信息泛化和子圖結(jié)構(gòu)信息泛化構(gòu)建子圖，在降低重構(gòu)圖的信息損失的同時(shí)，阻止擾動(dòng)攻擊。在社會(huì)網(wǎng)絡(luò)更新過(guò)程中，首先判斷網(wǎng)絡(luò)結(jié)構(gòu)變化，在網(wǎng)絡(luò)變化率較小的情況下，通過(guò)損失部分信息的方法平衡網(wǎng)絡(luò)計(jì)算時(shí)間復(fù)雜性，同時(shí)減少網(wǎng)絡(luò)結(jié)構(gòu)的破壞。后續(xù)研究工作中，將繼續(xù)研究在動(dòng)態(tài)的社會(huì)網(wǎng)絡(luò)中如何以最少的信息損失取得最優(yōu)的匿名級(jí)別問(wèn)題。

[1] 韓毅, 方濱興, 賈焰,等. 基于密度估計(jì)的社會(huì)網(wǎng)絡(luò)特征簇挖掘方法[J]. 通信學(xué)報(bào), 2012, 33(5):38-48.

HAN Y, FANG B X, JIA Y, et al. Mining characteristic clusters: a density estimation approach[J]. Journal on Communications, 2012, 33(5):38-48.

[2] WU X, YING X, LIU K. A survey of privacy-preservation of graphs and social networks[M]. Managing and mining graph data. Springer US, 2010: 421-453.

[3] CASAS-ROMA J, HERRERA-JOANCOMARTí J, TORRA V. Anonymizing graphs: measuring quality for clustering[J]. Knowledge & Information Systems, 2015, 44(3):1-22.

[4] BHAGAT S, CORMODE G, KRISHNAMURTHY B. Class based graph anaonymization for social network data[C]//35th International Conference on Very Large Data Base. c2009: 766-777.

[5] WANG R, ZHANG M, FENG D, et al. A clustering approach for privacy-preserving in social networks[C]//Information Security and Cryptology-ICISC 2014. Springer International Publishing, c2014: 193-204.

[6] JING Y, GOSSWEILER III R C. Using visualization techniques for adjustment of privacy settings in social networks[P]. US8832567. 2014.

[7] AGGARWAL C C, LI Y, YU P S. On the anonymizability of graphs[J]. Knowledge & Information Systems, 2015, 45(3):571-588.

[8] 蘭麗輝, 鞠時(shí)光. 基于差分隱私的權(quán)重社會(huì)網(wǎng)絡(luò)隱私保護(hù)[J]. 通信學(xué)報(bào), 2015, 36(9):145-159.

LAN L H, JU S G. Privacy preserving based on differential privacy for weighted social networks[J]. Journal on Communications, 2015, 36(9):145-159.

[9] KARWA V, SLAVKOVIC A B, KRIVITSKY P N. Differentially private exponential random graphs[C]//Privacy in Statistical Database-UNESCO Chair in Data Privacy, International Conference, PSD 2014. Ibiza, Spain, c2014: 143-155.

[10] SALA A, ZHAO X, WILSON C. Sharing graphs using differentially private graph models[C]//The 2011 ACM SIGCOMM Conference on Internet Measurement, ACM, c2011: 81-98.

[11] MEDFORTH N, WANG K. Privacy risk in graph stream publishing for social network data[C]//The 2011 IEEE 11th International Conference on Data Mining. c2011: 437-446.

[12] ROSSI L, MUSOLESI M, TORSELLO A. On the-anonymization of time-varying and multi-layer social graphs[J]. arXiv preprint arXiv: 1503. 06497, 2015.

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

[14] LIU C G, LIU I H, YAO W S, et al.-anonymity against neighborhood attacks in weighted social networks[J]. Security & Communication Networks, 2015, 18(8): 3864-3882.

[15] LIU K, TERZI E. Towards identity anonymization on graphs[C]//The 2008 ACM SIGMOD International Conference on Management of Data. ACM, c2008: 93-106.

[16] CHENG J, FU A W, LIU J.-isomorphism: privacy preserving network publication against structural attacks[C]//The 2010 ACM SIGMOD International Conference on Management of Data. ACM, c2010: 459-470.

[17] MICHEAL H, GEROME M, DAVID J. Resisting structural re-identification in anonymized social networks[J]. Proceedings of the VLDB Endowment, 2008, 1(1): 102-114.

[18] FUNG B C M, JIN Y, LI J, et al. Anonymizing social network data for maximal frequent-sharing pattern mining[M]//Recommendation and Search in Social Networks. Springer International Publishing, 2015:77-100.

[19] SWEENEY L.-anonymity: a model for protecting privacy[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2002, 10(05): 557-570.

[20] BYUN J W, KAMRA A, BERTINO E, et al. Efficient-anonymization using clustering techniques[C]//Dasfaa. Springer Berlin Heidelberg, c2007: 188-200.

[21] HAN J, KAMBER M. Data mining: comcepts and techniques[J]. San Francisco, 2006, 29(1): 1 - 25.

Method of constructing an anonymous graph based on information loss estimation

SU Jie, LIU Shuai, LUO Zhi-yong, SUN Guang-lu

（School of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China）

A potential attack based on degree information by re-identifying target vertexes from a sequence of published graphs was analyzed. To deal with this kind of attack, a-anonymous graph stream constructing method based on information loss estimation was provided. Information loss caused by re-constructing graph was controlled by using the method of attributes generalization of nodes and the structure generalization of sub-graph. The disturbance in sub-graph was forbidden to prevent the attack. The method of measuring the information loss of nodes and structures during the anonymous process due to re-construction of graph was defined. A-anonymity cluster algorithm based on greedy clustering algorithm was build, which realized anonymous partition according to the information loss. Finally, a method of constructing anonymous social network for the evolving social network with the least information loss was provided. The experiments on medical diagnostic data set show that the algorithm of constructing anonymous graph based on the information loss estimation can be used to control the loss of information.

social network, privacy protection,-anonymity, information loss estimation

TP309.2

A

10.11959/j.issn.1000-436x.2016116

2015-11-12；

2016-04-26

黑龍江省自然科學(xué)基金資助項(xiàng)目（No.A201301）；黑龍江省教育科學(xué)規(guī)劃課題基金資助項(xiàng)目(No.GBC1211062)；黑龍江省普通高等學(xué)校新世紀(jì)優(yōu)秀人才培養(yǎng)計(jì)劃基金資助項(xiàng)目(No.1155-ncet-008)；黑龍江省博士后基金資助項(xiàng)目（No.LBH-Z12082）

The Natural Science Foundation of Heilongjiang Province(No.A201301), Scientific Planning Issues of Education in Heilongjiang Province(No.GBC1211062), Research Fund for the Program of New Century Excellent Talents in Heilongjiang Provincial University (No.1155-ncet-008), Post Doctoral Fund of Heilongjiang Province(No.LBH-Z12082)

蘇潔（1979-），女，山東淄博人，哈爾濱理工大學(xué)副教授、碩士生導(dǎo)師，主要研究方向?yàn)橹悄苄畔⑻幚怼?/p>

劉帥（1988-），男，山東濟(jì)寧人，哈爾濱理工大學(xué)碩士生，主要研究方向?yàn)橹悄苄畔⑻幚怼?/p>

羅智勇（1978-），男，黑龍江大慶人，哈爾濱理工大學(xué)副教授、碩士生導(dǎo)師，主要研究方向?yàn)橹悄苄畔⑻幚怼?/p>

孫廣路（1979-），男，黑龍江哈爾濱人，哈爾濱理工大學(xué)教授、碩士生導(dǎo)師，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)與信息安全、機(jī)器學(xué)習(xí)。