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

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

0 引言

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

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

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

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

1 相關(guān)定義

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

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

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

(1)

其中：simatr(vip,vlp)=

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

(2)

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

圖1 愛好泛化層次樹

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

(3)

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

(4)

定義4局部聚類密度Cfs(vi)是局部聚類系數(shù)，|Ni|指vi的直接鄰居節(jié)點的個數(shù)，E{Ni}指節(jié)點vi的直接鄰居節(jié)點構(gòu)成邊的個數(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ù)敏感超點集隱私保護(hù)程度設(shè)定；min[Clustervalue]代表在敏感超點集中最小的隱私保護(hù)強(qiáng)度;2k為首項，代表敏感超點集中敏感度最高的超點的隱私保護(hù)力度，若3k/2有余數(shù)時，min[Clustervalue]等于3k/2取整加1，反之則取3k/2。

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

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

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

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

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

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

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

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

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

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

Step4 以此類推，初始中心點的計算方法為

vl∈HighCltCc;

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

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

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

算法2計算相似矩陣。

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

輸出： 有序相似矩陣HT。

Step1 對于每個節(jié)點，利用公式(1)計算該節(jié)點和各個SeedNc之間的相似度;

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

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

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

算法3PAS-CAA算法。

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

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

Step1 通過算法1選出Nc個初始中心,再把初始中心分配到每個簇中形成μ={μ1，μ2，…，μNc};

Step2 利用算法2計算相似矩陣HT；

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

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

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

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

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

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

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

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

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

3 算法分析

3.1 時間復(fù)雜度

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

3.2 安全性

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

3.3 有效性

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

4 實驗驗證

實驗采用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ù)集

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

4.2 實驗結(jié)果分析

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

個人屬性損失為

(7)

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

(8)

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

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

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

(9)

總體信息損失為

sum_loss=(Sum_lossinf+Sum_lossstr)/2。

(10)

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

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

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

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

圖4 在M1下時間比較

圖5 在M2下時間比較

5 總結(jié)

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