融合社團(tuán)劃分的社交網(wǎng)絡(luò)分級(jí)隱私保護(hù)算法*

陸 越，陳秀真,2，馬 進(jìn),2

0 引 言

近年來(lái)，隨著互聯(lián)網(wǎng)技術(shù)和無(wú)線(xiàn)通信技術(shù)的發(fā)展，在線(xiàn)社交日益成為人們分享和傳遞信息、維護(hù)和拓展社會(huì)關(guān)系的重要方式。大量具有不同功能、針對(duì)不同用戶(hù)群體的各類(lèi)社交平臺(tái)飛速發(fā)展，如Facebook、Twitter、新浪微博等平臺(tái)，積累了上億的注冊(cè)用戶(hù)[1-2]。社交網(wǎng)絡(luò)是真實(shí)社會(huì)的寫(xiě)照，包含了龐大的用戶(hù)群體和他們之間復(fù)雜的社會(huì)關(guān)系。大量用戶(hù)數(shù)據(jù)如用戶(hù)姓名、性別、年齡、婚姻情況、電子郵箱等資料在社交網(wǎng)絡(luò)中發(fā)布和傳播。出于數(shù)據(jù)共享和學(xué)術(shù)研究的目的，需要收集和發(fā)布社交網(wǎng)絡(luò)中的數(shù)據(jù)。這些信息可能涉及用戶(hù)的敏感、私密信息，而敏感信息的泄露會(huì)給當(dāng)事人帶來(lái)諸多麻煩，甚至造成經(jīng)濟(jì)損失、人身攻擊等。

社交網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)可能會(huì)被監(jiān)聽(tīng)和盜用，惡意攻擊者可以通過(guò)欺詐、釣魚(yú)網(wǎng)站、主動(dòng)攻擊、被動(dòng)攻擊及背景知識(shí)攻擊獲取用戶(hù)隱私信息。其中，主動(dòng)攻擊是指攻擊者在收集社交網(wǎng)絡(luò)數(shù)據(jù)時(shí)主動(dòng)對(duì)目標(biāo)進(jìn)行標(biāo)識(shí)，通過(guò)在發(fā)布圖中重識(shí)別這些標(biāo)識(shí)，從而攻擊與之相關(guān)聯(lián)的用戶(hù)。被動(dòng)攻擊指攻擊者對(duì)發(fā)布后的網(wǎng)絡(luò)中的目標(biāo)節(jié)點(diǎn)進(jìn)行攻擊，主要基于邊修改方法[3]和基于聚類(lèi)方法[4-5]。由于主動(dòng)攻擊和被動(dòng)攻擊都要求攻擊者向社會(huì)網(wǎng)絡(luò)中添加節(jié)點(diǎn)或信息，通過(guò)在發(fā)布圖中重識(shí)別實(shí)現(xiàn)攻擊，實(shí)際操作中難度較大，攻擊者更常利用擁有的關(guān)于目標(biāo)個(gè)體的背景知識(shí)（如節(jié)點(diǎn)的度、標(biāo)識(shí)屬性、節(jié)點(diǎn)間的連接關(guān)系、鄰域和嵌入子圖等）來(lái)推斷個(gè)體隱私信息。由于節(jié)點(diǎn)的度及標(biāo)識(shí)屬性比較容易獲取，現(xiàn)有研究大多基于這兩種背景知識(shí)信息展開(kāi)。

因此，在社交網(wǎng)絡(luò)數(shù)據(jù)發(fā)布時(shí)，需要在確保數(shù)據(jù)可用性的前提下，保護(hù)節(jié)點(diǎn)隱私信息。對(duì)于傳統(tǒng)關(guān)系型數(shù)據(jù)的隱私保護(hù)，目前已有很多較為成熟的隱私模型，如k-anonymity[6]、l-diversity[7]以及t-closeness[8]等。傳統(tǒng)關(guān)系型數(shù)據(jù)的研究對(duì)象主要是表數(shù)據(jù)，而社交網(wǎng)絡(luò)中的數(shù)據(jù)不僅包含用戶(hù)的個(gè)人信息，也包含用戶(hù)間復(fù)雜的社會(huì)關(guān)系，需要用圖結(jié)構(gòu)模型進(jìn)行描述。圖中的節(jié)點(diǎn)代表社交網(wǎng)絡(luò)中的個(gè)體，圖中的邊代表個(gè)體間的關(guān)聯(lián)[9]。借鑒傳統(tǒng)關(guān)系型數(shù)據(jù)的隱私保護(hù)方法，研究人員提出了一系列社交網(wǎng)絡(luò)發(fā)布數(shù)據(jù)的隱私保護(hù)方法。在攻擊者擁有節(jié)點(diǎn)度的背景知識(shí)下，Liu等人[10]提出了k-degree匿名方法，即對(duì)發(fā)布圖中任意一個(gè)節(jié)點(diǎn)V，與V擁有相同度的節(jié)點(diǎn)至少有k-1個(gè)。Yuan等人[11]提出了k-degree-l-diversity匿名方法，用于保護(hù)個(gè)體的敏感屬性。Ying等人[12]提出用隨機(jī)化的方法實(shí)現(xiàn)關(guān)系隱藏，即通過(guò)隨機(jī)刪除與添加m條邊來(lái)修改原圖。Zhou等人[13]提出了k-neighborhood匿名模型，即對(duì)于發(fā)布圖中任意一個(gè)節(jié)點(diǎn)V，與V擁有相似的鄰域的節(jié)點(diǎn)至少有k-1個(gè)。為了保護(hù)節(jié)點(diǎn)的敏感屬性，Zhou等人[14]將k-neighborhood匿名模型擴(kuò)展為k-neighborhood-l-diversity匿名模型。

