董祥祥，高 昂，梁 英，畢曉迪

1.中國(guó)科學(xué)院 計(jì)算技術(shù)研究所，北京 100190

2.中國(guó)科學(xué)院大學(xué)，北京 100190

3.移動(dòng)計(jì)算與新型終端北京市重點(diǎn)實(shí)驗(yàn)室，北京 100190

1 引言

“社會(huì)網(wǎng)絡(luò)”是指社會(huì)個(gè)體成員之間因?yàn)榛?dòng)而形成的相對(duì)穩(wěn)定的關(guān)系體系，已成為人們溝通交流、獲取信息和展示自我的重要途徑之一。近年來(lái)，隨著社會(huì)網(wǎng)絡(luò)的發(fā)展，數(shù)據(jù)泄露事件頻發(fā)，同時(shí)大數(shù)據(jù)挖掘技術(shù)的廣泛應(yīng)用，造成社會(huì)網(wǎng)絡(luò)公開(kāi)發(fā)布的數(shù)據(jù)和泄露的數(shù)據(jù)進(jìn)一步暴露隱私，用戶(hù)隱私面臨威脅。表1 展示了2018 年十大數(shù)據(jù)泄露事件，其中涉及了使用范圍較廣泛的國(guó)內(nèi)外社交網(wǎng)站與社交應(yīng)用。由于這些線(xiàn)上社交網(wǎng)絡(luò)存儲(chǔ)了大量的用戶(hù)注冊(cè)與使用信息，具有隱私性，故成為時(shí)下數(shù)據(jù)泄露的重災(zāi)區(qū)。

Table 1 10 biggest data breaches of 2018表1 2018年度十大數(shù)據(jù)泄露事件

據(jù)第27 次至39 次《中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》顯示（如圖1 所示），2011 年1 月至2017 年1 月微博用戶(hù)量呈現(xiàn)緩慢波動(dòng)的趨勢(shì)。這意味著隨著用戶(hù)加入和退出社交應(yīng)用，社會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)也存在增加和減少的變化，并且節(jié)點(diǎn)間會(huì)建立或去除連接關(guān)系。

Fig.1 Sina Weibo user statistics圖1 新浪微博用戶(hù)量統(tǒng)計(jì)

Viswanath 等人[1]以Facebook 為例進(jìn)行分析，得出社會(huì)網(wǎng)絡(luò)是具有動(dòng)態(tài)性的，相應(yīng)的匿名方法也適應(yīng)隨時(shí)間變化的性質(zhì)，具有動(dòng)態(tài)性。社會(huì)網(wǎng)絡(luò)中的數(shù)據(jù)無(wú)時(shí)無(wú)刻不在進(jìn)行更新迭代，社會(huì)網(wǎng)絡(luò)的動(dòng)態(tài)性也決定了靜態(tài)隱私保護(hù)方法不能保證動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)的隱私安全[2]。攻擊者可以將前后發(fā)布版本進(jìn)行關(guān)聯(lián)分析，可能得到個(gè)體的敏感信息，從而會(huì)導(dǎo)致社會(huì)網(wǎng)絡(luò)的數(shù)據(jù)泄露[3]。因此，開(kāi)展動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)隱私保護(hù)方法研究，滿(mǎn)足用戶(hù)的個(gè)性化隱私保護(hù)需求，同時(shí)確保數(shù)據(jù)的可用性變得非常重要。

社會(huì)網(wǎng)絡(luò)中的隱私信息包括節(jié)點(diǎn)、邊和圖的隱私，這些隱私信息一旦被攻擊者獲取并進(jìn)行攻擊與挖掘，將會(huì)威脅用戶(hù)自身及其好友的隱私。針對(duì)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)發(fā)布的隱私泄露，隱私保護(hù)方法可分為靜態(tài)方法和動(dòng)態(tài)方法。靜態(tài)方法指社會(huì)網(wǎng)絡(luò)數(shù)據(jù)單實(shí)例發(fā)布，即將社會(huì)網(wǎng)絡(luò)的每次更新視作一個(gè)新的網(wǎng)絡(luò)，在新的網(wǎng)絡(luò)發(fā)布時(shí)對(duì)數(shù)據(jù)進(jìn)行匿名處理，隱藏敏感信息，并在發(fā)布后不再更改這些數(shù)據(jù)。而動(dòng)態(tài)方法在新數(shù)據(jù)發(fā)布與匿名時(shí)，會(huì)涉及已發(fā)布的數(shù)據(jù)，再次對(duì)已發(fā)布的數(shù)據(jù)進(jìn)行處理。

目前社會(huì)網(wǎng)絡(luò)數(shù)據(jù)發(fā)布隱私保護(hù)方法多為靜態(tài)的方法。在節(jié)點(diǎn)屬性隱私保護(hù)研究方面，主要包括傳統(tǒng)方法和關(guān)注實(shí)用價(jià)值的方法。如使用原始K-匿名、L-多樣性和T-近鄰對(duì)社交網(wǎng)絡(luò)用戶(hù)屬性進(jìn)行屬性匿名[4]，通過(guò)在圖中增加噪音節(jié)點(diǎn)保護(hù)用戶(hù)隱私，將相似的節(jié)點(diǎn)聚類(lèi)成超節(jié)點(diǎn)[5]等。除上述傳統(tǒng)的匿名方法，將隱私保護(hù)結(jié)合其實(shí)用價(jià)值考慮也受到廣泛關(guān)注。針對(duì)實(shí)際問(wèn)題，Sei等人[6]提出敏感準(zhǔn)標(biāo)識(shí)符屬性的概念，采用改進(jìn)的L-多樣性和T-近鄰的方法可以有效地對(duì)敏感準(zhǔn)標(biāo)識(shí)符屬性進(jìn)行匿名。Hartung等人[7]改進(jìn)了NP-Hard問(wèn)題——K度匿名，用動(dòng)態(tài)規(guī)劃和啟發(fā)式方法進(jìn)行求解，可以高效地應(yīng)對(duì)大規(guī)模社會(huì)網(wǎng)絡(luò)的匿名問(wèn)題，但對(duì)數(shù)據(jù)隨機(jī)性不敏感。付艷艷等人[8]將社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)的屬性分為敏感屬性和非敏感屬性，以節(jié)點(diǎn)分割的方式保護(hù)用戶(hù)的敏感屬性，但其有效性很大程度上依賴(lài)于匿名區(qū)域內(nèi)屬性是否相關(guān)。劉向宇等人[9]提出了一種保持節(jié)點(diǎn)可達(dá)性的高效社會(huì)網(wǎng)絡(luò)圖匿名方法，避免可達(dá)性信息損失，但在某種程度上會(huì)降低距離查詢(xún)的精度。節(jié)點(diǎn)屬性包含了用戶(hù)的基本隱私信息，上述隱私保護(hù)方法在保護(hù)節(jié)點(diǎn)屬性的同時(shí)，雖然涉及了圖結(jié)構(gòu)數(shù)據(jù)的可用性，但是對(duì)于邊的保護(hù)不足，存在邊信息泄露的風(fēng)險(xiǎn)。在關(guān)系和邊的隱私保護(hù)研究方面，最基礎(chǔ)的圖結(jié)構(gòu)隱私保護(hù)方法是隨機(jī)圖編輯，即在圖中進(jìn)行隨機(jī)修改或交換邊的操作。Hay 等人[10]針對(duì)節(jié)點(diǎn)再識(shí)別和邊屬性攻擊提出了最簡(jiǎn)單的社會(huì)網(wǎng)絡(luò)匿名方法，僅僅從圖中去掉n條邊再隨機(jī)增加n條邊，形成新的社會(huì)網(wǎng)絡(luò)圖，但是隱私保護(hù)強(qiáng)度很低。Li等人[11]使用概率方法對(duì)圖數(shù)據(jù)進(jìn)行隨機(jī)更改，提出了兩種方法，分別為隨機(jī)稀疏化和隨機(jī)擾動(dòng)化，但該方法僅以概率來(lái)衡量隱私保護(hù)，無(wú)法應(yīng)對(duì)有背景知識(shí)的攻擊。Liu等人[12]將社會(huì)網(wǎng)絡(luò)中邊的權(quán)重作為隱私保護(hù)的對(duì)象，在保障圖中最短路徑序列以及每對(duì)節(jié)點(diǎn)間的最短距離的同時(shí)，通過(guò)對(duì)邊的權(quán)重增加高斯噪音進(jìn)行擾動(dòng)。Rong等人[13]把K-匿名思想應(yīng)用到圖結(jié)構(gòu)隱私保護(hù)中，提出一種K+-同構(gòu)方法對(duì)圖數(shù)據(jù)進(jìn)行修改，在子圖中達(dá)到K-匿名狀態(tài)。

