K-對(duì)稱(chēng)-N算法的社交網(wǎng)絡(luò)的隱私保護(hù)

◆高 潔 肖基毅 向 霞

（南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 湖南 421001）

K-對(duì)稱(chēng)-N算法的社交網(wǎng)絡(luò)的隱私保護(hù)

◆高 潔 肖基毅 向 霞

（南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 湖南 421001）

針對(duì)k匿名算法在對(duì)抗結(jié)構(gòu)攻擊的不足，采用k-對(duì)稱(chēng)匿名算法對(duì)社會(huì)網(wǎng)絡(luò)的隱私進(jìn)行保護(hù)。本文對(duì)k-對(duì)稱(chēng)匿名算法進(jìn)行可行性分析，并對(duì)其還原算法進(jìn)行描述。雖然社會(huì)網(wǎng)絡(luò)的隱私保護(hù)取得了大量的研究成果，社區(qū)結(jié)構(gòu)的隱私保護(hù)也取得了很多成功，但是其成果都是彼此相對(duì)獨(dú)立的，鮮有將二者兼顧。本文設(shè)計(jì)出一種k-對(duì)稱(chēng)-N匿名算法來(lái)解決此類(lèi)問(wèn)題。

k-對(duì)稱(chēng)匿名; 社區(qū)結(jié)構(gòu); 隱私保護(hù)

0 前言

隨著社交網(wǎng)絡(luò)的普及以及數(shù)據(jù)挖掘的技術(shù)的成熟，人們的隱私保護(hù)問(wèn)題成為了近些年來(lái)的研究熱點(diǎn)。人們?cè)谄谕畔⒐蚕淼耐瑫r(shí)又畏懼著信息共享[1]。太多的信息泄漏事件使得人們不敢將信息放在社交網(wǎng)絡(luò)上進(jìn)行交流，這就給數(shù)據(jù)挖掘等相關(guān)科研或者企業(yè)帶來(lái)了一定的困難。一般的社區(qū)網(wǎng)絡(luò)數(shù)據(jù)發(fā)布要在發(fā)布之前對(duì)數(shù)據(jù)進(jìn)行一定的處理才把數(shù)據(jù)發(fā)布到網(wǎng)絡(luò)中。一般采用泛化與隱匿技術(shù)來(lái)進(jìn)行數(shù)據(jù)的預(yù)處理。一般采用簡(jiǎn)單匿名的方式，但是簡(jiǎn)單匿名采用自底往上的匿名方式，會(huì)使得匿名后的數(shù)據(jù)可能世界空間加大，無(wú)法保持?jǐn)?shù)據(jù)的可用性。本文采用不確定性泛化策略來(lái)克服這種困難。隱私保護(hù)技術(shù)現(xiàn)階段有很多模型被廣泛應(yīng)用。其中為k-匿名模型、l-多樣性算法、以及個(gè)性化（a，k）-匿名三種最為廣泛應(yīng)用[3]。其中k匿名算法的應(yīng)用最非常廣泛，但是其存在多種不足[4]，本文在其基礎(chǔ)上，針對(duì)其針對(duì)社會(huì)網(wǎng)絡(luò)圖中的不足之處提出的改進(jìn)k-對(duì)稱(chēng)匿名算法運(yùn)用到社區(qū)網(wǎng)絡(luò)之中。社區(qū)網(wǎng)絡(luò)是社交網(wǎng)絡(luò)中一個(gè)經(jīng)典的問(wèn)題。社區(qū)網(wǎng)絡(luò)的發(fā)現(xiàn)算法包括KL算法、分割算法、譜分割算法、多級(jí)別圖圖分割算法、基于馬爾科夫聚類(lèi)的算法、局部圖聚類(lèi)算法等。本文基于分割算法對(duì)社交網(wǎng)絡(luò)進(jìn)行社區(qū)劃分。然后結(jié)合k-對(duì)稱(chēng)匿名算法提出了k-對(duì)稱(chēng)N匿名算法。

1 k-對(duì)稱(chēng)-社區(qū)匿名算法的實(shí)現(xiàn)過(guò)程

k-對(duì)稱(chēng)-社區(qū)匿名算法（K-symmetry-community anonymity algorithm）是一種在基于社區(qū)網(wǎng)絡(luò)劃分的前提下的關(guān)于結(jié)構(gòu)圖的k匿名算法。其流程圖如圖1下面將對(duì)算法進(jìn)行詳情介紹。

2 數(shù)據(jù)的預(yù)處理

