胡曉依 喬麗娟 王宇

（曲阜師范大學(xué)軟件學(xué)院 山東省曲阜市 273100）

在線社交媒體服所務(wù)產(chǎn)生的與日俱增的海量數(shù)據(jù)，為發(fā)現(xiàn)敏感信息提供了機(jī)會(huì)。為了滿足人們對(duì)數(shù)據(jù)的需求，數(shù)據(jù)發(fā)布者一直在發(fā)布數(shù)據(jù)，以提供給數(shù)據(jù)挖掘者進(jìn)行分析。但是，這產(chǎn)生了隱私的泄露問題，因?yàn)樵谠S多社交網(wǎng)絡(luò)數(shù)據(jù)中，頂點(diǎn)屬性和頂點(diǎn)之間的關(guān)系可能很敏感。因此，任何公開發(fā)布的信息都可能會(huì)涉及有關(guān)個(gè)人的隱私問題。

在某些情況下，網(wǎng)絡(luò)中個(gè)體或身份信息不敏感，而個(gè)體之間的關(guān)系是保密的，比如金融交易網(wǎng)絡(luò)，電子郵件網(wǎng)絡(luò)和社交網(wǎng)絡(luò)，其中鏈接的存在即金錢交易，私人電子郵件或兩個(gè)人之間的友誼被認(rèn)為是敏感的。這些數(shù)據(jù)發(fā)布之后，社會(huì)網(wǎng)絡(luò)中的數(shù)據(jù)被攻擊者大量收集，他們通過分析這些數(shù)據(jù)獲得有價(jià)值的信息，這將造成嚴(yán)重的隱私泄露。因此研究解決隱私泄露的匿名方法成為一大研究熱點(diǎn)[4][5]。

保護(hù)邊隱私的一種匿名化處理方法是隨機(jī)化方法，即將社交網(wǎng)絡(luò)建模為無向圖，并隨機(jī)刪除現(xiàn)有邊(u,v)，并添加相同數(shù)量的邊，從所有不存在的邊中隨機(jī)選擇不存在的邊(w,z)，將其添加到社會(huì)網(wǎng)絡(luò)圖中。隨機(jī)化方法的主要缺點(diǎn)是，對(duì)社會(huì)網(wǎng)絡(luò)的結(jié)構(gòu)具有較大的破壞性，因?yàn)閷?duì)于不存在的鏈接(w,z)是從整個(gè)空間中隨機(jī)選擇的。例如，在兩個(gè)遠(yuǎn)程節(jié)點(diǎn)之間添加邊，或刪除連接兩個(gè)子圖的唯一邊，將極大地影響最短路徑和可達(dá)性分析。

表1：數(shù)據(jù)集信息統(tǒng)計(jì)

本文考慮了頻繁子圖中敏感邊隱私的保護(hù)問題。具體來說，我們要確保攻擊者在社交網(wǎng)絡(luò)分析中無法準(zhǔn)確地推斷出敏感邊的存在，以確保邊的隱私需求。本文提出的基于敏感邊的隱私保護(hù)方法（Privacy protection of sensitive side），簡稱SEPP,能夠在保證社會(huì)網(wǎng)絡(luò)隱私保護(hù)需求的前提下，極大地保留數(shù)據(jù)的可用性。

圖1：社會(huì)網(wǎng)絡(luò)隱私保護(hù)實(shí)例

圖2：攻擊模型中用于敏感邊推斷的兩種子圖：三角形、矩形

1 相關(guān)工作

社會(huì)網(wǎng)絡(luò)隱私保護(hù)研究是一個(gè)熱門研究領(lǐng)域。它起源于關(guān)系型數(shù)據(jù)的研究，而典型的k-匿名技術(shù)是由Samarati 和Sweeny[6][7]在2002年提出來的。在社交網(wǎng)絡(luò)發(fā)布隱私保護(hù)的研究中，k-匿名是通過聚類泛化來實(shí)現(xiàn)的，即所有的社會(huì)網(wǎng)絡(luò)圖中的節(jié)點(diǎn)都被劃分到n 個(gè)簇中，每個(gè)簇中節(jié)點(diǎn)的個(gè)數(shù)都不小于k。當(dāng)發(fā)布數(shù)據(jù)時(shí)，每個(gè)簇都被泛化成一個(gè)超級(jí)節(jié)點(diǎn)，而簇與簇之間的邊也被泛化成超邊。子圖匿名意味著，當(dāng)攻擊者將目標(biāo)節(jié)點(diǎn)的子圖信息作為背景知識(shí)時(shí)，在社會(huì)網(wǎng)絡(luò)圖中至少存在k-1 個(gè)難以區(qū)分的其他節(jié)點(diǎn)的子圖結(jié)構(gòu)。然后，利用圖遷移技術(shù)使得目標(biāo)節(jié)點(diǎn)的敏感信息被泄露的概率不高于1/k。為了保護(hù)目標(biāo)節(jié)點(diǎn)的敏感信息，通過添加噪音和修改邊來確保攻擊者在發(fā)布的社會(huì)網(wǎng)絡(luò)圖中，識(shí)別目標(biāo)節(jié)點(diǎn)的可能性不高于一個(gè)確定的概率。該方法的優(yōu)點(diǎn)是，它不需要改變?cè)忌鐣?huì)網(wǎng)絡(luò)數(shù)據(jù)中節(jié)點(diǎn)和邊的個(gè)數(shù)。這在統(tǒng)計(jì)分析應(yīng)用中具有較大的優(yōu)勢。