現(xiàn)有動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)隱私保護(hù)方法可分為傳統(tǒng)的靜態(tài)社會(huì)網(wǎng)絡(luò)隱私保護(hù)移植方法、鏈路預(yù)測(cè)方法和增量式抽象方法。Cheng 等人[14]針對(duì)節(jié)點(diǎn)信息和連接信息攻擊，提出K-同構(gòu)的概念，將節(jié)點(diǎn)的標(biāo)識(shí)符進(jìn)行泛化后發(fā)布于社會(huì)網(wǎng)絡(luò)中，可以有效地對(duì)節(jié)點(diǎn)信息進(jìn)行保護(hù),但數(shù)據(jù)的可用性和匿名的質(zhì)量依賴(lài)于同構(gòu)子圖的劃分，魯棒性比較低。谷勇浩等人[15]提出基于聚類(lèi)的動(dòng)態(tài)圖發(fā)布隱私保護(hù)方法，使用隱匿率作為評(píng)價(jià)指標(biāo)，可以抵御多種背景知識(shí)攻擊，對(duì)社會(huì)網(wǎng)絡(luò)圖結(jié)構(gòu)變化具有較好的適應(yīng)性，但算法復(fù)雜度較高，執(zhí)行效率低。Chen等人[16]通過(guò)K分組的方法將節(jié)點(diǎn)被攻擊識(shí)別的概率降低為1/k，但并未在真實(shí)的社會(huì)網(wǎng)絡(luò)中進(jìn)行實(shí)驗(yàn)，實(shí)用性未知。Bhagat等人[17]采用鏈接預(yù)測(cè)的方式預(yù)測(cè)未來(lái)圖結(jié)構(gòu)，從而對(duì)邊和節(jié)點(diǎn)進(jìn)行保護(hù)，但匿名效果很大程度上依賴(lài)于鏈接預(yù)測(cè)的質(zhì)量，保護(hù)效果不穩(wěn)定。郭彩華等人[18]首次提出加權(quán)圖增量序列K-匿名隱私保護(hù)模型，將動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)抽象為加權(quán)圖的增量序列，提高了算法效率，但邊權(quán)重的設(shè)置方式不具有普遍性。差分隱私作為隱私保護(hù)領(lǐng)域的一項(xiàng)重要技術(shù)被應(yīng)用于動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)隱私保護(hù)中，但在動(dòng)態(tài)數(shù)據(jù)發(fā)布的應(yīng)用中面臨隱私預(yù)算耗盡時(shí)噪音驟增的問(wèn)題。Chan等人[19]通過(guò)設(shè)置一個(gè)閾值來(lái)判斷當(dāng)前時(shí)刻是否需要進(jìn)行隱私保護(hù)處理，但隨時(shí)間增長(zhǎng)隱私預(yù)算會(huì)被耗盡。蘭麗輝等人[20]提出了一種基于差分隱私模型的隱私保護(hù)方法，其實(shí)質(zhì)也是通過(guò)對(duì)社會(huì)網(wǎng)絡(luò)的結(jié)構(gòu)進(jìn)行擾動(dòng)實(shí)現(xiàn)隱私保護(hù)。

綜上所述，社會(huì)網(wǎng)絡(luò)數(shù)據(jù)發(fā)布隱私保護(hù)研究主要針對(duì)單實(shí)例發(fā)布的靜態(tài)網(wǎng)絡(luò)，即數(shù)據(jù)發(fā)布后不再進(jìn)行任何改變。而社會(huì)網(wǎng)絡(luò)是一種動(dòng)態(tài)網(wǎng)絡(luò)，由抽象的數(shù)學(xué)模型角度來(lái)看，動(dòng)態(tài)網(wǎng)絡(luò)可以認(rèn)為是一個(gè)圖快照序列[21]。針對(duì)單實(shí)例發(fā)布的隱私保護(hù)方法實(shí)際上就是對(duì)一個(gè)時(shí)刻的圖快照進(jìn)行保護(hù)，不能適應(yīng)具有高度動(dòng)態(tài)性的社會(huì)網(wǎng)絡(luò)的更新迭代過(guò)程。比如，攻擊者可以根據(jù)2次單實(shí)例匿名的社會(huì)網(wǎng)絡(luò)分析出社會(huì)網(wǎng)絡(luò)圖中節(jié)點(diǎn)的度信息變化，結(jié)合其背景知識(shí)進(jìn)行分析，獲取用戶(hù)隱私。其次，用戶(hù)的個(gè)性化隱私保護(hù)方案較少，難以滿(mǎn)足數(shù)以?xún)|計(jì)的社會(huì)網(wǎng)絡(luò)用戶(hù)的隱私保護(hù)需求，用戶(hù)偏好設(shè)置上只考慮了用戶(hù)隱私保護(hù)程度這一單一的偏好，忽略了用戶(hù)發(fā)布的社會(huì)網(wǎng)絡(luò)數(shù)據(jù)可用性。

本文針對(duì)動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)發(fā)布隱私泄露問(wèn)題，基于匿名規(guī)則研究圖數(shù)據(jù)的隱私保護(hù)方法，支持用戶(hù)個(gè)性化隱私需求，抵御數(shù)據(jù)發(fā)布的關(guān)聯(lián)攻擊。同時(shí)采集了新浪微博數(shù)據(jù)和公開(kāi)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，對(duì)數(shù)據(jù)安全性和可用性相關(guān)指標(biāo)進(jìn)行了評(píng)估。

2 定義及流程

2.1 問(wèn)題提出

社會(huì)網(wǎng)絡(luò)是一種實(shí)時(shí)更新的、動(dòng)態(tài)的網(wǎng)絡(luò)。數(shù)據(jù)發(fā)布更新時(shí)，可能會(huì)和已發(fā)布的數(shù)據(jù)產(chǎn)生數(shù)據(jù)關(guān)聯(lián)，即使在兩個(gè)時(shí)刻分別對(duì)圖數(shù)據(jù)進(jìn)行了隱私保護(hù)，攻擊者也可能通過(guò)兩個(gè)時(shí)刻的社會(huì)網(wǎng)絡(luò)圖進(jìn)行關(guān)聯(lián)攻擊，挖掘其中的隱私信息。假設(shè)使用K-匿名技術(shù)對(duì)社會(huì)網(wǎng)絡(luò)進(jìn)行隱私保護(hù)，k值取2，同時(shí)假設(shè)同一個(gè)匿名集中的節(jié)點(diǎn)之間不存在連接關(guān)系。T=0,T=1時(shí)刻的社會(huì)網(wǎng)絡(luò)圖分別如圖2（a）中的G0、G1所示，對(duì)這兩個(gè)時(shí)刻的社會(huì)網(wǎng)絡(luò)進(jìn)行匿名后，得到如圖2（a）中的所示的社會(huì)網(wǎng)絡(luò)。從圖中可以看出，匿名后的社會(huì)網(wǎng)絡(luò)每?jī)蓚€(gè)節(jié)點(diǎn)被分為一組，同一組節(jié)點(diǎn)之間不存在連接關(guān)系。但值得注意的是，T=0時(shí)，節(jié)點(diǎn)（1，2）（3，5）（4，8）（6，7）分別在同一個(gè)匿名集中；而T=1 時(shí)，節(jié)點(diǎn)（1，2）（3，5）（4，6）（7，8）分別在同一個(gè)分組中。根據(jù)前文所述規(guī)則可以進(jìn)行猜測(cè)，節(jié)點(diǎn)4與節(jié)點(diǎn)6、節(jié)點(diǎn)8均可以在同一分組中，但是其不能與節(jié)點(diǎn)7 分在同一個(gè)組，由此可以推測(cè)，節(jié)點(diǎn)4與節(jié)點(diǎn)7可能存在連接關(guān)系。

