基于局部擾亂的社會網(wǎng)絡隱私保護

胡曉依 喬麗娟 王宇

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

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

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

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

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

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

圖1：社會網(wǎng)絡隱私保護實例

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

1 相關工作

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

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

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

3 基于局部擾亂的社會網(wǎng)絡隱私保護

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

算法1.k—分組算法輸入：原始的社會網(wǎng)絡圖G，敏感邊集T 及參數(shù)k；輸出：組集F；1.節(jié)點根據(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 的頻繁子圖，邊的權重為子圖的個數(shù)|Wt|。目標邊t 的相似度表示為|Wt|，目標t 的相似度是f(P,t)=|Wt|，其中目標邊的相似性意味著更高的概率被推斷。定義了集合T 中所有目標邊的總相似度。文獻[2]中TPP 算法的目的是通過刪除一個有限集作為保護者來為所有的目標提供保護，以此來抵擋對抗性的邊預測，該有限集是由可替換的非目標邊組成，用作保護者，其中其中C 是常數(shù)。該相似度越高，則敏感邊被推斷出的概率就越高。本文提出的匿名方法模型，首先根據(jù)節(jié)點的度數(shù)不同，將節(jié)點按度的大小降序排列；然后根據(jù)三角形、矩形的結構特征，用權值大小表征邊的相關程度，通過計算盡可能選擇對三角形、矩形數(shù)量影響大的邊；然后隨機刪除這些邊；接著，對于任意邊，賦予每條邊一個存在概率，用來混淆邊真實存在的概率；最后得出匿名圖。

根據(jù)現(xiàn)有隱私保護模型的原理，對原始圖添加刪除邊操作，在添加刪除邊的過程中，改變原始圖中的頻繁子圖結構，同時減少對結構的破壞；對原始圖中的頻繁子圖進行隨機化處理，即三角形及矩形。

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

4 實驗結果和分析

4.1 實驗數(shù)據(jù)集和對比算法

本文在三個數(shù)據(jù)集上對數(shù)據(jù)可用性進行測試，數(shù)據(jù)集的詳細信息如表1所示，其中數(shù)據(jù)集WebK-B 是包含來自4 所大學的877 個網(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 是一個論文引用數(shù)據(jù)集，它包含2550 篇論文和6101 個引用關系。Cora (http://www.cs.umd.edu/projects/linqs/projects/lbc/index.html)數(shù)據(jù)集，該數(shù)據(jù)集是有向圖，有 2708 個節(jié)點和 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ù)作為評價指標，所有的算法均保證在同一實驗環(huán)境下進行，各算法在3 個數(shù)據(jù)集上的實驗結果對比圖見圖2-圖4。平均局部聚類系數(shù)越接近原始圖表示算法效果越好。兩種匿名方法后的社會網(wǎng)絡圖的平均局部聚集系數(shù)都呈下降趨勢。如果參數(shù)k 較大，則匿名度較大，并且匿名損失將增加。圖3-圖5分別代表的是3 個數(shù)據(jù)集在k 的不同取值下平均局部聚類系數(shù)的變化。

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

5 結束語

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