傳統(tǒng)的社區(qū)擾亂技術(shù)通常在于擾亂社區(qū)內(nèi)朋友之間的邊得關(guān)系，并不注重社區(qū)結(jié)構(gòu)的保持。我們采用一種特殊的社區(qū)擾亂技術(shù)。在進(jìn)行社區(qū)劃分之前對(duì)數(shù)據(jù)進(jìn)行簡(jiǎn)單處理。

（1）迭代查詢(xún)節(jié)點(diǎn)H的社會(huì)網(wǎng)絡(luò)圖。H1（節(jié)點(diǎn)）、H2（節(jié)點(diǎn)的度）、H3（節(jié)點(diǎn)的鄰接節(jié)點(diǎn)的度集合）。

（2）If Hx3==Hy3交換節(jié)點(diǎn)Hx、Hy

它使得攻擊者事先插入的節(jié)點(diǎn)改變了位置，導(dǎo)致攻擊錯(cuò)誤的攻擊到其不感興趣的社區(qū)導(dǎo)致攻擊失敗。

3 社區(qū)劃分算法

社區(qū)發(fā)現(xiàn)技術(shù)是本算法研究中核心部分。本算法采用邊分割算法，其依據(jù)是社區(qū)間邊的權(quán)值betweenness大于社區(qū)內(nèi)邊的權(quán)值。通過(guò)刪除較大權(quán)值的邊來(lái)進(jìn)行社區(qū)分割。循環(huán)分割直到社區(qū)數(shù)目達(dá)到預(yù)期的數(shù)目為止。

4 社區(qū)聚類(lèi)

數(shù)據(jù)挖掘中聚類(lèi)一般分為三種:基于劃分的方法、基于層次的方法、基于密度的方法三種。

本文采用第三種基于密度的聚類(lèi)方式對(duì)社區(qū)進(jìn)行聚類(lèi)。DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一個(gè)比較有代表性的基于密度的聚類(lèi)算法。能夠把具有足夠高密度的區(qū)域劃分為簇，并能發(fā)現(xiàn)任意形狀的聚類(lèi)。

圖1 k-對(duì)稱(chēng)-N社區(qū)隱私保護(hù)算法流程圖

社區(qū)聚類(lèi)的目地是將相似度大于一定閥值的社區(qū)進(jìn)行聚集，使得一個(gè)簇內(nèi)含有N個(gè)社區(qū)。這與k匿名算法的思想相同，將每個(gè)社區(qū)隱藏在與其相似的其余N-1個(gè)社區(qū)中。并用NMI對(duì)社區(qū)劃分準(zhǔn)確度進(jìn)行測(cè)量。

5 虛擬社區(qū)的產(chǎn)生

對(duì)于一個(gè)簇內(nèi)不滿(mǎn)N個(gè)的社區(qū)采取虛擬社區(qū)產(chǎn)生的方式，使其滿(mǎn)足一個(gè)簇內(nèi)至少有N個(gè)社區(qū)。

傳統(tǒng)的算法虛擬社區(qū)的產(chǎn)生與邊的數(shù)目都是隨機(jī)的，這種形式下的虛擬社區(qū)與本來(lái)存在的社區(qū)的差別很大。為了更好的使得社區(qū)的產(chǎn)生更加真實(shí)化，本文對(duì)每個(gè)簇內(nèi)節(jié)點(diǎn)期望值與邊的期望值作為最初的虛擬社區(qū)的節(jié)點(diǎn)數(shù)目與邊的條數(shù)，并在簇內(nèi)隨機(jī)挑選本簇內(nèi)的節(jié)點(diǎn)作為虛擬社區(qū)的節(jié)點(diǎn)，并隨機(jī)生成期望值條邊。形成初始的社區(qū)。根據(jù)公式（1）求此簇內(nèi)與其他社區(qū)內(nèi)相似度最大的社區(qū)。并計(jì)算虛擬社區(qū)與此社區(qū)之間的相似度。

設(shè)A1=(M1,N1),A2=(M2,N2)是社區(qū)網(wǎng)絡(luò)A=(M.N)的非空社區(qū)。Ni1=Ni(兩個(gè)社區(qū)中的邊),Ni2={nxy=(mx,my)∈N|mx∈M1,my∈M2},(兩個(gè)社區(qū)連接邊)，Ni3={nx,y=(mx,my) ∈N|mx∈Mi,my∈M-N1-M2}(社區(qū)空間中非這兩個(gè)社區(qū)與兩社區(qū)的連接邊)，其中1,2,j=1,2,3,設(shè)集合Q，則A1和A2的相似度S(A1,A2)定義為：