然而，上述社交網(wǎng)絡(luò)隱私保護(hù)方法，對(duì)于所有個(gè)體的信息采用統(tǒng)一的隱私保護(hù)標(biāo)準(zhǔn)，并未考慮處于社交網(wǎng)絡(luò)不同結(jié)構(gòu)特征中的節(jié)點(diǎn)有不同的隱私保護(hù)等級(jí)需求。無(wú)差別的隱私保護(hù)會(huì)對(duì)某些用戶(hù)過(guò)度保護(hù)，降低發(fā)布數(shù)據(jù)的可用性，增加算法的復(fù)雜度。為此，針對(duì)目前社交網(wǎng)絡(luò)匿名算法信息損失度大、數(shù)據(jù)可用性低以及隱私保護(hù)等級(jí)無(wú)差別等問(wèn)題，提出了一種基于社團(tuán)劃分的社交網(wǎng)絡(luò)分級(jí)隱私保護(hù)算法，用于發(fā)掘社交網(wǎng)絡(luò)結(jié)構(gòu)和滿(mǎn)足分級(jí)的隱私保護(hù)需求。

1 系統(tǒng)模型

社交網(wǎng)絡(luò)中普遍存在社團(tuán)結(jié)構(gòu)，同一社團(tuán)內(nèi)節(jié)點(diǎn)間的關(guān)聯(lián)更為緊密，且社團(tuán)中的局部核心節(jié)點(diǎn)信息保密性要求更高。因此，本文設(shè)計(jì)了一種基于社團(tuán)劃分的社交網(wǎng)絡(luò)分級(jí)隱私保護(hù)模型，實(shí)現(xiàn)對(duì)背景知識(shí)攻擊的有效防護(hù)，同時(shí)滿(mǎn)足個(gè)性化的隱私保護(hù)需求。

模型采用圖結(jié)構(gòu)模型描述社交網(wǎng)絡(luò)數(shù)據(jù)中包含的用戶(hù)個(gè)人信息和用戶(hù)間復(fù)雜的社會(huì)關(guān)系，圖中節(jié)點(diǎn)代表社交網(wǎng)絡(luò)中的個(gè)體，邊代表個(gè)體間的關(guān)聯(lián)。模型的核心思想是將社團(tuán)劃分引入隱私保護(hù)，識(shí)別局部核心節(jié)點(diǎn)，并對(duì)其進(jìn)行強(qiáng)力度的隱私保護(hù)。首先，提出融合節(jié)點(diǎn)影響力因素的標(biāo)簽傳播算法進(jìn)行社團(tuán)劃分，綜合評(píng)估節(jié)點(diǎn)的影響力并計(jì)算每個(gè)節(jié)點(diǎn)的權(quán)重值，按照節(jié)點(diǎn)影響力由高到低的順序異步更新標(biāo)簽。迭代更新完畢后，局部核心節(jié)點(diǎn)擁有較高權(quán)重值、標(biāo)簽相同的節(jié)點(diǎn)被劃分入一個(gè)社團(tuán)。其次，針對(duì)挖掘的社團(tuán)結(jié)構(gòu)，將網(wǎng)絡(luò)節(jié)點(diǎn)的隱私保護(hù)等級(jí)分為H、M、L 3種。對(duì)于網(wǎng)絡(luò)隱私保護(hù)等級(jí)為H的節(jié)點(diǎn)采用(k,l,θ1,θ2)匿名方法，對(duì)于隱私保護(hù)等級(jí)為M的節(jié)點(diǎn)采用k-degree-l-diversity匿名方法，對(duì)于隱私保護(hù)等級(jí)為L(zhǎng)的節(jié)點(diǎn)采用k-degree匿名方法。系統(tǒng)模型如圖1所示。

圖1 系統(tǒng)模型

社交網(wǎng)絡(luò)分級(jí)隱私保護(hù)算法涉及融合影響力因素的社團(tuán)劃分算法和基于社團(tuán)劃分的隱私保護(hù)算法，下面將分步驟介紹。

2 融合影響力因素的社團(tuán)劃分

社團(tuán)劃分即挖掘社交網(wǎng)結(jié)構(gòu)特性，發(fā)現(xiàn)個(gè)體之間的關(guān)聯(lián)，將存在密切聯(lián)系和頻繁互動(dòng)的個(gè)體集合聚為一個(gè)社區(qū)，且同一社團(tuán)內(nèi)部節(jié)點(diǎn)之間的關(guān)聯(lián)程度較強(qiáng)，不同社團(tuán)之間的關(guān)聯(lián)程度相對(duì)較弱。廣泛應(yīng)用于復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分的標(biāo)簽傳播（Label Propagation）算法，具有復(fù)雜度低、劃分效率高的特點(diǎn)，但傳統(tǒng)的標(biāo)簽傳播算法存在不穩(wěn)定問(wèn)題，在節(jié)點(diǎn)進(jìn)行初次標(biāo)簽更新時(shí)，所有標(biāo)簽數(shù)值都為1，節(jié)點(diǎn)在鄰居節(jié)點(diǎn)標(biāo)簽值中進(jìn)行隨機(jī)選擇。這一過(guò)程中，僅將標(biāo)簽數(shù)量作為選擇指標(biāo)，忽略了鄰居節(jié)點(diǎn)影響力的差別，且在最大標(biāo)簽值存在多個(gè)時(shí)，節(jié)點(diǎn)選擇鄰居節(jié)點(diǎn)標(biāo)簽值時(shí)具有隨機(jī)性，而這種隨機(jī)選擇將會(huì)影響標(biāo)簽傳播的效率，且會(huì)影響社區(qū)劃分的準(zhǔn)確性。研究人員提出，根據(jù)節(jié)點(diǎn)的度、聚集系數(shù)等特征參數(shù)進(jìn)行排序[15-17]，確定標(biāo)簽更新順序。但是，這些指標(biāo)通常只考慮了節(jié)點(diǎn)自身的某一種特性，沒(méi)有考慮節(jié)點(diǎn)間的鏈接關(guān)系。本文綜合考慮節(jié)點(diǎn)自身特性和全局特性，提出融合節(jié)點(diǎn)影響力因素的社團(tuán)劃分方法，利用節(jié)點(diǎn)權(quán)重，綜合評(píng)估節(jié)點(diǎn)影響力，使得影響力較大節(jié)點(diǎn)的標(biāo)簽?zāi)軌騼?yōu)先傳播。下面首先給出節(jié)點(diǎn)權(quán)重的計(jì)算方法，然后給出算法步驟。