圖2（a）中的G0、G1可以得到驗(yàn)證，上述猜測(cè)是正確的，即攻擊者利用關(guān)聯(lián)攻擊獲取了隱私信息。

本文算法目的在于抵御關(guān)聯(lián)攻擊所帶來(lái)的隱私泄露威脅，對(duì)圖2（a）中的G0、G1進(jìn)行隱私保護(hù)，隱私保護(hù)參數(shù)設(shè)置相同的情況下，得到如圖2（b）所示的執(zhí)行結(jié)果，即這兩個(gè)匿名圖中的節(jié)點(diǎn)分組相同，可有效抵御關(guān)聯(lián)攻擊。

Fig.2 Associated attack schema in dynamic social networks圖2 動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中的關(guān)聯(lián)攻擊示意圖

2.2 概念定義

為方便閱讀，本文常用的符號(hào)、公式及字母用表2進(jìn)行統(tǒng)一說(shuō)明。

定義1（隱私偏好preference）隱私偏好指用戶(hù)在社會(huì)網(wǎng)絡(luò)中的個(gè)性化隱私保護(hù)需求，包括隱私保護(hù)強(qiáng)度和社會(huì)網(wǎng)絡(luò)數(shù)據(jù)可用性的需求，可用二元組表示。其中l(wèi)evels表示用戶(hù)對(duì)其隱私的保護(hù)強(qiáng)度需求等級(jí)，levelu表示用戶(hù)對(duì)其發(fā)布的數(shù)據(jù)在社會(huì)網(wǎng)絡(luò)中的數(shù)據(jù)可用性需求等級(jí)。levels=0,1,…,N-1，levelu=0,1,…,N-1，N為自然數(shù)。levels的值越大，表示隱私保護(hù)強(qiáng)度越高；levelu越大，表示社會(huì)網(wǎng)絡(luò)數(shù)據(jù)可用性越高。

Table 2 Explanation of symbols表2 符號(hào)說(shuō)明

定義2（靜態(tài)社會(huì)網(wǎng)絡(luò)Gt）靜態(tài)社會(huì)網(wǎng)絡(luò)特指某一時(shí)刻t狀態(tài)下的社會(huì)網(wǎng)絡(luò)，是一個(gè)有向圖，可用一個(gè)二元組表示，其中：

（1）Vt是t時(shí)刻圖中所有節(jié)點(diǎn)(node)的集合，每個(gè)節(jié)點(diǎn)代表社會(huì)網(wǎng)絡(luò)中的一個(gè)用戶(hù)，即Vt={node}，其中每個(gè)node定義為：

式中，uid表示用戶(hù)唯一id。level表示隱私偏好級(jí)別，是隱私保護(hù)強(qiáng)度等級(jí)levels和社會(huì)網(wǎng)絡(luò)數(shù)據(jù)可用性等級(jí)levelu的函數(shù)，可表示為level=f(levels,levelu)，

其中f為levels與levelu映射到level的函數(shù)。time表示用戶(hù)加入社會(huì)網(wǎng)絡(luò)的時(shí)間。property表示用戶(hù)屬性集合，可表示為property={pi|i=1,2,…,np}，其中pi代表用戶(hù)的一種屬性。

（2）Et是t時(shí)刻圖中所有邊（edge）的集合，即Et={edge}，本文假設(shè)Gt中從nodesrc到nodedest的邊代表nodesrc在社會(huì)網(wǎng)絡(luò)中主動(dòng)產(chǎn)生與nodedest的聯(lián)系，可表示為：

式中，nodesrc表示Gt中關(guān)系的主動(dòng)產(chǎn)生者，nodedest表示Gt中關(guān)系的被動(dòng)接收者。為了敘述方便，可以使用edgeij表示nodei到nodej的連接邊，如在新浪微博中edgeij表示nodei關(guān)注了nodej；Gt、Vt表示t時(shí)刻靜態(tài)社會(huì)網(wǎng)絡(luò)圖Gt中的節(jié)點(diǎn)，同理Gt、Vt表示t時(shí)刻靜態(tài)社會(huì)網(wǎng)絡(luò)圖Gt中的邊，日常生活中使用的社會(huì)網(wǎng)絡(luò)，在某一時(shí)刻數(shù)據(jù)達(dá)到相對(duì)穩(wěn)定狀態(tài)時(shí)，均可視作一個(gè)靜態(tài)社會(huì)網(wǎng)絡(luò)。

定義3（動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)G）動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)是一個(gè)有向圖集合G：

其中，Gt為t時(shí)刻的靜態(tài)社會(huì)網(wǎng)絡(luò)，t為時(shí)間。當(dāng)時(shí)間由t時(shí)刻增加至t+1 時(shí)刻時(shí)，社會(huì)網(wǎng)絡(luò)中可能會(huì)出現(xiàn)節(jié)點(diǎn)和邊數(shù)量的增加或減少，節(jié)點(diǎn)屬性的更新，因此社會(huì)網(wǎng)絡(luò)由當(dāng)前時(shí)刻t的Gt更新為t+1 時(shí)刻的Gt+1，一系列時(shí)間范圍內(nèi)的靜態(tài)社會(huì)網(wǎng)絡(luò)則構(gòu)成了動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)。其中，動(dòng)態(tài)強(qiáng)調(diào)了社會(huì)網(wǎng)絡(luò)的結(jié)構(gòu)（包括節(jié)點(diǎn)和邊）會(huì)隨時(shí)間變化而變化。為了敘述方便，下文中將動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)簡(jiǎn)稱(chēng)為社會(huì)網(wǎng)絡(luò)。日常使用的社會(huì)網(wǎng)絡(luò)均存在數(shù)據(jù)的頻繁更新，實(shí)際上都是動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)。

G中每個(gè)時(shí)刻的靜態(tài)社會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)屬性更新時(shí)，其隱私偏好也可以更新，故每個(gè)時(shí)刻的隱私偏好級(jí)別(node.level)可以不同，支持用戶(hù)個(gè)性化隱私需求。

定義4（匿名動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)G*）匿名動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)G*指動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)G經(jīng)匿名算法處理后的，滿(mǎn)足某些約束條件的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)圖。即，已知一個(gè)動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)G={G0,G1,…,Gt,…,GT},t∈[0,T]，稱(chēng)G*=為G的匿名動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)圖，其中G*t為t時(shí)刻Gt的匿名圖，由變換得到。

定義5（匿名規(guī)則）匿名規(guī)則是隱私保護(hù)方法在進(jìn)行節(jié)點(diǎn)聚類(lèi)時(shí)遵循的規(guī)則。包括5個(gè)規(guī)則，其中Vgj為滿(mǎn)足匿名規(guī)則的節(jié)點(diǎn)集合，稱(chēng)作匿名集。

規(guī)則1（節(jié)點(diǎn)K-匿名規(guī)則）

?Vgi?|Vgi|≥k

規(guī)則2（屬性多樣性規(guī)則）

?Vgi?Diversity(Vgi)≥L

規(guī)則3（時(shí)間一致性規(guī)則）

?v,w∈VT,ifv∈Vgi∧w∈Vgi?

規(guī)則4（關(guān)系約束規(guī)則）

?∈ET,ifv∈Vgi∧w∈Vgi?v=w

規(guī)則5（邊約束規(guī)則）

?Vgi,Vgj,Vgi與Vgj為兩個(gè)匿名集，m為Vgj與Vgj之間邊的數(shù)量，且滿(mǎn)足m≤(|Vgi|×|Vgj|)/k。

