面向社交網(wǎng)絡(luò)數(shù)據(jù)的等差數(shù)列聚類匿名算法

劉振鵬， 董姝慧， 李澤園， 張慶文， 劉嘉航， 李小菲

(1.河北大學(xué) 電子信息工程學(xué)院 河北 保定 071002； 2.河北大學(xué) 信息技術(shù)中心 河北 保定 071002)

0 引言

在社交網(wǎng)絡(luò)數(shù)據(jù)挖掘中，研究如何實(shí)現(xiàn)社交網(wǎng)絡(luò)[1]發(fā)布的原始數(shù)據(jù)集和數(shù)據(jù)集中用戶隱私之間的權(quán)衡[2]已成為大數(shù)據(jù)和網(wǎng)絡(luò)信息安全領(lǐng)域的熱點(diǎn)問(wèn)題。許多研究者已經(jīng)相繼對(duì)社交網(wǎng)絡(luò)數(shù)據(jù)發(fā)布的隱私保護(hù)作了研究，為了減少數(shù)據(jù)發(fā)布過(guò)程中敏感信息的泄露，須對(duì)發(fā)布的數(shù)據(jù)進(jìn)行處理[3]，一般主要采用匿名[4-7]和差分隱私保護(hù)技術(shù)[8-9]。很多研究采用的社交網(wǎng)絡(luò)隱私保護(hù)算法都融入了k-匿名的思想[10-13]。文獻(xiàn)[14] 提出了一種基于k-成員模糊聚類和螢火蟲(chóng)算法的聯(lián)合匿名算法，能有效抵御一些攻擊。但是基于迭代的元啟發(fā)式算法的實(shí)現(xiàn)，需要更長(zhǎng)的執(zhí)行時(shí)間。文獻(xiàn)[15]提出同時(shí)考慮節(jié)點(diǎn)屬性和結(jié)構(gòu)的隱私聚類擾動(dòng)算法，在頂點(diǎn)間隨機(jī)交換屬性，誘導(dǎo)攻擊者錯(cuò)誤的方向，采用局部聚類和邊緣互補(bǔ)修改來(lái)擾動(dòng)，使隱私得到保證。文獻(xiàn)[16]提出(K,X)同構(gòu)加權(quán)社交隱私保護(hù)，改進(jìn)最大公共子圖方法，以找到更合適的子圖。文獻(xiàn)[17]提出基于節(jié)點(diǎn)中介中心性的匿名網(wǎng)絡(luò)重構(gòu)算法，把節(jié)點(diǎn)按照中介中心性進(jìn)行排列，具有較大值的候選節(jié)點(diǎn)優(yōu)先進(jìn)行重構(gòu)。以上基于匿名算法的研究在社交網(wǎng)絡(luò)隱私保護(hù)中都取得了較好的效果，但存在一個(gè)共同的缺陷就是在一定程度上丟失了原圖的重要特征，導(dǎo)致信息損失，降低了網(wǎng)絡(luò)數(shù)據(jù)效用，無(wú)法保證數(shù)據(jù)挖掘研究的有效進(jìn)行。另外還有一些研究采用差分技術(shù)來(lái)保護(hù)社交網(wǎng)絡(luò)的隱私，文獻(xiàn)[18-19]提出了一種基于差分隱私保護(hù)多核的聚類方案，通過(guò)添加一些隨機(jī)噪聲來(lái)增強(qiáng)數(shù)據(jù)聚類效果進(jìn)而保護(hù)隱私。文獻(xiàn)[20]提出了一種差分隱私保護(hù)密度聚類的方法，把拉普拉斯噪聲加入到局部密度和最短距離從而保護(hù)用戶的隱私。以上采用差分聚類來(lái)保護(hù)隱私，雖然可以防御背景知識(shí)的攻擊，但是數(shù)據(jù)對(duì)噪聲太過(guò)敏感，小的噪聲就會(huì)導(dǎo)致大的信息損失，從而導(dǎo)致數(shù)據(jù)可用性下降。針對(duì)以上不足，本文提出個(gè)性化等差數(shù)列聚類匿名分配算法(personalized arithmetic sequence clustering anonymous allocation algorithm，PAS-CAA)，在保證隱私安全的前提下，實(shí)現(xiàn)信息損失最小化。