2.1 節(jié)點(diǎn)權(quán)重計(jì)算

綜合考慮節(jié)點(diǎn)的自身特性與全局特性計(jì)算節(jié)點(diǎn)權(quán)重。節(jié)點(diǎn)權(quán)重與其自身影響力和對(duì)其他節(jié)點(diǎn)的影響力正相關(guān)，因此節(jié)點(diǎn)的標(biāo)簽權(quán)重I可以表示為：

其中，I0表示節(jié)點(diǎn)的基礎(chǔ)權(quán)重，I1表示節(jié)點(diǎn)的自身影響力，I2表示節(jié)點(diǎn)的全局影響力，其具體含義及計(jì)算方法如下。

部分社團(tuán)可能不存在顯著的核心節(jié)點(diǎn)，為了避免此類(lèi)社團(tuán)被鄰近的存在核心節(jié)點(diǎn)的社團(tuán)吞并，設(shè)定節(jié)點(diǎn)的基礎(chǔ)權(quán)重為：

度能夠描述社交網(wǎng)絡(luò)中節(jié)點(diǎn)間的鏈接分布情況。對(duì)于一個(gè)無(wú)向圖G=[V,E]，節(jié)點(diǎn)Vi的度ki等于與該節(jié)點(diǎn)相連的其他所有節(jié)點(diǎn)數(shù)目之和，是一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)自身特性的重要指標(biāo)。一般而言，節(jié)點(diǎn)的影響力與節(jié)點(diǎn)的度正相關(guān)。設(shè)定節(jié)點(diǎn)基于度的權(quán)重指標(biāo)為：

節(jié)點(diǎn)介數(shù)表示網(wǎng)絡(luò)中經(jīng)過(guò)該節(jié)點(diǎn)的所有節(jié)點(diǎn)間的最短路徑占所有最短路徑總數(shù)的比例。介數(shù)能夠反映網(wǎng)絡(luò)中不同成員的地位，是一個(gè)描述網(wǎng)絡(luò)節(jié)點(diǎn)全局特性的重要指標(biāo)。一般，節(jié)點(diǎn)影響力與節(jié)點(diǎn)介數(shù)正相關(guān)。節(jié)點(diǎn)介數(shù)越大，社交網(wǎng)絡(luò)中成員交流對(duì)該節(jié)點(diǎn)的依賴(lài)性越強(qiáng)。

對(duì)于網(wǎng)絡(luò)中節(jié)點(diǎn)Vi，有：

式中，σst表示從節(jié)點(diǎn)s到t的最短路徑的總數(shù)，σst(i)表示經(jīng)過(guò)i的最短路徑的數(shù)目。

2.2 算法步驟

通過(guò)引入權(quán)重函數(shù)I，對(duì)節(jié)點(diǎn)的影響力進(jìn)行綜合計(jì)算，使得影響力大的節(jié)點(diǎn)更容易被傳播，以此提升社團(tuán)劃分的準(zhǔn)確性。引入節(jié)點(diǎn)影響力的標(biāo)簽傳播算法主要步驟如下：

輸入：圖G=[V,E]

輸出：存儲(chǔ)節(jié)點(diǎn)標(biāo)簽的分類(lèi)數(shù)組L

步驟1：節(jié)點(diǎn)標(biāo)簽值初始化，為網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)分配一個(gè)唯一的標(biāo)簽。

步驟2：計(jì)算網(wǎng)絡(luò)中所有節(jié)點(diǎn)Vi的權(quán)重Ii，將權(quán)重值降序排列，確定一個(gè)序列Q。

步驟3：初次標(biāo)簽更新時(shí)，按序列Q進(jìn)行更新。

步驟4：對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)進(jìn)行標(biāo)簽迭代，節(jié)點(diǎn)的標(biāo)簽更新成為該節(jié)點(diǎn)鄰居節(jié)點(diǎn)中標(biāo)簽值出現(xiàn)數(shù)目最多的標(biāo)簽。若鄰居節(jié)點(diǎn)中有多個(gè)標(biāo)簽出現(xiàn)數(shù)目相對(duì)且同為最大值，則選取其中權(quán)重值I最大的標(biāo)簽作為節(jié)點(diǎn)標(biāo)簽。