這5 個(gè)規(guī)則約束了匿名動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)圖的狀態(tài)以及匿名分組過(guò)程，其中規(guī)則1約束了匿名后的社會(huì)網(wǎng)絡(luò)中，每個(gè)匿名集中的節(jié)點(diǎn)數(shù)量不少于k個(gè)，節(jié)點(diǎn)識(shí)別率不超過(guò)1/k；規(guī)則2 約束了每個(gè)匿名集中的節(jié)點(diǎn)屬性需要滿(mǎn)足L多樣性，其中Diversity(Vgi)表示匿名集中節(jié)點(diǎn)屬性多樣性，抵御同質(zhì)攻擊，其計(jì)算方法見(jiàn)算法1；規(guī)則3 約束了同一個(gè)匿名集中的節(jié)點(diǎn)都是同一時(shí)刻生成的，此規(guī)則確保逆向更新的正確性，避免在逆向更新的過(guò)程中出現(xiàn)節(jié)點(diǎn)缺失的情況；規(guī)則4約束了同一個(gè)匿名集中的節(jié)點(diǎn)不能存在連接邊，因?yàn)榇嬖谶B接的兩個(gè)節(jié)點(diǎn)必然存在某種關(guān)系，他們的隱私信息存在關(guān)聯(lián)，故同一個(gè)匿名集中的節(jié)點(diǎn)應(yīng)減少連接，防止由于分析節(jié)點(diǎn)信息造成的隱私泄露；規(guī)則5從數(shù)學(xué)的角度約束了本文的方法，當(dāng)任意兩個(gè)匿名集內(nèi)的節(jié)點(diǎn)之間的邊數(shù)小于某個(gè)值時(shí)，可保證社會(huì)網(wǎng)絡(luò)圖中每條邊的隱私泄露概率不超過(guò)1/k。綜上所述，經(jīng)過(guò)上述5 條規(guī)則匿名后的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)，在一個(gè)穩(wěn)定的時(shí)刻，其節(jié)點(diǎn)和邊被識(shí)別的概率均不大于1/k。其證明過(guò)程如下：

首先，每個(gè)匿名集中的節(jié)點(diǎn)數(shù)至少為k個(gè)，則每個(gè)節(jié)點(diǎn)被唯一識(shí)別的概率至多為1/k，且同一個(gè)匿名集中的節(jié)點(diǎn)屬性滿(mǎn)足L-多樣性，保障了節(jié)點(diǎn)被識(shí)別的概率不超過(guò)1/k；其次，同一個(gè)匿名集中的節(jié)點(diǎn)不存在連接邊，則邊的起點(diǎn)或終點(diǎn)至少有k個(gè)可能的節(jié)點(diǎn)；接下來(lái)本文定義邊的識(shí)別率EI，代表當(dāng)前社會(huì)網(wǎng)絡(luò)圖中真實(shí)存在的邊占全部可能邊的比重，其計(jì)算公式如下：

EI=|(Vgi×Vgj)?Et|/(|Vgi|×|Vgj|)

令m=|(Vgi×Vgj)?Et|，即Vgi、Vgj之間t時(shí)刻連接邊的數(shù)量，可以得出：

綜上所述，當(dāng)社會(huì)網(wǎng)絡(luò)處于某一確定的時(shí)刻時(shí)，節(jié)點(diǎn)與邊的識(shí)別率均不大于1/k。

定義6（T時(shí)刻匿名圖）T時(shí)刻匿名圖為滿(mǎn)足匿名規(guī)則1～5的二元組，其中：

2.3 主要流程

本文設(shè)計(jì)了基于匿名規(guī)則的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)圖數(shù)據(jù)隱私保護(hù)方法，在數(shù)據(jù)發(fā)布階段對(duì)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行匿名處理，以保護(hù)用戶(hù)隱私。為了抵御關(guān)聯(lián)攻擊，在每次數(shù)據(jù)更新時(shí)，通過(guò)圖的差集對(duì)已發(fā)布的數(shù)據(jù)進(jìn)行逆向更新。

Fig.3 Flow chart of method圖3 方法流程圖

圖3 展示了動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)圖數(shù)據(jù)隱私保護(hù)方法的全部執(zhí)行過(guò)程。首先進(jìn)行個(gè)性化參數(shù)計(jì)算，判斷是否符合匿名條件，若符合匿名條件則進(jìn)行數(shù)據(jù)更新，接收T時(shí)刻的社會(huì)網(wǎng)絡(luò)數(shù)據(jù)。然后根據(jù)屬性?xún)?yōu)先級(jí)進(jìn)行節(jié)點(diǎn)排序，得到一個(gè)有序節(jié)點(diǎn)集合。接下來(lái)根據(jù)本文所定義的匿名規(guī)則進(jìn)行節(jié)點(diǎn)聚類(lèi)，得到若干匿名集，每個(gè)匿名集中包含若干節(jié)點(diǎn)。進(jìn)而計(jì)算T時(shí)刻數(shù)據(jù)連接關(guān)系生成匿名圖。最后根據(jù)不同時(shí)刻圖的差集，逆向更新已發(fā)布的數(shù)據(jù)。具體步驟如下：

步驟1T時(shí)刻接收動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中更新的數(shù)據(jù)，加入到時(shí)間窗口中。

步驟2判斷時(shí)間窗口是否符合時(shí)間窗口大小設(shè)置，若符合，進(jìn)入步驟3；否則返回步驟1。

步驟3判斷時(shí)間窗口內(nèi)的數(shù)據(jù)是否符合匿名閾值大小設(shè)置，若符合，進(jìn)入步驟4；否則返回步驟1。

步驟4對(duì)當(dāng)前社會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)屬性的優(yōu)先級(jí)排序。

步驟5對(duì)當(dāng)前社會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)依據(jù)匿名規(guī)則進(jìn)行節(jié)點(diǎn)聚類(lèi)。

步驟6刪除當(dāng)前時(shí)刻社會(huì)網(wǎng)絡(luò)中不是同一時(shí)刻生成的邊，得到當(dāng)前社會(huì)網(wǎng)絡(luò)的匿名圖。

步驟7對(duì)于t∈[0,T-1]時(shí)刻的社會(huì)網(wǎng)絡(luò)數(shù)據(jù)，刪除與當(dāng)前時(shí)刻不屬于同一時(shí)刻生成的數(shù)據(jù)，進(jìn)行逆向更新。

上述步驟描述了一次完整的包含時(shí)間窗口和匿名閾值的基于匿名規(guī)則的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)圖數(shù)據(jù)隱私保護(hù)方法，下文將進(jìn)行詳細(xì)介紹。

3 動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)圖數(shù)據(jù)隱私保護(hù)方法

3.1 隱私保護(hù)參數(shù)計(jì)算

為了支持用戶(hù)個(gè)性化隱私保護(hù)，本文設(shè)置了兩個(gè)隱私保護(hù)參數(shù)，分別為時(shí)間窗口和匿名閾值。用戶(hù)的隱私偏好經(jīng)函數(shù)計(jì)算得到隱私偏好級(jí)別level，時(shí)間窗口和匿名閾值的取值隨level的變化而變化。

3.1.1 時(shí)間窗口

由于社會(huì)網(wǎng)絡(luò)圖數(shù)據(jù)隱私保護(hù)針對(duì)的是社會(huì)網(wǎng)絡(luò)這個(gè)整體，不能由單一的用戶(hù)作為社會(huì)網(wǎng)絡(luò)隱私保護(hù)級(jí)別的決策者，故本文以網(wǎng)絡(luò)中所有用戶(hù)作為隱私保護(hù)級(jí)別的設(shè)置者。社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)的度反映了用戶(hù)與其他用戶(hù)的關(guān)聯(lián)情況，一個(gè)用戶(hù)的度越大，說(shuō)明其與其他用戶(hù)產(chǎn)生越多的聯(lián)系，若此用戶(hù)的隱私信息泄露，可能會(huì)危及很多用戶(hù)的隱私。故本文使用加權(quán)的方式來(lái)度量社會(huì)網(wǎng)絡(luò)中的平均隱私偏好級(jí)別levelaverage，計(jì)算方法見(jiàn)式（4）。