本文主要的貢獻(xiàn)為：

1) 針對(duì)聚類算法存在隨機(jī)選取初始節(jié)點(diǎn)的敏感問(wèn)題，通過(guò)計(jì)算局部聚類密度參數(shù)對(duì)選取初始節(jié)點(diǎn)的算法進(jìn)行優(yōu)化，采取綜合相似度進(jìn)行聚類，提高聚類的有效性，同時(shí)也減少了信息的損失；

2) 在聚類過(guò)程中通過(guò)設(shè)置參數(shù)θΝ=k，使每個(gè)超點(diǎn)包含的個(gè)數(shù)至少為k。若不滿足該條件則取消該類進(jìn)行重新分配，保證每個(gè)超點(diǎn)都實(shí)現(xiàn)基本的k保護(hù)力度。把具有k保護(hù)力度的超點(diǎn)根據(jù)超點(diǎn)局部密度閾值ρθ劃分為敏感超點(diǎn)集(ρsuper≥ρθ)和非敏感超點(diǎn)集(ρsuper<ρθ)。為了實(shí)現(xiàn)信息損失最小化，對(duì)于敏感超點(diǎn)集采用遞減的等差數(shù)列進(jìn)行聚類，使每個(gè)敏感度不同的敏感超點(diǎn)擁有與其相對(duì)應(yīng)的隱私保護(hù)力度，其隱私保護(hù)力度范圍是[2k,min[Clustervalue]]。因此，在實(shí)現(xiàn)最低安全隱私保護(hù)的基礎(chǔ)上，體現(xiàn)個(gè)性化的隱私保護(hù)思想。

1 相關(guān)定義

定義1綜合相似度，是指結(jié)構(gòu)鄰近相似度simstr(vi,vl) 和個(gè)人信息屬性相似性simatr(vip,vlp)，其中p代表屬性通過(guò)調(diào)節(jié)參數(shù)β來(lái)進(jìn)行調(diào)節(jié)計(jì)算出的相似度，其值越大越容易聚在一起，其中：vi、vl指的節(jié)點(diǎn)i和節(jié)點(diǎn)l；nei(vi)指節(jié)點(diǎn)vi的鄰接節(jié)點(diǎn)。

S(vi,vl)=βsimstr(vi,vl)+(1-β)simatr(vip,vlp)=

β|nei(vi)∩nei(vl)|/|nei(vi)∪nei(vl)|+

(1)

其中：simatr(vip,vlp)=

同理任意節(jié)點(diǎn)vi和超點(diǎn)Vx的相似度表示為

(2)

定義2屬性的概化。社交網(wǎng)絡(luò)中的節(jié)點(diǎn)屬性一般分為數(shù)值型和非數(shù)值型。當(dāng)多個(gè)節(jié)點(diǎn)聚集成超點(diǎn)，數(shù)值型可以用[max(atr(clt)),min(atr(clt))]范圍來(lái)概化超點(diǎn)包含的所有節(jié)點(diǎn)的屬性值；對(duì)于非數(shù)值型可以采用泛化層次樹(shù)，圖1給出一棵愛(ài)好泛化層次樹(shù)，其中根節(jié)點(diǎn)的泛化范圍最大，不同層次上的分支節(jié)點(diǎn)代表不同泛化范圍。

圖1 愛(ài)好泛化層次樹(shù)

定義3局部密度ρ。給定節(jié)點(diǎn)vA，vAi是vA的k近鄰點(diǎn)，節(jié)點(diǎn)vA的局部密度ρ的計(jì)算公式為

(3)

其中：SNER(vA,vAi)是基于k近鄰聚類的共享近鄰相似度，代表節(jié)點(diǎn)vA和vAi的近鄰相似性，其值越大越容易聚在一塊。同理，超點(diǎn)的局部密度為

(4)

定義4局部聚類密度Cfs(vi)是局部聚類系數(shù)，|Ni|指vi的直接鄰居節(jié)點(diǎn)的個(gè)數(shù)，E{Ni}指節(jié)點(diǎn)vi的直接鄰居節(jié)點(diǎn)構(gòu)成邊的個(gè)數(shù)，公式為