步驟5：重復(fù)執(zhí)行步驟4，直至每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中標(biāo)簽變化趨于穩(wěn)定，即算法終止，標(biāo)簽值相同的節(jié)點(diǎn)被劃分入同一個(gè)社區(qū)。

通過(guò)預(yù)先為節(jié)點(diǎn)設(shè)置優(yōu)先級(jí)控制節(jié)點(diǎn)更新順序，能夠增強(qiáng)算法穩(wěn)定性，提升社團(tuán)劃分的效果，降低標(biāo)簽選擇隨機(jī)性對(duì)標(biāo)簽傳播效率和結(jié)果的影響。

3 基于社團(tuán)劃分的分級(jí)隱私保護(hù)算法

3.1 社交網(wǎng)絡(luò)隱私保護(hù)算法概述

本文提出的分級(jí)隱私保護(hù)算法涉及兩種經(jīng)典的無(wú)分級(jí)的社交網(wǎng)絡(luò)隱私保護(hù)匿名化方法：k-degree[10]匿名和k-degree-1-diversity[11]。其中，k-degree匿名實(shí)現(xiàn)了對(duì)節(jié)點(diǎn)度的隱私保護(hù)；k-degree-1-diversity實(shí)現(xiàn)了對(duì)節(jié)點(diǎn)度、敏感屬性的隱私保護(hù)。下面給出這兩個(gè)算法的具體細(xì)節(jié)。

3.1.1 k-degree匿名方法

在社交網(wǎng)絡(luò)隱私保護(hù)中，節(jié)點(diǎn)的度是攻擊者最易獲取的背景知識(shí)。如圖2所示，其中7個(gè)節(jié)點(diǎn)的度的集合d={3,1,4,2,1,2,1}，圖中僅節(jié)點(diǎn)c3的度為4，因此存在極高的暴露風(fēng)險(xiǎn)。

圖2 社交網(wǎng)絡(luò)模型

k-degree[10]匿名方法是Liu等人針對(duì)上述問(wèn)題提出的節(jié)點(diǎn)身份保護(hù)算法。k-degree匿名要求，對(duì)于社會(huì)網(wǎng)絡(luò)G=[V,E]，圖中擁有相同度的節(jié)點(diǎn)至少為k個(gè)，即圖中任一節(jié)點(diǎn)V都至少與其他k-1個(gè)節(jié)點(diǎn)擁有相同的度。

如圖3所示，在圖2的基礎(chǔ)上增加一條連接c1與c7的邊，圖中度的集合更新為d1={4,1,4,2,1,2,2}，每個(gè)度都至少出現(xiàn)兩次，滿(mǎn)足2-degree匿名。k-degree匿名使得攻擊者在擁有度背景知識(shí)的前提下，推斷出目標(biāo)身份的概率小于1/k。在k度匿名中缺乏對(duì)節(jié)點(diǎn)敏感屬性的保護(hù)，會(huì)受到一致性攻擊。圖3中，節(jié)點(diǎn)c1和節(jié)點(diǎn)c3的度相同，且出生年均為1994；節(jié)點(diǎn)c6和節(jié)點(diǎn)c7的度相同，且出生年均為1993。因此，敏感屬性極易暴露。

圖3 滿(mǎn)足2-degree的社交網(wǎng)絡(luò)模型

3.1.2 k-degree-1-diversity匿名方法

Yuan等人提出k-degree-l-diversity[11]匿名，用于保護(hù)節(jié)點(diǎn)的敏感標(biāo)簽。k-degree-l-diversity匿名要求，對(duì)于社會(huì)網(wǎng)絡(luò)G=[V,E]，對(duì)圖中任一節(jié)點(diǎn)V，與其具有相同度數(shù)的節(jié)點(diǎn)至少有k-1個(gè)，且度數(shù)相同的節(jié)點(diǎn)的敏感屬性值至少包含l種。如圖4所示，增加了c1與c4的連邊、c2與c5的連邊、c4與c7的連邊，圖中度的集合d2={4,2,4,4,2,2,2}，每個(gè)度數(shù)都至少出現(xiàn)2次，且每個(gè)等價(jià)類(lèi)中節(jié)點(diǎn)的敏感屬性均至少為兩種，有效防御了同質(zhì)性攻擊，滿(mǎn)足2-degree-2-diversity匿名。

上述兩種社交網(wǎng)絡(luò)數(shù)據(jù)隱私保護(hù)方法，僅考慮節(jié)點(diǎn)的度和節(jié)點(diǎn)敏感屬性因素，并采用統(tǒng)一的標(biāo)準(zhǔn)進(jìn)行匿名。論文基于這兩種無(wú)分級(jí)的隱私保護(hù)算法，提出基于社團(tuán)劃分的社交網(wǎng)絡(luò)分級(jí)隱私保護(hù)算法，有效滿(mǎn)足了社交網(wǎng)絡(luò)差異化隱私保護(hù)的需求。

圖4 滿(mǎn)足2-degree-2-diversity的社交網(wǎng)絡(luò)模型

3.2 基于敏感分布的 (k,l,θ1,θ2)算法

3.2.1 基于邊敏感分布的隱私約束準(zhǔn)則θ1

假設(shè)節(jié)點(diǎn)Vi和Vj的隱私保護(hù)等級(jí)都為H，即fs(Vi)=H、fs(Vj)=H，且 Vi和 Vj間存在連邊 Eij，則LE=1；否則，LE=0。其中，fs(Vi)表示點(diǎn)Vi的隱私保護(hù)等級(jí)，LE表示邊的標(biāo)簽值。也就是說(shuō)，兩個(gè)隱私保護(hù)等級(jí)均為H的節(jié)點(diǎn)的連邊的邊標(biāo)簽為1，其余邊的標(biāo)簽均為0。