其中，weighti表示用戶(hù)i的度所占權(quán)重，weighti=表示用戶(hù)i的度，leveli表示由用戶(hù)i的隱私偏好所計(jì)算出來(lái)的隱私偏好級(jí)別。

本文設(shè)置了兩個(gè)隱私保護(hù)參數(shù)。其一為時(shí)間窗口（time window），它代表實(shí)際執(zhí)行圖數(shù)據(jù)更新的時(shí)間間隔。由于圖數(shù)據(jù)是流式更新的，無(wú)法保證數(shù)據(jù)每次更新時(shí)的時(shí)間。然而，每當(dāng)有數(shù)據(jù)更新時(shí)就進(jìn)行圖數(shù)據(jù)匿名對(duì)于數(shù)據(jù)量龐大的社會(huì)網(wǎng)絡(luò)來(lái)說(shuō)是很大的開(kāi)銷(xiāo)，但長(zhǎng)時(shí)間不對(duì)數(shù)據(jù)進(jìn)行處理則會(huì)增大用戶(hù)隱私泄露的風(fēng)險(xiǎn)。故本文使用時(shí)間窗口來(lái)進(jìn)行衡量，由社會(huì)網(wǎng)絡(luò)中的平均隱私偏好級(jí)別確定。其計(jì)算公式見(jiàn)式（5）。其中window表示基礎(chǔ)匿名窗口，單位為秒（s），window=0,1,…,N,N為自然數(shù)。

3.1.2 匿名閾值

匿名閾值（cost threshold）代表當(dāng)前社會(huì)網(wǎng)絡(luò)已更新的數(shù)據(jù)量。由于社會(huì)網(wǎng)絡(luò)數(shù)據(jù)的匿名過(guò)程包含逆向更新過(guò)程，若每當(dāng)社會(huì)網(wǎng)絡(luò)中數(shù)據(jù)有更新時(shí)就進(jìn)行匿名，會(huì)增大網(wǎng)絡(luò)中的時(shí)間開(kāi)銷(xiāo)，但是數(shù)據(jù)大量積累會(huì)造成用戶(hù)隱私泄露。故本文使用匿名閾值來(lái)計(jì)算當(dāng)前網(wǎng)絡(luò)中已更新的數(shù)據(jù)量，若此數(shù)據(jù)量小于閾值，則不進(jìn)行匿名。其計(jì)算公式見(jiàn)式（6）。其中threshold表示基礎(chǔ)匿名閾值，threshold=0,1,…,N,N為自然數(shù)。

至此，本文得到了用于圖數(shù)據(jù)隱私保護(hù)的參數(shù)。

3.2節(jié)點(diǎn)聚類(lèi)

節(jié)點(diǎn)聚類(lèi)是把社會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)聚類(lèi)成若干個(gè)超級(jí)節(jié)點(diǎn)（稱(chēng)作匿名集），每個(gè)超級(jí)節(jié)點(diǎn)至少包括k個(gè)節(jié)點(diǎn)，并對(duì)超級(jí)節(jié)點(diǎn)的屬性進(jìn)行泛化處理，達(dá)到隱私保護(hù)的目的。本文遵循定義5 的匿名規(guī)則進(jìn)行節(jié)點(diǎn)聚類(lèi)，不僅確保節(jié)點(diǎn)和邊的再識(shí)別攻擊概率小于1/k，同時(shí)兼顧節(jié)點(diǎn)的屬性多樣性，抵御同質(zhì)攻擊。

社會(huì)網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都可能存在若干個(gè)屬性property={pi|i=1,2,…,np}，這些屬性可能是敏感信息，導(dǎo)致用戶(hù)隱私泄露，比如用戶(hù)在社會(huì)網(wǎng)絡(luò)所填寫(xiě)的職業(yè)可能推理出其可能的工作單位；其興趣愛(ài)好可能會(huì)反映出他的社交圈。本文對(duì)于用戶(hù)的屬性進(jìn)行K-匿名和L-多樣性保護(hù)，即匿名后的社會(huì)網(wǎng)絡(luò)中，對(duì)于每一個(gè)匿名集中至少有k個(gè)用戶(hù)，且同一個(gè)屬性的取值滿(mǎn)足至少有L個(gè)。然而在實(shí)際的社會(huì)網(wǎng)絡(luò)中，幾乎不可能找到兩個(gè)一模一樣的節(jié)點(diǎn)，因?yàn)橛脩?hù)所填寫(xiě)的屬性信息無(wú)論是內(nèi)容、句式還是結(jié)構(gòu)都會(huì)有區(qū)別，故本文使用SimHash語(yǔ)義指紋[22]來(lái)衡量不同用戶(hù)的屬性之間的相似程度。SimHash 算法的特點(diǎn)是語(yǔ)義指紋包含了文本特征的散列值。相似的文本有相似的散列值，不同于MD5 等加密方式中細(xì)微的差別都會(huì)映射為不同的指紋，相比于MD5 等方式只能排查完全重復(fù)的文本，SimHash的應(yīng)用范圍更廣。

本文將每個(gè)屬性作為一個(gè)token，為其分配權(quán)重后按如下步驟進(jìn)行處理，可以得到文本的語(yǔ)義指紋[23]：

（1）將一個(gè)f維的向量V初始化為0；f位的二進(jìn)制數(shù)S初始化為0。

（2）對(duì)每一個(gè)特征，用傳統(tǒng)的Hash算法對(duì)該特征產(chǎn)生一個(gè)f位的簽名b。對(duì)i=1 到f，如果b的第i位為1，則V的第i個(gè)元素加上該特征的權(quán)重；否則，V的第i個(gè)元素減去該特征的權(quán)重。

（3）如果V的第i個(gè)元素大于0，則S的第i位為1，否則為0。

（4）輸出S作為語(yǔ)義指紋。

文本的語(yǔ)義指紋S均為f位的二進(jìn)制字符串，度量?jī)蓚€(gè)文本之間的相似程度使用的是海明距離。海明距離是兩個(gè)字符串對(duì)應(yīng)位置的不同字符的個(gè)數(shù)。兩個(gè)文本越相似，其海明距離越小。該算法被應(yīng)用于Google 搜索引擎的網(wǎng)頁(yè)相似度檢測(cè)中，指紋長(zhǎng)度為64 bit。由于用戶(hù)在社會(huì)網(wǎng)絡(luò)中填寫(xiě)的屬性信息基本為短文本，其粒度與分詞后的文本基本無(wú)差別，故本文將用戶(hù)在社會(huì)網(wǎng)絡(luò)中所填寫(xiě)的每一個(gè)屬性信息視作一個(gè)特征，進(jìn)行語(yǔ)義指紋的計(jì)算。當(dāng)用戶(hù)的屬性更新后，重新計(jì)算語(yǔ)義指紋。相對(duì)于網(wǎng)頁(yè)中的文本，用戶(hù)屬性的文本數(shù)量會(huì)少很多，因此本文取f=32，使用32 bit 語(yǔ)義指紋進(jìn)行相似度判斷。進(jìn)行節(jié)點(diǎn)聚類(lèi)時(shí)，為了保障每個(gè)匿名集中的節(jié)點(diǎn)具有L-多樣性，本文使用算法1計(jì)算一個(gè)匿名集中的屬性多樣性。

算法1屬性多樣性計(jì)算算法Diversity

算法中的hammingDistance 用于計(jì)算兩個(gè)語(yǔ)義指紋的海明距離。算法的輸入為一個(gè)有序節(jié)點(diǎn)集合Vx，以及判斷兩個(gè)語(yǔ)義指紋是否相似的距離閾值minDis，針對(duì)每一個(gè)節(jié)點(diǎn)集合，若存在任意兩個(gè)節(jié)點(diǎn)的語(yǔ)義距離大于閾值，則認(rèn)為增加了集合中的多樣性。算法的時(shí)間復(fù)雜度為O(n2),n為集合Vx的大小。