CltCc(Vi)=1+ρVi*Cfs(vi)=1+ρvi*(|E{Ni}|/

(|Ni|*(|Ni|-1)/2))。

(5)

定義5遞減的等差數(shù)列公式為

Clustervalue=2k+(n-1)d,d<0,

(6)

其中：k是隱私保護(hù)力度；d指的是公差，根據(jù)敏感超點(diǎn)集隱私保護(hù)程度設(shè)定；min[Clustervalue]代表在敏感超點(diǎn)集中最小的隱私保護(hù)強(qiáng)度;2k為首項(xiàng)，代表敏感超點(diǎn)集中敏感度最高的超點(diǎn)的隱私保護(hù)力度，若3k/2有余數(shù)時(shí)，min[Clustervalue]等于3k/2取整加1，反之則取3k/2。

2 基于個(gè)性化等差數(shù)列聚類匿名分配算法

基于個(gè)性化等差數(shù)列聚類匿名分配算法(PAS-CAA)主要由三部分組成。首先利用初始節(jié)點(diǎn)優(yōu)化算法選出初始節(jié)點(diǎn)；然后利用相似矩陣算法把每個(gè)節(jié)點(diǎn)與初始節(jié)點(diǎn)的相似度計(jì)算出來(lái)形成矩陣；最后采用PAS-CAA算法根據(jù)該相似矩陣把節(jié)點(diǎn)分配到初始節(jié)點(diǎn)形成的簇中，若形成的簇中的個(gè)數(shù)小于k，則取消該簇,把該簇中的節(jié)點(diǎn)重新分配聚類，然后根據(jù)局部密度閾值ρθ，把形成的超點(diǎn)分成敏感超點(diǎn)集和非敏感超點(diǎn)集，讓所有非敏感超點(diǎn)集都形成k保護(hù)力度，而作為敏感超點(diǎn)集,需要更強(qiáng)的個(gè)性化保護(hù)，采取的保護(hù)強(qiáng)度范圍為[2k, min[Clustervalue]]，并根據(jù)敏感超點(diǎn)集中超點(diǎn)局部密度ρsuper進(jìn)行由高到低排序，用公式(6)遞減的等差數(shù)列進(jìn)行聚類分配，最后對(duì)每個(gè)超點(diǎn)進(jìn)行匿名化處理。實(shí)現(xiàn)了可以根據(jù)超點(diǎn)隱私要求來(lái)靈活地提供隱私保護(hù)力度，從而最大程度上減少信息損失，提高數(shù)據(jù)的利用率。

2.1 初始節(jié)點(diǎn)的優(yōu)化算法

由于K-means算法存在一定的局限性，對(duì)隨機(jī)選取初始節(jié)點(diǎn)敏感，因此利用局部密度和局部聚類系數(shù)相結(jié)合來(lái)選擇初始中心點(diǎn)，采用綜合相似度進(jìn)行聚類，實(shí)現(xiàn)更準(zhǔn)確有效的聚類效果。按局部聚類密度對(duì)所有的節(jié)點(diǎn)進(jìn)行排序，首先選取局部聚類密度最大的一個(gè)節(jié)點(diǎn)作為初始點(diǎn)，同時(shí)需要滿足聚類的特性就是簇內(nèi)的節(jié)點(diǎn)盡量緊密連在一起或相似，不同簇中的節(jié)點(diǎn)盡量遠(yuǎn)離或不同，所以第二個(gè)初始節(jié)點(diǎn)要選一個(gè)與第一個(gè)初始節(jié)點(diǎn)相似度最小，并且還要使局部聚類密度相對(duì)較大的節(jié)點(diǎn)。

算法1初始節(jié)點(diǎn)優(yōu)化算法。

輸入：G(V,E,A)，聚類個(gè)數(shù)Nc。

輸出： 初始中心節(jié)點(diǎn)。

Step1 根據(jù)公式(5)計(jì)算局部聚類密度，獲取高聚集密度區(qū)域，得到集合HighCltCc；

Step2 選取局部聚類密度最大的節(jié)點(diǎn)作為第一個(gè)初始中心seed1；

Step3 在集合HighCltCc中選取與seed1相似度最小的點(diǎn)形成一個(gè)集合，并在該集合中選取局部聚類密度最大的點(diǎn)作為seed2；