2 現(xiàn)有的隱私保護(hù)技術(shù)

現(xiàn)有的隱私保護(hù)方法如果只通過在社會(huì)網(wǎng)絡(luò)圖上增刪邊，極有可能使得攻擊者通過分析發(fā)布的社會(huì)網(wǎng)絡(luò)圖來推斷出兩個(gè)節(jié)點(diǎn)之間的關(guān)聯(lián)關(guān)系。假設(shè)圖1（a），圖1（b）是表示社會(huì)網(wǎng)絡(luò)中的朋友關(guān)系，A，B 之間的關(guān)系是敏感的。如圖1（a）是原始的社會(huì)網(wǎng)絡(luò)圖，如圖1（b）是使用簡單隨機(jī)添加刪除邊得到的匿名后的社會(huì)網(wǎng)絡(luò)圖，我們假設(shè)攻擊者擁有強(qiáng)大的背景知識(shí)，在此基礎(chǔ)上攻擊者通過分析頻繁子圖模式來預(yù)測這些隱藏鏈接的存在。如圖1（b），攻擊者極有可能推斷出節(jié)點(diǎn)A，B 有關(guān)聯(lián)。

3 基于局部擾亂的社會(huì)網(wǎng)絡(luò)隱私保護(hù)

針對(duì)上述存在的問題，本文研究了社會(huì)網(wǎng)絡(luò)發(fā)布中隱藏邊的隱私保護(hù)問題。根據(jù)社會(huì)活動(dòng)個(gè)體對(duì)隱私保護(hù)的不同要求，本文提出了一種基于社會(huì)網(wǎng)絡(luò)的敏感邊的隱私保護(hù)機(jī)制，將現(xiàn)有隱私保護(hù)技術(shù)與不確定圖思想結(jié)合起來，設(shè)計(jì)了一種新的隱私保護(hù)方法。圖2是攻擊模型中用于推斷的兩種子圖：三角形、矩形。

算法1.k—分組算法輸入：原始的社會(huì)網(wǎng)絡(luò)圖G，敏感邊集T 及參數(shù)k；輸出：組集F；1.節(jié)點(diǎn)根據(jù)度數(shù)降序排列；；2.group g=new group{t};3.while |V|＞k do 4.while |g|＞k do 5.for each (u,v)∈E do 6.compute 7.8.9.10.End while 11.

邊t 的頻繁子圖表示為wt，如三角形、矩形，Wt表示鏈接t 的頻繁子圖，邊的權(quán)重為子圖的個(gè)數(shù)|Wt|。目標(biāo)邊t 的相似度表示為|Wt|，目標(biāo)t 的相似度是f(P,t)=|Wt|，其中目標(biāo)邊的相似性意味著更高的概率被推斷。定義了集合T 中所有目標(biāo)邊的總相似度。文獻(xiàn)[2]中TPP 算法的目的是通過刪除一個(gè)有限集作為保護(hù)者來為所有的目標(biāo)提供保護(hù)，以此來抵擋對(duì)抗性的邊預(yù)測，該有限集是由可替換的非目標(biāo)邊組成，用作保護(hù)者，其中其中C 是常數(shù)。該相似度越高，則敏感邊被推斷出的概率就越高。本文提出的匿名方法模型，首先根據(jù)節(jié)點(diǎn)的度數(shù)不同，將節(jié)點(diǎn)按度的大小降序排列；然后根據(jù)三角形、矩形的結(jié)構(gòu)特征，用權(quán)值大小表征邊的相關(guān)程度，通過計(jì)算盡可能選擇對(duì)三角形、矩形數(shù)量影響大的邊；然后隨機(jī)刪除這些邊；接著，對(duì)于任意邊，賦予每條邊一個(gè)存在概率，用來混淆邊真實(shí)存在的概率；最后得出匿名圖。