3.3 連接關(guān)系計(jì)算

節(jié)點(diǎn)聚類(lèi)后生成了一系列匿名集，匿名集中包含若干節(jié)點(diǎn)，本節(jié)將介紹邊的連接規(guī)則，將匿名集中的節(jié)點(diǎn)進(jìn)行連接，生成匿名圖。

邊連接規(guī)則：

規(guī)則1生成連接邊集合

規(guī)則2若存在node.degree=0，生成連接邊

上述邊連接規(guī)則描述了如何用匿名集中的節(jié)點(diǎn)生成邊構(gòu)成匿名圖。規(guī)則1 描述了圖中的真實(shí)節(jié)點(diǎn)的邊的生成規(guī)則，對(duì)于一個(gè)真實(shí)節(jié)點(diǎn)在候選補(bǔ)圖的邊集中篩選出所有與它相連的邊，即以node為起始節(jié)點(diǎn)或終止節(jié)點(diǎn)的連接邊。規(guī)則2 描述了圖中噪音節(jié)點(diǎn)的邊的生成規(guī)則，對(duì)于一個(gè)噪音節(jié)點(diǎn)，若存在與不在同一個(gè)匿名集中的噪音節(jié)點(diǎn)，且該節(jié)點(diǎn)的度為0，即未與其他節(jié)點(diǎn)產(chǎn)生連接關(guān)系，則構(gòu)造一條以為起始節(jié)點(diǎn)，為終止節(jié)點(diǎn)的連接邊。

圖4中展示了兩個(gè)匿名集，匿名集1中所有節(jié)點(diǎn)的tag均為{1,3}，其中1號(hào)為真實(shí)節(jié)點(diǎn)，3號(hào)為噪音節(jié)點(diǎn)。同理，匿名集2 中所有節(jié)點(diǎn)的tag均為{2,4}，其中2號(hào)為真實(shí)節(jié)點(diǎn)，4號(hào)為噪音節(jié)點(diǎn)。圖中所示，真實(shí)節(jié)點(diǎn)只能與和其具有原始連接關(guān)系的真實(shí)節(jié)點(diǎn)相連接，而噪音節(jié)點(diǎn)只能與和其不在同一個(gè)匿名集中且符合度數(shù)要求的噪音節(jié)點(diǎn)相連接。

Fig.4 Diagram of connection rules圖4 邊連接規(guī)則示意圖

3.4 匿名圖生成與逆向更新

對(duì)于T時(shí)刻的社會(huì)網(wǎng)絡(luò)圖GT，候選補(bǔ)圖和邊連接規(guī)則生成匿名圖與基于圖的差集進(jìn)行逆向更新的方法見(jiàn)算法2。

算法2匿名圖生成與逆向更新算法

輸入：G={G0,G1,…,Gt,…,GT-1},UpdateGraph,ksets,k。

4 實(shí)驗(yàn)及效果評(píng)估

4.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)收集了新浪微博169 246 個(gè)用戶(hù)的屬性數(shù)據(jù)和4 485 488條關(guān)注關(guān)系。為了模擬社會(huì)網(wǎng)絡(luò)的動(dòng)態(tài)更新過(guò)程，本文通過(guò)隨機(jī)增刪的方式，模擬社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)、邊的增刪過(guò)程，并進(jìn)行多次迭代；除此之外，還獲取了SNAP公開(kāi)的歐洲某研究中心986個(gè)用戶(hù)的332 334 條郵件往來(lái)信息（https://snap.stanford.edu/data/email-Eu-core.html），包含郵件收發(fā)的相對(duì)時(shí)間，可直接用來(lái)更新動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)。

4.1.1 社會(huì)網(wǎng)絡(luò)用戶(hù)關(guān)注關(guān)系網(wǎng)絡(luò)分析

為了評(píng)價(jià)隱私保護(hù)方法的數(shù)據(jù)安全性與可用性，本文采集了2009 年8 月至2012 年10 月期間的新浪微博169 246 個(gè)用戶(hù)的2 031 393 條屬性數(shù)據(jù)和4 485 488條關(guān)注關(guān)系數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。

為了更加真實(shí)地模擬社會(huì)網(wǎng)絡(luò)數(shù)據(jù)動(dòng)態(tài)更新的過(guò)程，結(jié)合《中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》（第27次至39 次）發(fā)布的2011 年1 月至2017 年1 月期間的新浪微博用戶(hù)量的真實(shí)變化趨勢(shì)，擬合了圖5所示的用戶(hù)量隨時(shí)間變化的數(shù)據(jù)曲線(xiàn)。其含義為12個(gè)月內(nèi)新浪微博用戶(hù)量隨時(shí)間變化的趨勢(shì)，其中圖5（a）約涉及1 600名用戶(hù)，圖5（b）約涉及10 000名用戶(hù)。為了模擬準(zhǔn)確，使用了6 次方程進(jìn)行擬合，其公式分別為y1=-0.037 3x6+1.582 9x5-25.813x4+208.14x3-913.48x2+2 266.9x-1 218.1,（如圖5（a）所示）；y2=-0.224 1x6+9.497 1x5-154.88x4+1 248.8x3-5 480.9x2+13 601x-7 308.9,（如圖5（b）所示）。

Fig.5 Changes in user quantity over time圖5 用戶(hù)量隨時(shí)間變化曲線(xiàn)

本實(shí)驗(yàn)中將進(jìn)行12 次迭代，即x=1,2,…,12，得到社會(huì)網(wǎng)絡(luò)中用戶(hù)總數(shù)，每次迭代的過(guò)程中，隨機(jī)刪除部分節(jié)點(diǎn)及與其相連的邊，再隨機(jī)增加節(jié)點(diǎn)與邊，達(dá)到擬合曲線(xiàn)的標(biāo)準(zhǔn)。為了能夠充分利用社會(huì)網(wǎng)絡(luò)中的關(guān)系數(shù)據(jù)，采用廣度優(yōu)先搜索的方式，首先選取一個(gè)種子節(jié)點(diǎn)，然后搜索與此種子節(jié)點(diǎn)相連的節(jié)點(diǎn)，依次加入到實(shí)驗(yàn)集合中，接下來(lái)進(jìn)行第2輪廣度優(yōu)先搜索，直到實(shí)驗(yàn)集合中的節(jié)點(diǎn)個(gè)數(shù)滿(mǎn)足上述公式，最后執(zhí)行匿名算法，對(duì)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行保護(hù)后發(fā)布。本實(shí)驗(yàn)將會(huì)記錄x=1時(shí)刻的原始社會(huì)網(wǎng)絡(luò)，記為G0，在每次迭代并逆向更新之后記錄，共可以得到12個(gè)

4.1.2 社會(huì)網(wǎng)絡(luò)郵件收發(fā)關(guān)系網(wǎng)絡(luò)分析

新浪微博數(shù)據(jù)雖然屬于典型的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)，但未記錄用戶(hù)在社會(huì)網(wǎng)絡(luò)中行為數(shù)據(jù)（更新上述屬性）的時(shí)間信息。為了驗(yàn)證本文方法適用于動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中數(shù)據(jù)真實(shí)的更新情況，選取了由SNAP所提供的歐洲某研究機(jī)構(gòu)由2003 年10 月至2005 年5 月（共18 個(gè)月）期間的郵件往來(lái)數(shù)據(jù)，共986 個(gè)用戶(hù)的332 334條郵件往來(lái)信息。每條數(shù)據(jù)包含一個(gè)時(shí)間戳，其含義為距相對(duì)起點(diǎn)（時(shí)間戳為0）間隔的秒數(shù)，可以按照時(shí)間戳信息還原郵件網(wǎng)絡(luò)的動(dòng)態(tài)更新過(guò)程。