Step4 以此類推，初始中心點(diǎn)的計(jì)算方法為

vl∈HighCltCc;

Step5 選出初始中心節(jié)點(diǎn)。

2.2 個(gè)性化等差數(shù)列聚類匿名算法

在聚類過(guò)程中，設(shè)置參數(shù)θΝ=k,保證了每個(gè)超點(diǎn)都符合最基本的k保護(hù)力度，通過(guò)ρθ局部密度閾值劃分成兩個(gè)區(qū)域，敏感超點(diǎn)集和非敏感超點(diǎn)集。根據(jù)超點(diǎn)局部密度對(duì)敏感超點(diǎn)集中的超點(diǎn)進(jìn)行一個(gè)由高到低的排序，為減少信息的損失，采取遞減的等差數(shù)列進(jìn)行聚類，從而可以靈活地根據(jù)所需要的隱私保護(hù)來(lái)實(shí)現(xiàn)不同程度的保護(hù)力度，在敏感超點(diǎn)集中設(shè)定了隱私保護(hù)力度最大值為2k，并根據(jù)公式(6)計(jì)算敏感超點(diǎn)所對(duì)應(yīng)的保護(hù)力度，范圍為[2k, min[Clustervalue]]。當(dāng)采用遞減的等差數(shù)列進(jìn)行聚類時(shí)，若敏感超點(diǎn)集的隱私保護(hù)力度小于min[Clustervalue]，為了保證足夠的隱私安全，該超點(diǎn)及之后的超點(diǎn)就進(jìn)行保護(hù)力度為min[Clustervalue]的聚類，該方法保證最低隱私安全程度的同時(shí)，實(shí)現(xiàn)了個(gè)性化的隱私保護(hù)，使得需要高隱私保護(hù)要求的簇達(dá)到隱私要求的同時(shí)減少信息損失，需要低隱私保護(hù)的簇在實(shí)現(xiàn)數(shù)據(jù)安全性的同時(shí)保護(hù)隱私。

算法2計(jì)算相似矩陣。

輸入： 用戶集Nn、屬性集Am、初始節(jié)點(diǎn)SeedNc。

輸出： 有序相似矩陣HT。

Step1 對(duì)于每個(gè)節(jié)點(diǎn)，利用公式(1)計(jì)算該節(jié)點(diǎn)和各個(gè)SeedNc之間的相似度;

Step2 把計(jì)算出的第一個(gè)節(jié)點(diǎn)和各個(gè)SeedNc的相似度放在矩陣的第一列，并用D1表示;

Step3 同理分別把各個(gè)節(jié)點(diǎn)與各個(gè)SeedNc算出的相似度用Dn表示;

Step4 最后形成大小為1*nNc的矩陣HT=(D1D2…Dn)。

算法3PAS-CAA算法。

輸入： 原始社交網(wǎng)絡(luò)圖G，聚類個(gè)數(shù)Nc。

輸出： 社交網(wǎng)絡(luò)圖G*=(V*,E*,A*)。

Step1 通過(guò)算法1選出Nc個(gè)初始中心,再把初始中心分配到每個(gè)簇中形成μ={μ1，μ2，…，μN(yùn)c};

Step2 利用算法2計(jì)算相似矩陣HT；

Step3 把未分配的節(jié)點(diǎn)根據(jù)公式(2)相似度的大小分配到簇中；

Step4 判斷每個(gè)簇中的元素個(gè)數(shù)是否小于θΝ(θΝ代表聚類中的最小節(jié)點(diǎn)數(shù)，為實(shí)現(xiàn)k隱私保護(hù)力度，θΝ=k),若小于θΝ就要取消該類，Nc=Nc-1,把取消的這個(gè)類中的節(jié)點(diǎn)重新分配，根據(jù)S(vi,VX)相似度的大小來(lái)分配到相應(yīng)的簇中；

Step5 針對(duì)所形成的超點(diǎn)，計(jì)算超點(diǎn)的局部密度ρsuper，超點(diǎn)的局部密度≥ρθ(局部密度閾值)，該超點(diǎn)歸到敏感超點(diǎn)集中，反之放在非敏感超點(diǎn)集中；