其中?為加權(quán)印子 (0≤?≤1),其中 ?用于確定節(jié)點(diǎn)相似度(邊相似度)占社區(qū)相似度所占的比重。std(Q)和分別為實(shí)數(shù)集合Q中的均值和標(biāo)準(zhǔn)差。e-|M1|,f=|M2|,rx∈M1,ty∈M2。

這種方法即考慮了節(jié)點(diǎn)的相似度，也考慮了邊的相似度。

若虛擬社區(qū)與相似度最大社區(qū)之間的相似度小于閥值時(shí)，求虛擬社區(qū)對(duì)相似度最大社區(qū)的等異度子集，并將其按度的降序排列的同時(shí)將相似度最大的社區(qū)度按降序排列，然后將虛擬社區(qū)等異度子集度的一半數(shù)目的節(jié)點(diǎn)用最大社區(qū)降序前相同數(shù)目的節(jié)點(diǎn)替換。將虛擬社區(qū)交換后的節(jié)點(diǎn)相連的邊刪除。并在社區(qū)內(nèi)隨機(jī)產(chǎn)生相同數(shù)目的邊（邊的數(shù)目不變?cè)瓌t）。重新計(jì)算虛擬社區(qū)與相似度最大社區(qū)的相似度，小于閥值繼續(xù)上述步驟。大于閥值則結(jié)束。

6 社區(qū)內(nèi)部?jī)?yōu)化k-對(duì)稱(chēng)算法

由于社區(qū)的聚類(lèi)使得每個(gè)節(jié)點(diǎn)至少隱藏在N個(gè)社區(qū)之內(nèi)，但是對(duì)于這種隱藏方式與k匿名一樣對(duì)預(yù)防鏈接攻擊有很好的療效。但一個(gè)簇內(nèi)的社區(qū)很大程度上是敏感同質(zhì)的，對(duì)于社區(qū)內(nèi)的節(jié)點(diǎn)有時(shí)保護(hù)度不夠，我們對(duì)于社區(qū)內(nèi)部再次使用k-對(duì)稱(chēng)匿名算法。是其應(yīng)對(duì)對(duì)于社區(qū)內(nèi)部的結(jié)構(gòu)攻擊。

K-對(duì)稱(chēng)匿名算法是k匿名的算法在圖論中應(yīng)用的一種變種。其將圖論中的圖對(duì)稱(chēng)理論運(yùn)用到k-匿名算法中。簡(jiǎn)單講是對(duì)社區(qū)的節(jié)點(diǎn)進(jìn)行對(duì)稱(chēng)處理后再進(jìn)行k-匿名。本文由于篇幅問(wèn)題紙描述一個(gè)社區(qū)的k-對(duì)稱(chēng)匿名過(guò)程。

其步驟如下:

對(duì)圖中的節(jié)點(diǎn)做出社會(huì)網(wǎng)路關(guān)系矩陣，本文中因?yàn)槭菬o(wú)向圖，矩陣是對(duì)稱(chēng)矩陣。

找出圖中自首等價(jià)數(shù)目最少的節(jié)點(diǎn)，對(duì)其進(jìn)行對(duì)稱(chēng)處理。判斷每個(gè)節(jié)點(diǎn)是否至少有k個(gè)自守等價(jià)的節(jié)點(diǎn)，不滿(mǎn)足重復(fù)步驟2。滿(mǎn)足則結(jié)束。

其是k-匿名算法在圖結(jié)構(gòu)的變種，是可行的。相對(duì)于傳統(tǒng)的將每個(gè)節(jié)點(diǎn)都做對(duì)稱(chēng)處理節(jié)點(diǎn)和邊都減少很多。復(fù)雜度降低。

其還原算法，將最后相同的等價(jià)類(lèi)只留一個(gè)，這種還原方法雖然無(wú)法百分之百還原原始數(shù)據(jù)，但在一定程度上還是可取的。

7 實(shí)驗(yàn)及分析

將k-對(duì)稱(chēng)N社區(qū)發(fā)現(xiàn)算法在不同的k值下的信息損失與經(jīng)典的p-Sensitive k-匿名算法進(jìn)行比較。已判斷其數(shù)據(jù)的真實(shí)性。

K-對(duì)稱(chēng)-N匿名算法與經(jīng)典p-Sensitive k-匿名算法信息損失對(duì)比如圖2。

由實(shí)驗(yàn)可知k-對(duì)稱(chēng)-N算法比p-Sensitive k-匿名算法數(shù)據(jù)損失小，證明了其有效性。

其數(shù)據(jù)隱私保護(hù)度相對(duì)與傳統(tǒng)的k匿名算法又增加了N社區(qū)匿名。大大提高了隱私的保護(hù)度。