如圖5所示，節(jié)點(diǎn)c1與節(jié)點(diǎn)c3的隱私保護(hù)等級(jí)均為H，則其連邊的標(biāo)簽為1。假設(shè)攻擊者獲知節(jié)點(diǎn)c1與節(jié)點(diǎn)c3的度均為4，雖然攻擊者無(wú)法分辨c1與c3的身份及其對(duì)應(yīng)的敏感信息，但攻擊者可以獲知c1與c3之間存在密切關(guān)聯(lián)。

圖5 邊敏感屬性分布

對(duì)于隱私保護(hù)等級(jí)較高的核心節(jié)點(diǎn)，不僅需要對(duì)其的度及敏感屬性多樣性進(jìn)行保護(hù)，也要避免將存在密切關(guān)聯(lián)的多個(gè)核心節(jié)點(diǎn)都劃分入同一個(gè)等價(jià)類(lèi)中。將局部核心節(jié)點(diǎn)之間的連邊定義為擁有敏感屬性的邊，應(yīng)限制每個(gè)等價(jià)類(lèi)內(nèi)敏感屬性邊的分布占比，定義等價(jià)類(lèi)內(nèi)敏感屬性邊的分布概率如下：

其中Gi表示第i個(gè)等價(jià)類(lèi)，V(Gi)表示等價(jià)類(lèi)中所有定點(diǎn)的個(gè)數(shù)，|V(Gi)|*|V(Gi)-1|表示等價(jià)類(lèi)中所有節(jié)點(diǎn)間的連邊的最大值，|ES(Gi)|表示Gi中敏感屬性邊的數(shù)目，fE為敏感屬性邊上的標(biāo)簽值，PS(Gi)反映了敏感屬性邊在等價(jià)類(lèi)內(nèi)的分布情況。

對(duì)于任一節(jié)點(diǎn)Vi，假設(shè)其所屬的等價(jià)類(lèi)為Gi，則如果其邊敏感分布滿(mǎn)足θ1準(zhǔn)則，則有：

即等價(jià)類(lèi)中存在敏感屬性邊的概率小于θ1。

3.2.2 基于標(biāo)簽分布的隱私約束準(zhǔn)則θ2

要求節(jié)點(diǎn)所屬的社團(tuán)標(biāo)簽LV在任意一個(gè)等價(jià)類(lèi)中的分布，與該社團(tuán)標(biāo)簽在整個(gè)網(wǎng)絡(luò)中的分布情況不超過(guò)閾值θ2。本文通過(guò)KL-散度（Kullback-Leibler）[8]定義概率分布的距離。

KL-散度：對(duì)于兩個(gè)給定的概率分布p=(p1,p2,…,pn)和 q=(q1,q2,…,qn)，有：

對(duì)于一個(gè)等價(jià)類(lèi)Gi，標(biāo)簽在等價(jià)類(lèi)中的分布PG與標(biāo)簽在整個(gè)網(wǎng)絡(luò)中的分布PT的KL-散度為：

則標(biāo)簽分布滿(mǎn)足隱私約束準(zhǔn)則θ2。

3.3 基于社團(tuán)劃分的分級(jí)隱私保護(hù)算法

社交網(wǎng)絡(luò)中，不同個(gè)體的隱私保護(hù)需求等級(jí)存在差別。社團(tuán)局部核心節(jié)點(diǎn)的屬性往往能夠反映整個(gè)社團(tuán)的部分屬性特征，其保密性要求較高，應(yīng)對(duì)其采用更高等級(jí)的泛化程度。社交網(wǎng)絡(luò)中普遍存在社團(tuán)結(jié)構(gòu)，權(quán)重值較高的節(jié)點(diǎn)影響力較大。社團(tuán)局部核心節(jié)點(diǎn)的屬性往往能夠反映整個(gè)社團(tuán)的部分屬性特征，其保密性要求較高，應(yīng)對(duì)其采用更高等級(jí)的泛化程度[18]。

本文結(jié)合k-degree、k-degree-l-diversity等匿名保護(hù)思路，提出了一種綜合敏感程度分布的分級(jí)隱私保護(hù)算法。由于社交網(wǎng)絡(luò)對(duì)處于不同結(jié)構(gòu)特征中的節(jié)點(diǎn)的隱私保護(hù)需求有所不同，將隱私保護(hù)等級(jí)分為H（high）、M（middle）和L（low）3種。

H等級(jí)：要求對(duì)節(jié)點(diǎn)的度、敏感屬性多樣性、標(biāo)簽和邊的敏感分布均滿(mǎn)足匿名保護(hù)要求，即(k,l,θ1,θ2)模型。

M等級(jí)：對(duì)節(jié)點(diǎn)的度、敏感屬性多樣性進(jìn)行保護(hù)，滿(mǎn)足k-degree-l-diversity匿名要求。

L等級(jí)：僅對(duì)節(jié)點(diǎn)的度進(jìn)行保護(hù)，滿(mǎn)足k-degree匿名要求。

分級(jí)隱私保護(hù)示意圖如圖6所示。

圖6 分級(jí)隱私保護(hù)