Step6 非敏感超點(diǎn)集中節(jié)點(diǎn)個(gè)數(shù)大于k的超點(diǎn)中|Cluster| ≥k&min[S(vi,Vx)]的節(jié)點(diǎn)放在集合A中；

Step7 把敏感超點(diǎn)集中的超點(diǎn)根據(jù)ρsuper進(jìn)行由高到低的排序；

Step8 根據(jù)步驟7中敏感超點(diǎn)由高到低的排序，依次利用max[S(vi,Vx)]把集合A中的點(diǎn)分配到敏感超點(diǎn)集的超點(diǎn)中，敏感度最高的超點(diǎn)采用2k隱私保護(hù)力度，然后利用公式(6)進(jìn)行遞減的等差數(shù)列聚類分配；

Step9 達(dá)到最大迭代數(shù)Im則終止，否則返回到Step3；

Step10 對(duì)每個(gè)超點(diǎn)進(jìn)行匿名化(屬性概化)處理；

Step11 得到聚類結(jié)果G*=(V*,E*,A*)。

3 算法分析

3.1 時(shí)間復(fù)雜度

根據(jù)算法1算出所有節(jié)點(diǎn)的局部聚類密度，并在高聚集密度區(qū)域形成一些種子節(jié)點(diǎn)集，外層是簇的個(gè)數(shù)，內(nèi)層是高聚集密度區(qū)域循環(huán)，因此算法1的時(shí)間復(fù)雜度是O(n2)。算法2計(jì)算相似矩陣，求解綜合相似度是在O(l)中完成，所以時(shí)間復(fù)雜度是O(n2)。算法3把待分配節(jié)點(diǎn)都分配到簇中，外層是未分配節(jié)點(diǎn)數(shù)目的循環(huán)，內(nèi)層是簇個(gè)數(shù)的循環(huán)，且簇個(gè)數(shù)小于等于n/k，所以時(shí)間復(fù)雜度是O(n2)；同理，算法3把A集合中的節(jié)點(diǎn)分配到敏感超點(diǎn)集中未滿足隱私保護(hù)力度的超點(diǎn)中，A集合的節(jié)點(diǎn)小于n，未滿足匿名程度簇個(gè)數(shù)小于n/k，分配方法相同，時(shí)間復(fù)雜度也相同為O(n2)；算法3對(duì)屬性概化的時(shí)間復(fù)雜度是O(n2)。綜上所述，本文算法的時(shí)間復(fù)雜度是O(n2)。

3.2 安全性

PAS-CAA算法根據(jù)綜合相似性度進(jìn)行聚類，形成超點(diǎn)，每個(gè)超點(diǎn)至少有k個(gè)節(jié)點(diǎn)，用超點(diǎn)內(nèi)的節(jié)點(diǎn)個(gè)數(shù)及邊數(shù)來(lái)代替各個(gè)子圖的具體結(jié)構(gòu)，把超點(diǎn)內(nèi)、超點(diǎn)之間節(jié)點(diǎn)的連接程度和子圖的結(jié)構(gòu)進(jìn)行隱匿，可以抵御結(jié)構(gòu)攻擊；用超點(diǎn)的泛化值代替其內(nèi)部各個(gè)節(jié)點(diǎn)的屬性值，可以防止擁有屬性背景知識(shí)的攻擊。同時(shí)，考慮到敏感程度不同的超點(diǎn)對(duì)于隱私保護(hù)需求不一致，因此，需要不同的隱私保護(hù)強(qiáng)度，根據(jù)局部密度閾值ρθ，把超點(diǎn)分為敏感超點(diǎn)集和非敏感超點(diǎn)集，對(duì)于隱私要求最高的敏感超點(diǎn)采用2k隱私保護(hù)強(qiáng)度進(jìn)行保護(hù)，隨著隱私要求不斷下降的敏感超點(diǎn)采用遞減的等差數(shù)列進(jìn)行隱私保護(hù)，直到敏感超點(diǎn)實(shí)現(xiàn)的隱私保護(hù)力度小于min[Clustervalue]，代表隱私保護(hù)力度再低就不能保證敏感超點(diǎn)的隱私安全，所以該敏感超點(diǎn)及之后的敏感超點(diǎn)采用隱私強(qiáng)度為min[Clustervalue]進(jìn)行聚類，因此隱私保護(hù)力度范圍是[2k，min[Clustervalue]]，使敏感超點(diǎn)集中所有超點(diǎn)隱私保護(hù)力度都大于等于1.5k，避免降低高隱私保護(hù)力度節(jié)點(diǎn)的安全性；對(duì)于非敏感超點(diǎn)集采用的隱私保護(hù)力度為k，使攻擊者識(shí)別概率最高只能到1/k。最后，對(duì)所有超點(diǎn)進(jìn)行匿名化處理。隱匿、泛化和個(gè)性化的等差數(shù)列聚類形成了多重的隱私保護(hù)，因此具有很強(qiáng)的保護(hù)效果。