本文對(duì)郵件數(shù)據(jù)度-用戶(hù)數(shù)進(jìn)行了統(tǒng)計(jì)，結(jié)果如圖6所示。其中度數(shù)最小值為1，最大值為10 571，平均度數(shù)為337。度的取值共604 種情況，平均每種情況約有1.6個(gè)用戶(hù)。此數(shù)據(jù)集中，用戶(hù)數(shù)隨度數(shù)的增加迅速減少直至趨于平緩，其分布基本符合冪律分布。

Fig.6 User quantity-degree statistics of email data set圖6 郵件數(shù)據(jù)集度-用戶(hù)數(shù)統(tǒng)計(jì)

由于此數(shù)據(jù)集中包含時(shí)間戳，為了更好地還原動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)更新的過(guò)程，本文對(duì)時(shí)間戳信息進(jìn)行了統(tǒng)計(jì)，時(shí)間戳的相對(duì)起點(diǎn)為0，每隔1 s增加一個(gè)時(shí)間單位，相對(duì)終點(diǎn)為45 405 138，郵件發(fā)送的最小時(shí)間間隔為0 s，最大時(shí)間間隔為58 s，平均間隔為0.625 s。圖7展示了郵件發(fā)送的時(shí)間間隔統(tǒng)計(jì)情況，可以分析出，時(shí)間間隔-郵件數(shù)分布同樣符合冪律分布。

Fig.7 Time interval-email quantity statistics圖7 時(shí)間間隔-郵件數(shù)統(tǒng)計(jì)

4.2 評(píng)價(jià)指標(biāo)

本文將從數(shù)據(jù)安全性和數(shù)據(jù)可用性?xún)煞矫嬖u(píng)價(jià)算法的有效性，評(píng)價(jià)指標(biāo)見(jiàn)表3。

4.3 結(jié)果分析

理論上，根據(jù)K匿名算法的性質(zhì)，k值越大，匿名性越好，安全性越高；數(shù)據(jù)發(fā)布時(shí)間點(diǎn)越密集，間隔越短，圖更新的速度越快，可以執(zhí)行更多次的匿名方法，匿名性也越好；網(wǎng)絡(luò)中節(jié)點(diǎn)與邊的數(shù)量也會(huì)影響匿名性。當(dāng)節(jié)點(diǎn)數(shù)量和邊增加時(shí)，需要更大的k值進(jìn)行保護(hù)。在節(jié)點(diǎn)數(shù)量不夠，數(shù)據(jù)發(fā)布時(shí)間間隔較長(zhǎng)的情況下，本文算法會(huì)通過(guò)增加隨機(jī)節(jié)點(diǎn)的方式保證匿名性，具體的匿名程度和算法中選取的k值有關(guān)。

4.3.1 社會(huì)網(wǎng)絡(luò)用戶(hù)關(guān)注關(guān)系網(wǎng)絡(luò)分析

本文使用新浪微博的用戶(hù)屬性數(shù)據(jù)進(jìn)行模擬實(shí)驗(yàn)，將每個(gè)用戶(hù)視作社會(huì)網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)，用戶(hù)間的關(guān)注關(guān)系視作社會(huì)網(wǎng)絡(luò)中的有向邊，起點(diǎn)為關(guān)注者，終點(diǎn)為被關(guān)注者。每個(gè)用戶(hù)選取節(jié)點(diǎn)id為用戶(hù)的唯一標(biāo)識(shí)，除此之外選取5個(gè)用戶(hù)屬性作為節(jié)點(diǎn)排序的依據(jù)，分別為性別、所在地區(qū)、描述、用戶(hù)標(biāo)簽和教育信息。

由于新浪微博數(shù)據(jù)集中不存在用戶(hù)更新屬性信息、用戶(hù)關(guān)注關(guān)系的具體時(shí)間，本文采用模擬的方式，將全部數(shù)據(jù)集視作全集。在數(shù)據(jù)更新的過(guò)程中，第1次數(shù)據(jù)更新時(shí)，隨機(jī)選取M個(gè)節(jié)點(diǎn)及其之間的連接關(guān)系作為原始社會(huì)網(wǎng)絡(luò)，稱(chēng)這個(gè)過(guò)程為初始化。在之后的每次數(shù)據(jù)更新過(guò)程中，隨機(jī)去掉N個(gè)節(jié)點(diǎn)以及與這些節(jié)點(diǎn)相關(guān)的邊，并從全集中隨機(jī)增加P個(gè)節(jié)點(diǎn)，以及相關(guān)的邊，得到一次更新后的數(shù)據(jù)。其中M、N、P為合法的隨機(jī)數(shù)即N≤M，其余參數(shù)無(wú)約束條件。

（1）數(shù)據(jù)安全性

為了衡量不同隱私保護(hù)參數(shù)下的隱私保護(hù)效果，將對(duì)200個(gè)節(jié)點(diǎn)的社會(huì)網(wǎng)絡(luò)進(jìn)行匿名，計(jì)算k值為3～10 時(shí)的匿名率，通過(guò)匿名率來(lái)判斷數(shù)據(jù)安全性。如圖8所示，隨著k值的增加，匿名率呈現(xiàn)增長(zhǎng)趨勢(shì)。可知隨著k值的增大，數(shù)據(jù)的安全性逐漸增大，當(dāng)k=10時(shí)，匿名率約為26%。

為了驗(yàn)證本文算法的屬性多樣性的設(shè)置效果，分別在使用與不使用屬性多樣性的條件下進(jìn)行了實(shí)驗(yàn)，對(duì)比屬性多樣性在算法中的作用。本文設(shè)置當(dāng)兩個(gè)節(jié)點(diǎn)的屬性語(yǔ)義指紋距離小于H時(shí)，認(rèn)為它們?yōu)橄嗨频模粫?huì)增加多樣性，執(zhí)行匿名算法后，統(tǒng)計(jì)每個(gè)匿名集中語(yǔ)義指紋的多樣性，實(shí)驗(yàn)結(jié)果如圖9 所示。其中，H=5，選取100個(gè)節(jié)點(diǎn)及其相關(guān)的邊，k值取10，不設(shè)置L值，算法結(jié)束后未增加噪音節(jié)點(diǎn)，故產(chǎn)生的多樣性均為節(jié)點(diǎn)的真實(shí)屬性匿名后的結(jié)果。

Table 3 Evaluation indexes表3 評(píng)價(jià)指標(biāo)

Fig.8 Anonymity rate statistics of Sina Weibo data set圖8 新浪微博數(shù)據(jù)集匿名率統(tǒng)計(jì)

Fig.9 Semantic fingerprint and diversity result圖9 語(yǔ)義指紋與多樣性結(jié)果

由圖9可知，從多樣性、海明距離兩個(gè)指標(biāo)來(lái)看，含語(yǔ)義指紋計(jì)算出的匿名方法基本優(yōu)于不含語(yǔ)義指紋的情況。其中平均海明距離為同一個(gè)匿名集中的節(jié)點(diǎn)屬性?xún)蓛芍g的距離平均值，最大最小距離雖有一定的偶然性，但使用語(yǔ)義指紋的方法效果普遍更好。多樣性方面，通過(guò)語(yǔ)義指紋的設(shè)置，提高了同一個(gè)匿名集中屬性的多樣性。

除此之外，本文測(cè)試了數(shù)據(jù)安全性與迭代次數(shù)的關(guān)系，使用新浪微博數(shù)據(jù)進(jìn)行兩組實(shí)驗(yàn)，分別進(jìn)行12輪迭代，并使用聚集系數(shù)、中介中心性作為衡量指標(biāo)，分別記錄了測(cè)量值與匿名前后的變化率。結(jié)果如圖10 所示，圖10（a）展示了原始圖與經(jīng)過(guò)12 次迭代的匿名圖的聚集系數(shù)和中心中介性變化率統(tǒng)計(jì)結(jié)果，兩項(xiàng)指標(biāo)隨著圖數(shù)據(jù)的迭代而變化。隨著迭代次數(shù)的增加，聚集系數(shù)變化率和中介中心性變化率均呈現(xiàn)上升趨勢(shì)，說(shuō)明數(shù)據(jù)安全性與迭代次數(shù)呈正相關(guān)關(guān)系，進(jìn)一步說(shuō)明本文所述方法在圖數(shù)據(jù)匿名后可以在圖結(jié)構(gòu)上產(chǎn)生差異性，保護(hù)原始圖結(jié)構(gòu)。圖10（b）展示的是10 000名用戶(hù)的模擬實(shí)驗(yàn)結(jié)果，本文方法對(duì)于大數(shù)據(jù)集同樣可以進(jìn)行擾動(dòng)，保護(hù)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)隱私。但由于數(shù)據(jù)量大，在變化數(shù)量相對(duì)穩(wěn)定的情況下，變化率結(jié)果略低于小數(shù)據(jù)集實(shí)驗(yàn)。