其中，隱私保護(hù)等級(jí)為H的節(jié)點(diǎn)的影響力不小于 I1，采用 (k,l,θ1,θ2)匿名模型；隱私保護(hù)等級(jí)為M的節(jié)點(diǎn)的影響力小于I1且大于等于I2，采用k-degree-l-diversity匿名模型；隱私保護(hù)等級(jí)為L(zhǎng)的節(jié)點(diǎn)的影響力小于I2，采用k-degree匿名模型。(k,l,θ1,θ2)分級(jí)保護(hù)社交網(wǎng)絡(luò)匿名圖示例，如圖7所示。

圖7 (k,l,θ1,θ2)分級(jí)保護(hù)社交網(wǎng)絡(luò)匿名圖示例

{c1,c2,c6}屬于同一社團(tuán)，標(biāo)簽為l1；{c3,c7}屬于同一社團(tuán)，標(biāo)簽為l2；{c4,c5}屬于同一社團(tuán)，標(biāo)簽為l3。

經(jīng)分級(jí)隱私保護(hù)后，在節(jié)點(diǎn)c1與節(jié)點(diǎn)c4、節(jié)點(diǎn)c4與節(jié)點(diǎn)c7之間增加了兩條邊，匿名發(fā)布圖可被劃分為3個(gè)等價(jià)類(lèi)：

①度為4的等價(jià)類(lèi)：{c1,c3,c4}；

②度為2的等價(jià)類(lèi)：{c6,c7}；

③度為1的等價(jià)類(lèi)：{c2,c5}。

由于僅c1與c3的連邊E13的邊敏感屬性值LE=1，因此在等價(jià)類(lèi){c1,c3,c4}中，PS(Gi)≤ 0.4。

因此，示例中，分級(jí)隱私保護(hù)模型如下：

①c1與c3的隱私保護(hù)等級(jí)為H，滿(mǎn)足(2,2,0.4,0.2)匿名；

②c4的隱私保護(hù)等級(jí)為M，滿(mǎn)足2-degree-2-diversity匿名；

③c2、c5、c6與c7的隱私保護(hù)等級(jí)為L(zhǎng)，滿(mǎn)足2-degree匿名。

3.4 算法步驟

基于社團(tuán)劃分的分級(jí)隱私保護(hù)算法主要步驟如下。

輸入：圖 G,k,l,θ1,θ2（k、l為整數(shù)）

輸出：分級(jí)匿名圖G'

步驟1：通過(guò)基于節(jié)點(diǎn)影響力的標(biāo)簽傳播算法，計(jì)算節(jié)點(diǎn)影響力Il(Vi)，并實(shí)現(xiàn)社團(tuán)劃分。同一社團(tuán)內(nèi)的節(jié)點(diǎn)擁有相同的標(biāo)簽值lk。

步驟2：選取影響力閾值I1和I2，若Il(Vi)≥I1，記其隱私等級(jí)為H；若I1＞Il(Vi)≥I2，記其隱私等級(jí)為M；若Il(Vi)＜I2，記其隱私等級(jí)為L(zhǎng)。

步驟3：采用(k,l,θ1,θ2)匿名模型，對(duì)隱私保護(hù)等級(jí)為H的節(jié)點(diǎn)進(jìn)行泛化，使得等價(jià)類(lèi)中度相同的節(jié)點(diǎn)數(shù)不少于k，敏感屬性種類(lèi)不少于l，邊敏感分布滿(mǎn)足約束準(zhǔn)則θ1，標(biāo)簽分布滿(mǎn)足約束準(zhǔn)則θ2。

步驟4：采用k-degree-1-diversity匿名模型，對(duì)隱私保護(hù)等級(jí)為M的節(jié)點(diǎn)進(jìn)行泛化，使得等價(jià)類(lèi)中度相同的節(jié)點(diǎn)數(shù)不少于k，敏感屬性種類(lèi)不少于l。

步驟5：采用k-degree匿名模型，對(duì)隱私保護(hù)等級(jí)為L(zhǎng)的節(jié)點(diǎn)進(jìn)行泛化，使得等價(jià)類(lèi)中度相同的節(jié)點(diǎn)數(shù)不少于k。

步驟6：循環(huán)迭代直至匿名完畢，發(fā)布分級(jí)匿名圖G'。

通過(guò)基于現(xiàn)有的k-degree和k-degree-1-diversity匿名模型，本文提出了綜合敏感屬性分布的(k,l,θ1,θ2)匿名模型，并基于社團(tuán)劃分和節(jié)點(diǎn)影響力，實(shí)現(xiàn)了對(duì)社交網(wǎng)絡(luò)數(shù)據(jù)發(fā)布的分級(jí)隱私保護(hù)，有效滿(mǎn)足了社交網(wǎng)絡(luò)差異化的隱私保護(hù)需求。

4 實(shí)驗(yàn)分析

4.1 隱私保護(hù)算法評(píng)估指標(biāo)

根據(jù)Liu[11]等人提出的匿名算法評(píng)估指標(biāo)，本文采用信息損失率（COSTA）和平均路徑長(zhǎng)度（APL）進(jìn)行評(píng)估，具體的計(jì)算方法如下。

（1）信息損失率

G中節(jié)點(diǎn)i的度。

（2）平均路徑長(zhǎng)度

其中dij表示節(jié)點(diǎn)i與j之間的最短距離。

4.2 實(shí)驗(yàn)結(jié)果及討論