3.3 有效性

有效性指的是在保證隱私不被泄露的同時(shí)要減少信息損失實(shí)現(xiàn)數(shù)據(jù)的可用性，信息損失越少，代表數(shù)據(jù)的可用性越高。采用PAS-CAA算法進(jìn)行聚類時(shí)，遵循綜合相似度最大原則，即綜合相似度越大的兩個(gè)節(jié)點(diǎn)聚在同一個(gè)簇中，信息損失就越少。同理，節(jié)點(diǎn)與簇聚類也是遵循綜合相似度最大原則，因此信息損失最少。同時(shí)把聚類以后的超點(diǎn)劃分成非敏感超點(diǎn)集和敏感超點(diǎn)集，對(duì)于非敏感超點(diǎn)集中的超點(diǎn)，需要的隱私保護(hù)程度較低，因此用k保護(hù)力度就可以保持基本安全，避免隱私保護(hù)力度過(guò)大導(dǎo)致低隱私需求的超點(diǎn)損失更多信息的弊端；對(duì)于敏感超點(diǎn)集采用遞減等差數(shù)列進(jìn)行聚類，使需要的隱私保護(hù)力度和要求的隱私程度相符合，可以靈活有效地調(diào)節(jié)隱私保護(hù)力度，減少信息損失?？傊?，使得信息損失最小化，因此，具有較高的有效性。

4 實(shí)驗(yàn)驗(yàn)證

實(shí)驗(yàn)采用Windows 10(64位)，處理器是Intel(R) Core(TM) i5-6200U CPU@2.3 GHz 2.40 GHz,RAM為4.00 GB的主機(jī)。

4.1 數(shù)據(jù)集

實(shí)驗(yàn)?zāi)康氖菍?shí)現(xiàn)隱私保護(hù)的同時(shí)使社交網(wǎng)絡(luò)數(shù)據(jù)擁有好的可用性。實(shí)驗(yàn)數(shù)據(jù)來(lái)自UC Irvine Machine Learning Repository的 Adult 數(shù)據(jù)集，分別從中任意取500 個(gè)節(jié)點(diǎn)和 700 個(gè)節(jié)點(diǎn)構(gòu)成社交網(wǎng)絡(luò)，記為M1和M2，利用Python3在兩個(gè)真實(shí)數(shù)據(jù)集上比較PAS-CAA算法、經(jīng)典聚類匿名算法SaNGreeA[21]、CAA-VS算法[22]和Adaptive-Dense-Cfs算法[23]的總體信息損失和消耗的時(shí)間。

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

實(shí)驗(yàn)比較上述算法在數(shù)據(jù)集上的總體信息損失。信息損失包括個(gè)人屬性和結(jié)構(gòu)損失，個(gè)人屬性損失包括數(shù)值和非數(shù)值損失，結(jié)構(gòu)損失包括超點(diǎn)內(nèi)部損失和簇之間的損失。

個(gè)人屬性損失為

(7)

(length(atrLp,root))/n， 非數(shù)值型

(8)

其中：n指的是節(jié)點(diǎn)的個(gè)數(shù)；clt={clt1,clt2,clt3，…,cltt}為匿名后的社交網(wǎng)絡(luò)；clti={v1,v2,v3,…,vj},atrLj代表節(jié)點(diǎn)vj在屬性L上的值。

結(jié)構(gòu)損失為

(|clti|*|cltj|))))/(n*(n-1)/4)。

(9)

總體信息損失為