根據(jù)現(xiàn)有隱私保護(hù)模型的原理，對(duì)原始圖添加刪除邊操作，在添加刪除邊的過程中，改變?cè)紙D中的頻繁子圖結(jié)構(gòu)，同時(shí)減少對(duì)結(jié)構(gòu)的破壞；對(duì)原始圖中的頻繁子圖進(jìn)行隨機(jī)化處理，即三角形及矩形。

算法2.隨機(jī)化算法輸入：組集F；輸出：匿名后的社會(huì)網(wǎng)絡(luò)圖G'；1.While |F|＞0 do 2.For each do 3.隨機(jī)刪除邊(u,v)，其中4.隨機(jī)添加一條邊(w,z)，其中 且5.Sample with probability 6.End for 7.End while 8.Return G'//返回匿名圖

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

4.1 實(shí)驗(yàn)數(shù)據(jù)集和對(duì)比算法

本文在三個(gè)數(shù)據(jù)集上對(duì)數(shù)據(jù)可用性進(jìn)行測試，數(shù)據(jù)集的詳細(xì)信息如表1所示，其中數(shù)據(jù)集WebK-B 是包含來自4 所大學(xué)的877 個(gè)網(wǎng) 站(http://linqs.umiacs.umd.edu/projects//projects/lbc/index.html)，Citat-ion 數(shù)據(jù)集http://www.cs.umd.edu/projects/linqs/projects/lbc/index.html 是一個(gè)論文引用數(shù)據(jù)集，它包含2550 篇論文和6101 個(gè)引用關(guān)系。Cora (http://www.cs.umd.edu/projects/linqs/projects/lbc/index.html)數(shù)據(jù)集，該數(shù)據(jù)集是有向圖，有 2708 個(gè)節(jié)點(diǎn)和 5429 條邊。

圖3：數(shù)據(jù)集WebKB

圖4：數(shù)據(jù)集Citation

圖5：數(shù)據(jù)集Core

圖6：數(shù)據(jù)集WebKB

圖7：數(shù)據(jù)集Citation

圖8：數(shù)據(jù)集Core

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

本文采用平均聚類系數(shù)作為評(píng)價(jià)指標(biāo)，所有的算法均保證在同一實(shí)驗(yàn)環(huán)境下進(jìn)行，各算法在3 個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果對(duì)比圖見圖2-圖4。平均局部聚類系數(shù)越接近原始圖表示算法效果越好。兩種匿名方法后的社會(huì)網(wǎng)絡(luò)圖的平均局部聚集系數(shù)都呈下降趨勢。如果參數(shù)k 較大，則匿名度較大，并且匿名損失將增加。圖3-圖5分別代表的是3 個(gè)數(shù)據(jù)集在k 的不同取值下平均局部聚類系數(shù)的變化。

圖6-圖8分別代表的是3 個(gè)真實(shí)數(shù)據(jù)集在不同k 值下杰卡德相似系數(shù)的變化。從整體來看，隨著k 值的增加，匿名處理對(duì)原始社區(qū)具有較為嚴(yán)重的破壞。Local-Perturbation 方法隨著k 值增加，其對(duì)應(yīng)的杰卡德相似系數(shù)下降幅度較大，而本文中提出的局部擾亂數(shù)據(jù)匿名方法所對(duì)應(yīng)的杰卡德相似系數(shù)下降幅度明顯較弱。更明顯的是，在k 的不同取值情況下，SEPP 隱私保護(hù)方法的杰卡德相似系數(shù)值較大，說明它能更好的保護(hù)社區(qū)結(jié)構(gòu)。這足以證明本文提出的匿名方法能夠更好地保護(hù)原始社會(huì)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。

5 結(jié)束語

本文提出了一種新的社會(huì)網(wǎng)絡(luò)隱私保護(hù)算法，該算法首先利用k-分組算法，根據(jù)TPP 算法對(duì)非敏感邊進(jìn)行分組，然后采用隨機(jī)化方法進(jìn)行隨機(jī)添加刪除邊，最后使得每條邊都有相應(yīng)的概率存在于社會(huì)網(wǎng)絡(luò)中，同時(shí)使攻擊者唯一識(shí)別帶敏感標(biāo)簽個(gè)體的概率不高于1/k。因此可以達(dá)到較好的效果。詳細(xì)的實(shí)驗(yàn)表明，本文算法能夠在平均聚類系數(shù)和杰卡德相似系數(shù)上取得顯著提高，能更好的保護(hù)社區(qū)結(jié)構(gòu)。在今后的工作中，我們將嘗試使用更先進(jìn)的技術(shù)來改進(jìn)算法。