實(shí)驗(yàn)選用社交網(wǎng)絡(luò)Pokec[19]上的用戶(hù)數(shù)據(jù)進(jìn)行分析。Pokec是斯洛伐克著名的在線(xiàn)社交網(wǎng)絡(luò)平臺(tái)，至今提供了近20年服務(wù)，連接了160多萬(wàn)人。原始數(shù)據(jù)集中包含性別、年齡、愛(ài)好等用戶(hù)屬性，是優(yōu)秀的研究社交網(wǎng)絡(luò)的數(shù)據(jù)集。本文通過(guò)節(jié)點(diǎn)間的相互連接，通過(guò)發(fā)散的方法選取其中2 500個(gè)節(jié)點(diǎn)及它們之間5 332條邊進(jìn)行研究。本文選取節(jié)點(diǎn)的度數(shù)作為準(zhǔn)標(biāo)識(shí)符進(jìn)行匿名化保護(hù)，并選取用戶(hù)生日（出生年）代表用戶(hù)隱私屬性進(jìn)行分析，即每個(gè)節(jié)點(diǎn)包含的屬性有節(jié)點(diǎn)編號(hào)、用戶(hù)生日、節(jié)點(diǎn)度數(shù)，且包含節(jié)點(diǎn)間邊的關(guān)系。

在Pokec數(shù)據(jù)集上，分別應(yīng)用k-degree、k-degree-l-diversity、(k,l,θ1,θ2)和分級(jí)的 (k,l,θ1,θ2)匿名模型，對(duì)比算法信息損失率和邊變化的表現(xiàn)。取l=3，θ1=0.1，θ2=0.36，取影響力前10%的節(jié)點(diǎn)標(biāo)注其隱私保護(hù)等級(jí)為H，前10%～30%的節(jié)點(diǎn)的隱私保護(hù)等級(jí)為M，剩余節(jié)點(diǎn)的隱私保護(hù)等級(jí)為L(zhǎng)。在l=3的情況下，隨k值變化的信息損失率和邊的變化如圖8、圖9所示。

圖8 信息損失率與k值的關(guān)聯(lián)

圖9 邊變化數(shù)與k值的關(guān)聯(lián)

圖8 和圖9描述了隨著k的增加，四類(lèi)算法的信息損失率都幾乎呈線(xiàn)性增長(zhǎng)。通過(guò)實(shí)驗(yàn)數(shù)據(jù)分析可知，k-degree匿名信息損失率和邊變化數(shù)最小(k,l,θ1,θ2)匿名信息損失率和邊變化數(shù)最大，k-degree-l-diversity匿名信息損失率和邊變化數(shù)介于兩者之間。分級(jí)的(k,l,θ1,θ2)匿名信息損失率和邊變化數(shù)略小于k-degree-l-diversity匿名，實(shí)現(xiàn)了對(duì)核心節(jié)點(diǎn)的較高隱私保護(hù)程度，并將信息損失率和邊變化數(shù)控制在可接受的范圍。

不同k值對(duì)APL影響的測(cè)試結(jié)果，則如圖10所示。

圖10描述了隨著k的增加，四類(lèi)算法的APL都緩慢下降。通過(guò)實(shí)驗(yàn)數(shù)據(jù)分析可知，k-degree匿名APL最大且與原圖更接近，(k,l,θ1,θ2)匿名APL最小且與原圖差異性最大，k-degree-l-diversity匿名APL介于兩者之間，而分級(jí)的(k,l,θ1,θ2)匿名APL略大于k-degree-l-diversity匿名的APL，實(shí)現(xiàn)了對(duì)核心節(jié)點(diǎn)的較高隱私保護(hù)程度，并將APL的變化量控制在可接受的范圍。

圖10 APL與k值的關(guān)聯(lián)

總體上，信息損失率和保護(hù)強(qiáng)度都會(huì)隨著k值的上升而提高。本文提出的分級(jí)匿名算法降低了k-degree-l-diversity算法的信息損失程度，信息損失率更小，數(shù)據(jù)可用性有所提升，具有更強(qiáng)的安全性，平均路徑長(zhǎng)度與原圖也更為接近。由此可見(jiàn)，分級(jí)匿名在實(shí)現(xiàn)對(duì)局部核心節(jié)點(diǎn)的有效保護(hù)的同時(shí)，保持了圖結(jié)構(gòu)性質(zhì)，具有一定的優(yōu)越性，非常適用于社交網(wǎng)絡(luò)數(shù)據(jù)發(fā)布。

5 結(jié) 語(yǔ)

本文主要針對(duì)社交網(wǎng)絡(luò)數(shù)據(jù)發(fā)布環(huán)節(jié)數(shù)據(jù)可用性和節(jié)點(diǎn)隱私信息保密性的需求，提出了社交網(wǎng)絡(luò)中的分級(jí)隱私保護(hù)算法，實(shí)現(xiàn)了社交網(wǎng)絡(luò)不同結(jié)構(gòu)特征中節(jié)點(diǎn)差異化的隱私保護(hù)。優(yōu)勢(shì)主要體現(xiàn)在以下幾個(gè)方面：

（1）個(gè)性化隱私保護(hù)。分級(jí)的隱私保護(hù)算法綜合考慮了節(jié)點(diǎn)的自身特性和全局特性，基于社團(tuán)結(jié)構(gòu)識(shí)別了局部核心節(jié)點(diǎn)，并對(duì)局部核心節(jié)點(diǎn)采用更高的泛化程度的匿名算法，實(shí)現(xiàn)了個(gè)性化的隱私保護(hù)需求。

（2）數(shù)據(jù)高可用性。分級(jí)的隱私保護(hù)有效避免了對(duì)某些用戶(hù)的過(guò)度保護(hù)，僅重點(diǎn)保護(hù)局部核心節(jié)點(diǎn)，且通過(guò)社團(tuán)劃分優(yōu)先聚集具有相近結(jié)構(gòu)特征的節(jié)點(diǎn)，降低了數(shù)據(jù)發(fā)布的信息損失程度，提高了數(shù)據(jù)可用性。