sum_loss=(Sum_lossinf+Sum_lossstr)/2。

(10)

實(shí)驗(yàn)在數(shù)據(jù)集M1和M2上的總體信息損失結(jié)果分別如圖2、圖3所示。從圖2和圖3中可以看出，隨著簇中節(jié)點(diǎn)數(shù)(隱私保護(hù)力度)k的增大，隱匿性自然會(huì)越好，總體信息損失也會(huì)增大，因?yàn)闀?huì)有更多的節(jié)點(diǎn)和邊及其結(jié)構(gòu)被隱匿，并且每個(gè)超點(diǎn)的泛化范圍也會(huì)變大，導(dǎo)致總體信息損失變大。同時(shí)圖2和圖3的sum_loss比較接近，因?yàn)閟um_loss代表總的平均信息損失，但是總體看來(lái)圖3的總體信息損失相對(duì)較大，因?yàn)閿?shù)據(jù)集的增大會(huì)按比例使簇中不同類型的屬性值更大程度被隱匿。PAS-CAA算法比其他算法有著較低的總體信息損失，因?yàn)镻AS-CAA算法把超點(diǎn)劃分成非敏感超點(diǎn)集和敏感超點(diǎn)集，對(duì)敏感超點(diǎn)集采用遞減等差數(shù)列進(jìn)行聚類分配，在隱私保護(hù)力度為[2k, min[Clustervalue]]中可以進(jìn)行動(dòng)態(tài)個(gè)性化聚類分配，使隱私要求與保護(hù)程度貼切，避免使用相同的隱私保護(hù)力度導(dǎo)致與實(shí)際需求的保護(hù)力度不一致，從而減少總體信息損失，對(duì)于非敏感超點(diǎn)集進(jìn)行k保護(hù)力度聚類，保證了最低隱私安全。所以PAS-CAA算法總體信息損失最小，更具有數(shù)據(jù)有效性。

圖2 在M1下總體信息損失比較

圖3 在M2下總體信息損失比較

如圖4和圖5所示，在數(shù)據(jù)集M2上比M1上用的時(shí)間多，因?yàn)閿?shù)據(jù)越多，就需要越多的時(shí)間處理。PAS-CAA算法避免進(jìn)行多余的聚類分配來(lái)實(shí)現(xiàn)比實(shí)際需求高的隱私保護(hù)力度，從而時(shí)間最少、效率最高。因此PAS-CAA算法的時(shí)間變化率基本為0，不隨k的變化而變化。

圖4 在M1下時(shí)間比較

圖5 在M2下時(shí)間比較

5 總結(jié)

針對(duì)社交網(wǎng)絡(luò)數(shù)據(jù)的急劇增加不能實(shí)現(xiàn)隱私保護(hù)力度和數(shù)據(jù)可用性平衡的問(wèn)題，提出了PAS-CAA算法，對(duì)K-means 沒(méi)有結(jié)合社交網(wǎng)絡(luò)的特點(diǎn)和初始節(jié)點(diǎn)選擇敏感的問(wèn)題進(jìn)行了改進(jìn)。利用局部聚類密度來(lái)選擇初始中心節(jié)點(diǎn)，根據(jù)綜合相似性進(jìn)行更加準(zhǔn)確地聚類，減少信息的損失，使得每個(gè)簇中至少包括k個(gè)節(jié)點(diǎn)，并且根據(jù)超點(diǎn)有著不同程度的隱私需求，分成了敏感超點(diǎn)集和非敏感超點(diǎn)集，對(duì)敏感超點(diǎn)集采用等差數(shù)列進(jìn)行聚類分配，從而可以不斷地根據(jù)敏感超點(diǎn)所需的隱私要求進(jìn)行相應(yīng)的隱私保護(hù)。在未來(lái)的工作中，要設(shè)計(jì)抵御一切背景知識(shí)攻擊的差分聚類算法，采用準(zhǔn)確聚類的動(dòng)態(tài)分配隱私預(yù)算的方法，使得可以根據(jù)用戶的隱私保護(hù)要求進(jìn)行更加準(zhǔn)確地分配，提高聚類結(jié)果的準(zhǔn)確性和效率，同時(shí)提高差分聚類后數(shù)據(jù)的實(shí)用性。