Fig.10 Data security of Sina Weibo data set圖10 新浪微博數(shù)據(jù)集安全性

（2）數(shù)據(jù)可用性

按照4.1 節(jié)中的模擬方法，本文使用新浪微博數(shù)據(jù)集進(jìn)行兩組實(shí)驗(yàn)，分別進(jìn)行12輪迭代，以接近中心性、harmonic 中心性、平均路徑長(zhǎng)度和離心率等指標(biāo)測(cè)試數(shù)據(jù)可用性。

圖11（a）至圖11（d）分別展示了兩組數(shù)據(jù)的原始社會(huì)網(wǎng)絡(luò)圖與經(jīng)過(guò)12 次更新及匿名后的評(píng)價(jià)指標(biāo)。由圖11（a）與圖11（c）可知，兩組數(shù)據(jù)經(jīng)匿名后，四種衡量指標(biāo)均呈現(xiàn)波動(dòng)性變化，對(duì)原始圖數(shù)據(jù)產(chǎn)生了擾動(dòng)。由圖11（b）與圖11（d）可知，兩組數(shù)據(jù)匿名后的四種變化率除平均路徑長(zhǎng)度外，不超過(guò)15%，從圖中節(jié)點(diǎn)間距離的角度來(lái)衡量，保持了數(shù)據(jù)可用性。與前文所述類(lèi)似，由于相同的變化量在小數(shù)據(jù)中產(chǎn)生的變化率更大，故小數(shù)據(jù)集實(shí)驗(yàn)的變化率略高于大數(shù)據(jù)集。

4.3.2 郵件收發(fā)關(guān)系網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果分析

社會(huì)網(wǎng)絡(luò)是一個(gè)動(dòng)態(tài)網(wǎng)絡(luò)，數(shù)據(jù)的更新迭代的時(shí)間不可控，它由用戶(hù)參與社會(huì)網(wǎng)絡(luò)的時(shí)間、頻率和動(dòng)作決定。僅僅通過(guò)模擬動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)生成的方式是不能夠完全展現(xiàn)其更新迭代過(guò)程的，也不能驗(yàn)證算法的有效性。故本文使用歐洲某研究機(jī)構(gòu)的郵件往來(lái)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，按照郵件的收發(fā)時(shí)間進(jìn)行社會(huì)網(wǎng)絡(luò)的動(dòng)態(tài)更新，體現(xiàn)時(shí)間窗口、匿名閾值的作用與算法的實(shí)用價(jià)值。

（1）數(shù)據(jù)安全性

通過(guò)統(tǒng)計(jì)k值為3～10 時(shí)的匿名率來(lái)衡量數(shù)據(jù)的安全性。如圖12 所示，匿名率隨著k值的增大而增大，社會(huì)網(wǎng)絡(luò)數(shù)據(jù)的安全性逐漸增大。

本實(shí)驗(yàn)從數(shù)據(jù)集中按照時(shí)間順序進(jìn)行圖數(shù)據(jù)的動(dòng)態(tài)更新，參數(shù)設(shè)置為：時(shí)間窗口為86 400 s，匿名閾值為0，即對(duì)于每一輪數(shù)據(jù)更新都進(jìn)行匿名，進(jìn)行10次迭代。對(duì)比匿名后的圖數(shù)據(jù)與網(wǎng)絡(luò)初始化時(shí)的圖數(shù)據(jù)結(jié)構(gòu)的差異性，使用聚集系數(shù)、中介中心性及它們的變化率來(lái)衡量圖結(jié)構(gòu)的變化。

由圖13（a）可知，本文方法可以對(duì)真實(shí)數(shù)據(jù)集進(jìn)行圖數(shù)據(jù)匿名，在不同的迭代中產(chǎn)生不同的匿名效果。圖13（b）中的變化率顯示，當(dāng)?shù)螖?shù)為10 時(shí)，聚集系數(shù)與中介中心性的變化率分別約為40%和60%，對(duì)原始數(shù)據(jù)產(chǎn)生了擾動(dòng)。且隨著迭代次數(shù)的增加，變化率逐漸增大。

（2）數(shù)據(jù)可用性

為了驗(yàn)證本文方法在真實(shí)的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)隱私保護(hù)中依然有效，與之前實(shí)驗(yàn)類(lèi)似，使用接近中心性、harmonic 中心性、平均路徑長(zhǎng)度和離心率等指標(biāo)進(jìn)行方法驗(yàn)證。本實(shí)驗(yàn)從數(shù)據(jù)集中按照時(shí)間順序進(jìn)行圖數(shù)據(jù)的動(dòng)態(tài)更新，參數(shù)設(shè)置為：時(shí)間窗口為86 400 s，匿名閾值為0，即對(duì)于每一輪數(shù)據(jù)更新都進(jìn)行匿名，進(jìn)行10 次迭代。對(duì)比匿名后的圖數(shù)據(jù)與網(wǎng)絡(luò)初始化時(shí)的圖數(shù)據(jù)的差異性，結(jié)果如圖14所示。

圖14（a）中接近中心性、harmonic中心性、離心率和平均路徑長(zhǎng)度這4 項(xiàng)指標(biāo)在數(shù)據(jù)迭代的過(guò)程中均有不同程度的變化，說(shuō)明本文方法在真實(shí)數(shù)據(jù)集中也可產(chǎn)生效果。圖14（b）中的變化率指標(biāo)表明，隨著數(shù)據(jù)的更新，除平均路徑長(zhǎng)度外，各項(xiàng)指標(biāo)的變化率均在10%以?xún)?nèi)，保持了較好的數(shù)據(jù)可用性。平均路徑長(zhǎng)度由于圖結(jié)構(gòu)的變化，產(chǎn)生了相對(duì)較大的變化。

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

目前，社會(huì)網(wǎng)絡(luò)中用戶(hù)個(gè)性化隱私保護(hù)主要針對(duì)單實(shí)例發(fā)布的靜態(tài)網(wǎng)絡(luò)，不能適應(yīng)具有高度動(dòng)態(tài)性的社會(huì)網(wǎng)絡(luò)的更新迭代過(guò)程，不能保證社會(huì)網(wǎng)絡(luò)的隱私安全。本文開(kāi)展了動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)發(fā)布個(gè)性化隱私保護(hù)研究，提出基于匿名規(guī)則的圖數(shù)據(jù)隱私保護(hù)方法。使用新浪微博數(shù)據(jù)和公開(kāi)數(shù)據(jù)集驗(yàn)證，實(shí)驗(yàn)結(jié)果表明本文方法兼顧了用戶(hù)數(shù)據(jù)隱私保護(hù)和數(shù)據(jù)可用性的個(gè)性化需求。

Fig.13 Data security of email data set圖13 郵件數(shù)據(jù)集數(shù)據(jù)安全性

Fig.14 Data availability of email data set圖14 郵件數(shù)據(jù)集數(shù)據(jù)可用性

未來(lái)研究工作將基于多維度用戶(hù)隱私保護(hù)方法開(kāi)展深入研究，構(gòu)建多特征的聯(lián)合匿名保護(hù)方案，構(gòu)建隱私保護(hù)方案安全評(píng)價(jià)體系，為用戶(hù)提供更加可靠的社會(huì)網(wǎng)絡(luò)環(huán)境。