（3）數(shù)據(jù)安全性。分級(jí)的隱私保護(hù)算法對(duì)于局部核心節(jié)點(diǎn)采用(k,l,θ1,θ2)匿名模型，對(duì)局部核心節(jié)點(diǎn)的敏感屬性分布進(jìn)行保護(hù)，保證了數(shù)據(jù)發(fā)布的安全性。

因此，融合社團(tuán)劃分的社交網(wǎng)絡(luò)分級(jí)隱私保護(hù)算法具有良好的可行性和優(yōu)越性，具有極高的研究?jī)r(jià)值和廣闊的應(yīng)用前景。

目前，本文對(duì)于節(jié)點(diǎn)隱私保護(hù)等級(jí)的劃分還比較單一，未來(lái)將結(jié)合數(shù)據(jù)的具體特征、隱私需求細(xì)化分類(lèi)層級(jí)。此外，研究結(jié)果基于攻擊者的背景知識(shí)為節(jié)點(diǎn)的度，尚未考慮背景知識(shí)為子圖等情況，以后可以進(jìn)一步展開(kāi)討論。

[1] 姚瑞欣,李暉,曹進(jìn).社交網(wǎng)絡(luò)中的隱私保護(hù)研究綜述[J].網(wǎng)絡(luò)與信息安全學(xué)報(bào),2016,2(04):33-43.YAO Rui-xin,LI Hui,CAO Jin.Overview of Privacy Protection in Social Networks[J].Chinese Journal of Network and Information Security,2016,2(04):33-43.

[2] Backstrom L,Dwork C,Kleinberg J.Wherefore Art Thou r3579x?:Anonymized Social Networks,Hidden Patterns,and Structural Steganography[C].International Conference on World Wide Web ACM,2007:181-190.

[3] Liu K,Terzi E.Towards Identity Anonymization on Graphs[C].Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data ACM,2008:93-106.

[4] Zheleva E,Getoor L.Preserving the Privacy of Sensitive Relationships in Graph Data[M].Privacy,Security,and Trust in KDD,2008:153-171.

[5] ZHOU B,PEI J,Luk W S.A Brief Survey on Anonymization Techniques for Privacy Preserving Publishing of Social Network Data[J].ACM SIGKDD Explorations Newsletter,2008,10(02):12-22.

[6] Sweeney L.K-anonymity:A Model for Protecting Privacy[J].International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems,2002,10(05):557-570.

[7] Machanavajjhala A,Kifer D,Gehrke J.l-diversity:Privacy Beyond k-anonymity[J].ACM Transactions on Knowledge Discovery from Data(TKDD),2007,1(01):3.

[8] LI N,LI T,Venkatasubramanian S.t-closeness:Privacy Beyond k-anonymity and l-diversity[C].Data Engineering,IEEE 23rd International Conference on,2007:106-115.

[9] Wasserman S.Social Network Analysis:Methods and Applications[M].Cambridge:Cambridge University Press,1994.

[10] LIU K,Terzi E.Towards Identity Anonymization on Graphs[C].Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data ACM,2008:93-106.

[11] YUAN M,CHEN L,YU P S,et al.Protecting Sensitive Labels in Social Network Data Anonymization[J].IEEE Transactions on Knowledge & Data Engineering,2013,25(03):633-647.

[12] YING X,WU X.Randomizing Social Networks:a Spectrum Preserving Approach[C].Siam International Conference on Data Mining,2008(08):739-750.

[13] ZHOU B,PEI J.Preserving Privacy in Social Networks Against Neighborhood Attacks[C].International Conference on Data Engineering IEEE,2008:506-515.

[14] ZHOU B,PEI J.The k-anonymity and l-diversity Approaches for Privacy Preservation in Social Networks Against Neighborhood Attacks[J].Knowledge and Information Systems,2011,28(01):47-77.

[15] Raghavan U N,Albert R,Kumara S.Near Linear Time Algorithm to Detect Community Structures in Large-scale Networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2007,76(02):036106.

[16] 季青松,趙郁忻,陳樂(lè)生等.有效改善標(biāo)簽傳播算法魯棒性的途徑[J].信息安全與通信保密,2012(09):135-137.JI Qing-song,ZHAO Yu-xin,CHEN Le-sheng,et al.A Method for Effectively Improving the Robustness of Label Propagation Algorithm[J].China Information Security,2012(09):135-137.

[17] 劉世超,朱福喜,甘琳.基于標(biāo)簽傳播概率的重疊社區(qū)發(fā)現(xiàn)算法[J].計(jì)算機(jī)學(xué)報(bào),2016,39(04):717-729.LIU Shi-chao,ZHU Fu-xi,GAN lin.A Label Propagation Probability Based Algorithm for Overlapping Community Detection[J].Chinese Journal of Computers,2016,39(04):717-729.

[18] 蘇潔,劉帥,羅智勇等.基于信息損失量估計(jì)的匿名圖構(gòu)造方法[J].通信學(xué)報(bào),2016,37(06):56-64.SU Jie,LIU Shuai,LUO Zhi-yong,et al.Method of Constructing an Anonymous Graph Based on Information Loss Estimation[J].Journal on Communicati-ons,2016,37(06):56-64.

[19] Takac L,Zabovsky M.Data Analysis in Public Social Networks[C].Proceedings of International Scientific Conference & International Workshop Present Day Trends of Innovations,2012:1-6.