范國婷，楊 穎，孫 剛，趙 佳

（阜陽師范學(xué)院 計算機與信息工程學(xué)院，安徽 阜陽 236037）

基于擾動的社交網(wǎng)絡(luò)保護(hù)方法

范國婷，楊 穎，孫 剛，趙 佳

（阜陽師范學(xué)院 計算機與信息工程學(xué)院，安徽 阜陽 236037）

擾動技術(shù)是社交網(wǎng)絡(luò)隱私保護(hù)的重要方法，本文提出了高斯隨機擾動和貪心擾動兩種擾動算法保護(hù)社交網(wǎng)絡(luò)的權(quán)值，分別適用于動態(tài)和靜態(tài)社交網(wǎng)絡(luò)。高斯隨機擾動可以簡單有效地保護(hù)動態(tài)社交網(wǎng)絡(luò)的權(quán)值隱私，貪心擾動算法將社交網(wǎng)絡(luò)的邊分類，可以在保護(hù)靜態(tài)社交網(wǎng)絡(luò)權(quán)值隱私的同時保證社交網(wǎng)絡(luò)的最小生成樹不變，提高社交網(wǎng)絡(luò)數(shù)據(jù)的可用性。實驗結(jié)果表明兩種算法均能有效保護(hù)社交網(wǎng)絡(luò)的權(quán)值安全，并且保持較高的數(shù)據(jù)可用性。

社交網(wǎng)絡(luò)；隱私保護(hù)；擾動；權(quán)值

快速發(fā)展的社交網(wǎng)絡(luò)存儲了用戶的大量個人信息，這些海量信息蘊含了豐富的價值，對社交網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘能得到寶貴的知識，但是社交網(wǎng)絡(luò)數(shù)據(jù)包含了用戶的大量敏感信息，對社交網(wǎng)絡(luò)數(shù)據(jù)挖掘前需要對其進(jìn)行隱私保護(hù)處理。近年來，在保持社交網(wǎng)絡(luò)數(shù)據(jù)可用性的同時，如何保護(hù)用戶隱私成為一個嚴(yán)峻的問題[1]。目前社交網(wǎng)絡(luò)的隱私保護(hù)研究主要集中在節(jié)點保護(hù)[2]和邊保護(hù)[3-5]，保護(hù)社交網(wǎng)絡(luò)中的用戶身份和用戶間的敏感關(guān)系不被發(fā)現(xiàn)。而權(quán)值是社交網(wǎng)絡(luò)的一種重要特性，權(quán)值保護(hù)具有重要意義[6]。

權(quán)值需要保護(hù)主要有兩方面原因，一是權(quán)值本身是敏感信息[7]，例如在一個商業(yè)交易社交網(wǎng)絡(luò)中，節(jié)點代表不同的交易者，兩個節(jié)點之間邊的權(quán)值是交易者之間的交易金額，交易金額是隱私信息，需要對該信息進(jìn)行保護(hù)[8]。另一種原因是權(quán)值可以作為攻擊者的背景知識，例如在社交網(wǎng)絡(luò)中，節(jié)點的身份是敏感的，利用權(quán)值可以推斷社交網(wǎng)絡(luò)的節(jié)點身份，此時也需要對權(quán)值進(jìn)行保護(hù)。最小生成樹是圖論中的經(jīng)典問題，具有重要應(yīng)用價值，保護(hù)社交網(wǎng)絡(luò)權(quán)值隱私的同時保證社交網(wǎng)絡(luò)的最小生成樹不變可以有效提高社交網(wǎng)絡(luò)的數(shù)據(jù)可用性。

目前社交網(wǎng)絡(luò)的權(quán)值保護(hù)研究主要有兩種方向，一是通過改變權(quán)值，保護(hù)節(jié)點或邊的身份，Skarkala等人[9]利用結(jié)點k-匿名機制，保護(hù)邊的權(quán)重的同時將用戶身份泄露概率降至1/k以內(nèi)。文獻(xiàn)[10]基于k-匿名思想，提出了一種k-權(quán)值模型，該模型確保匿名圖中任意節(jié)點至少存在k-1個節(jié)點與其權(quán)值屬性相同，從而保護(hù)節(jié)點身份文獻(xiàn)。文獻(xiàn)[11]在文獻(xiàn)[10]的基礎(chǔ)上提出了一種泛化模型，進(jìn)一步保留了社交網(wǎng)絡(luò)的一些基于權(quán)值的統(tǒng)計信息。另一種是不考慮節(jié)點和邊的身份保護(hù)，保護(hù)權(quán)值的同時盡量保持社交網(wǎng)絡(luò)的某些線性屬性不變，從而提高社交網(wǎng)絡(luò)的數(shù)據(jù)可用性。如Das等人在文獻(xiàn)[12]中提出一種線性規(guī)劃模型，使用不等式組約束權(quán)值，對邊的權(quán)值提供隱私保護(hù)的同時保持圖的最短路徑等線性屬性。Liu等人在文獻(xiàn)[13]提出權(quán)值保護(hù)方案，同時保護(hù)節(jié)點間的最短路徑盡量不變。為解決現(xiàn)有社交網(wǎng)絡(luò)權(quán)值保護(hù)的不足，本文提出了兩種社交網(wǎng)絡(luò)權(quán)值保護(hù)方案，一種可以保護(hù)動態(tài)社交網(wǎng)絡(luò)的權(quán)值，另一種可以在保護(hù)靜態(tài)社交網(wǎng)絡(luò)權(quán)值安全的同時，保持其最小生成樹不變。

1 預(yù)備知識

本文將社交網(wǎng)絡(luò)形式化定義為：G={V,E,W},節(jié)點集V={v1,v2,…,vn}代表社交網(wǎng)絡(luò)的實體，vi可以代表個體、機構(gòu)等，邊集E={(vi,vj)|1≤i,j≤n,i≠j}代表社交網(wǎng)絡(luò)實體間的社交連接關(guān)系，ei,j代表連接節(jié)點vi和vj之間的邊，權(quán)值集W={(wij)|1≤i,j≤n,i≠j}代表社交網(wǎng)絡(luò)的權(quán)值集合，權(quán)值wij代表邊ei,j的權(quán)值，用變量n和m表示節(jié)點和邊的數(shù)量。圖1(a)顯示了一個有權(quán)社交網(wǎng)絡(luò)的抽象結(jié)構(gòu)模型圖。

本文用T表示社交網(wǎng)絡(luò)的最小生成樹（Minimum Spanning Tree，MST）邊集，公式wT=∑wij(eij∈T)來計算社交網(wǎng)絡(luò)的最小生成樹的權(quán)值和，圖1(a)所示的社交網(wǎng)絡(luò)MST邊集T={e1,2,e1,3,e1,6,e4,6,e5,6}，最小生成樹的權(quán)值和wT=88。擾動后的社交網(wǎng)絡(luò)表示為G*={V*,E*,W*}，w*ij表示擾動后節(jié)點vi和vj間的邊權(quán)值，T*表示擾動后的社交網(wǎng)絡(luò)最小生成樹邊集表示擾動后的社交網(wǎng)絡(luò)最小生成樹的權(quán)值和。

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

2 權(quán)值保護(hù)策略

本文介紹兩種權(quán)值保護(hù)算法：高斯隨機擾動算法和貪心擾動算法，高斯隨機擾動可以簡單有效地保護(hù)權(quán)值信息不被泄露。貪心擾動算法適應(yīng)于靜態(tài)社交網(wǎng)絡(luò)，可以保證貪心擾動后的社交網(wǎng)絡(luò)最小生成樹結(jié)構(gòu)和權(quán)值和不發(fā)生改變。

2.1 高斯隨機擾動策略

W是社交網(wǎng)絡(luò)G的權(quán)值集合，當(dāng)兩個節(jié)點間有邊連接，wij的值是邊ei,j的權(quán)值，當(dāng)兩個節(jié)點間沒有邊連接，則值為0，表示擾動后邊的權(quán)值，N(0,δ2)代表一個n*n的對稱高斯隨機噪聲矩陣，該高斯矩陣均值為0，標(biāo)準(zhǔn)偏差為δ，高斯隨機擾動算法對每條邊的權(quán)值擾動策略為：

其中xi,j是滿足高斯隨機分布函數(shù)N(0,δ2)的隨機數(shù)，圖1(a)所示的社交網(wǎng)絡(luò)使用高斯隨機矩陣N(0,0.152)(δ=0.15)進(jìn)行權(quán)值擾動后，得到的社交網(wǎng)絡(luò)如圖1(b)所示。

相比原社交網(wǎng)絡(luò)G，高斯擾動后的社交網(wǎng)絡(luò)G*結(jié)構(gòu)未發(fā)生改變，即V=V*，E=E*，改變的僅僅是權(quán)值。高斯隨機擾動策略中，擾動后的社交網(wǎng)絡(luò)邊的權(quán)值之和能保持在一定范圍內(nèi)，那么社交網(wǎng)絡(luò)的很多線性屬性（如最短路徑長度等）接近原始值，保證了數(shù)據(jù)可用性。本節(jié)利用最小生成樹的權(quán)值和證明，證明過程如下：

定理1高斯隨機擾動策略中，

將上式左右分別相加可得

利用上述不等式的概率函數(shù)，可得

從前文可知，高斯隨機擾動算法復(fù)雜度低，適用于動態(tài)社交網(wǎng)絡(luò)權(quán)值保護(hù)，但是高斯隨機擾動后的社交網(wǎng)絡(luò)，很多基于權(quán)值的應(yīng)用不能完全保持，如最小生成樹的結(jié)構(gòu)發(fā)生了改變，最小生成樹的權(quán)值和也由88變?yōu)?2。最小生成樹作為社交網(wǎng)絡(luò)中一種常見應(yīng)用，其變化會影響社交網(wǎng)絡(luò)的數(shù)據(jù)可用性，本文為保護(hù)擾動后的社交網(wǎng)絡(luò)最小生成樹不變，進(jìn)一步提出了貪心擾動算法。

2.2 貪心擾動策略

貪心擾動算法的實現(xiàn)目標(biāo)是生成社交網(wǎng)絡(luò)G*={V*,E*,W*}，并且滿足以下條件：

（ⅰ）T*=T，即擾動后的最小生成樹包含的邊集不變；

考慮到保護(hù)社交網(wǎng)絡(luò)的最小生成樹不變，并不是所有節(jié)點間的權(quán)值都不能改變，設(shè)計貪心擾動算法時，對社交網(wǎng)絡(luò)的邊進(jìn)行分類處理，將原社交網(wǎng)絡(luò)G中的邊集E分為兩類：不屬于最小生成樹的邊和屬于最小生成樹的邊。

定義1若邊ei,j不屬于最小生成樹邊集T，邊ei,j定義為非歸屬邊（ei,j?T）。

原始社交網(wǎng)絡(luò)的最小生成樹邊集T={e1,2,e1,3,e1,6,e4,6,e5,6}，則邊e2,4,e3,5,e4,5是非歸屬邊。對于非歸屬邊ei,j，將其權(quán)值任意加上一個隨機正值r，即實現(xiàn)那么最小生成樹的結(jié)構(gòu)不會發(fā)生變化，并且最小生成樹的權(quán)值和也不受影響，即圖2(a)顯示了一種社交網(wǎng)絡(luò)非歸屬邊進(jìn)行貪心擾動的過程，可見對社交網(wǎng)絡(luò)的非歸屬邊進(jìn)行擾動不會影響最小生成樹。

圖2 貪心擾動策略

定義2若邊ei,j屬于最小生成樹邊集T，邊ei,j定義為歸屬邊（ei,j∈T）。

圖1(a)所示的原社交網(wǎng)絡(luò)最小生成樹邊集T={e1,2,e1,3,e1,6,e4,6,e5,6}，則邊e1,2,e1,3,e1,6,e4,5,e4,6均為歸屬邊，對于社交網(wǎng)絡(luò)的歸屬邊，有兩種改變策略。

（?。┰龃蟛呗?/p>

對于歸屬邊ei,j，可以將它的權(quán)值加上一個隨機值，新的權(quán)值，r需要滿足其中是社交網(wǎng)絡(luò)G-的最小生成樹的權(quán)值，G-表示社交網(wǎng)絡(luò)G刪除邊ei,j和權(quán)值wi,j后的社交網(wǎng)絡(luò)G-={V,{E-ei,j},{W-wi,j}}，由于所以對某一歸屬邊ei,j采取增大策略后，MST邊集不會發(fā)生變化，而權(quán)值和會增大，即如圖 2(b)，歸屬邊e1,3=10，wT=88，，則r可取值5，那么對歸屬邊采用增大策略進(jìn)行擾動后的社交網(wǎng)絡(luò)G*中，

（ⅱ）減小策略

圖3顯示了貪心擾動前后的社交網(wǎng)絡(luò)，由圖可見，經(jīng)過上述貪心擾動后生成的社交網(wǎng)絡(luò)G*，其最小生成樹結(jié)構(gòu)不會發(fā)生變化，即T*=T，最小生成樹的權(quán)值也未發(fā)生變化，即

圖3 貪心擾動后社交網(wǎng)絡(luò)

2.3 算法分析

本文針對權(quán)值保護(hù)提出了兩種擾動算法：高斯隨機擾動和貪心擾動。高斯隨機擾動的過程是將每條邊的權(quán)值乘上一個高斯隨機數(shù)，如果社交網(wǎng)絡(luò)是動態(tài)的，那么對于后續(xù)新添進(jìn)的邊也做如此操作，由于本文假設(shè)社交網(wǎng)絡(luò)中邊的數(shù)量是m，所以高斯隨機擾動的時間復(fù)雜度是O(m)。對于貪心擾動算法，需要對社交網(wǎng)絡(luò)中的每一條邊采取增大邊權(quán)值或者減小邊權(quán)值策略進(jìn)行擾動，所以貪心擾動的時間復(fù)雜度也是O(m)，兩種算法的時間復(fù)雜度相同。

3 實驗與分析

3.1 實驗數(shù)據(jù)集

實驗所用數(shù)據(jù)集是數(shù)據(jù)集EIES Acquaintanceship at time 2，該數(shù)據(jù)集常用于有權(quán)社交網(wǎng)絡(luò)分析，由Freeman等[15]收集，包含早期參加電子信息交換影響研究的若干研究者以及他們之間電子郵件的聯(lián)系。數(shù)據(jù)集邊上的權(quán)值代表他們之間的關(guān)系親密度，由于該數(shù)據(jù)集是有向社交網(wǎng)絡(luò)，本文在實驗前將該社交網(wǎng)絡(luò)變換為無向社交網(wǎng)絡(luò)，生成實驗需要的數(shù)據(jù)集。

3.2 實驗結(jié)果分析

社交網(wǎng)絡(luò)的權(quán)值保護(hù)研究中，文獻(xiàn)[12]提出了一種線性規(guī)劃模型（linear programming，LP），該模型能有效保護(hù)社交網(wǎng)絡(luò)的權(quán)值，并且保證變化后的社交網(wǎng)絡(luò)最小生成樹盡量不變，本文實驗部分將高斯隨機擾動算法、貪心擾動算法與LP算法相比較，驗證本文高斯擾動和貪心擾動算法的性能。試驗從隱私保護(hù)性能、數(shù)據(jù)可用性和算法復(fù)雜度三方面比較。

3.2.1 隱私保護(hù)性能分析

高斯隨機擾動、貪心擾動和LP算法均采用隨機值對社交網(wǎng)絡(luò)權(quán)值進(jìn)行保護(hù)，高斯擾動算法中，權(quán)值乘上一個高斯隨機數(shù)，改變后的權(quán)值相比較原始權(quán)值的變化范圍在[-δ,δ]、[-2δ,2δ]、[-3δ,3δ]的概率分別近似于0.68、0.95、0.997。貪心擾動算法通過加減一個大于0的隨機值改變權(quán)值，隨機值r的取值取決于原社交網(wǎng)絡(luò)的權(quán)值，真實權(quán)值被預(yù)測的概率根據(jù)隨機值的大小變化而變化。LP算法中，通過一系列不等式組來約束隨機值的大小，真實權(quán)值被預(yù)測的概率取決于不等式的約束條件。這三種算法處理后的社交網(wǎng)絡(luò)，真實權(quán)值被預(yù)測的概率不定，取決于所選隨機值的大小，高斯隨機算法處理后的權(quán)值在一定范圍變化，在隱私保護(hù)強度上略低于貪心擾動算法和LP算法。這三種算法處理后的社交網(wǎng)絡(luò)真實權(quán)值被保護(hù)，具體的保護(hù)強度根據(jù)隨機值不同而改變。

3.2.2 數(shù)據(jù)可用性分析

本文對社交網(wǎng)絡(luò)的權(quán)值進(jìn)行保護(hù)時，未改變社交網(wǎng)絡(luò)的結(jié)構(gòu)，所以試驗選擇最小生成樹的權(quán)值和來衡量社交網(wǎng)絡(luò)變化后的數(shù)據(jù)可用性。

圖4顯示了經(jīng)過貪心擾動算法、高斯隨機擾動算法和LP算法保護(hù)后的社交網(wǎng)絡(luò)MST權(quán)值和與原始社交網(wǎng)絡(luò)MST權(quán)值和的比較，由圖4可以看出，貪心擾動后的社交網(wǎng)絡(luò)MST權(quán)值和始終與原始社交網(wǎng)絡(luò)保持一致，而高斯隨機擾動算法和LP算法會造成最小生成樹權(quán)值和的變化。高斯隨機擾動最終的權(quán)值和與原始社交網(wǎng)絡(luò)的權(quán)值和變化控制在一定范圍內(nèi)，MST結(jié)構(gòu)可能變化。貪心擾動算法的目標(biāo)是保證MST的結(jié)構(gòu)與權(quán)值和不變。LP算法利用一系列不等式組對權(quán)值變化進(jìn)行約束，保證生成的社交網(wǎng)絡(luò)最小生成樹結(jié)構(gòu)不變，但是權(quán)值和有可能變化。因此，貪心擾動算法和LP算法均能保證變化后的社交網(wǎng)絡(luò)MST的結(jié)構(gòu)不發(fā)生改變，而高斯擾動算法處理后的社交網(wǎng)絡(luò)最小生成樹有可能發(fā)生變化，在數(shù)據(jù)可用性方面，貪心算法的性能最優(yōu)。

圖4 最小生成樹權(quán)值和比較

3.2.3 算法復(fù)雜度分析

圖5顯示了3種算法在處理數(shù)據(jù)集時所耗費的時間，從實驗結(jié)果來看，高斯隨機擾動耗時最短，貪心擾動耗時次之，LP算法耗時最長。從上文的算法時間復(fù)雜度分析可知，高斯隨機擾動和貪心擾動的時間復(fù)雜度是O(m)，而文獻(xiàn)[12]中的LP算法的時間復(fù)雜度是O(dm)，其中d是m條邊的平均度?？梢灶A(yù)見，隨著數(shù)據(jù)集的不斷增大，LP算法耗時相比本文算法耗時的差距會越來越大，所以本文所提算法在時間復(fù)雜度方面也表現(xiàn)出了優(yōu)越性，而且在算法效率上，高斯隨機擾動算法比貪心擾動算法更優(yōu)。

圖5 算法運行時間

4 結(jié)束語

本文介紹了兩種權(quán)值保護(hù)算法，高斯隨機擾動算法實現(xiàn)簡單，能夠有效保護(hù)動態(tài)社交網(wǎng)絡(luò)的權(quán)值，但是經(jīng)過高斯隨機擾動后的社交網(wǎng)絡(luò)，很多基于權(quán)值的應(yīng)用會發(fā)生變化，針對社交網(wǎng)絡(luò)中的最小生成樹應(yīng)用，本文提出了貪心擾動算法，貪心擾動能保護(hù)靜態(tài)社交網(wǎng)絡(luò)的權(quán)值不被泄露，同時保證擾動后的社交網(wǎng)絡(luò)最小生成樹不變，保證社交網(wǎng)絡(luò)的數(shù)據(jù)可用性。但貪心擾動策略需要提前獲得社交網(wǎng)絡(luò)的全部權(quán)值信息，無法有效應(yīng)用于動態(tài)社交網(wǎng)絡(luò)權(quán)值保護(hù)。在保持社交網(wǎng)絡(luò)高數(shù)據(jù)可用性的同時，如何有效保護(hù)動態(tài)社交網(wǎng)絡(luò)權(quán)值仍待進(jìn)一步研究。

[1]Liu P,Li X.An improved privacy preserving algorithm for publishing social network data[C]//IEEE International Conference on High Performance Computing and Communications,2013:888-895.

[2]劉向宇，王 斌，楊曉春.社會網(wǎng)絡(luò)數(shù)據(jù)發(fā)布隱私保護(hù)技術(shù)綜述[J].軟件學(xué)報，2014，25（3）：576-590．

[3]Fogues R,Such J M,Espinosa A A.Open challenges in Relationship-Based privacy mechanisms for social network services[J].International Journal of Human-Computer Interaction,2015,31(5):350-370.

[4]Zheleva E,Getoor L.Preserving the privacy of sensitive relationships in graph data[C]//Proceedings of the 1st ACM SIGKDD Workshop on Privacy,2007:153-171.

[5]Bazarova N N,Choi Y H.Self‐disclosure in social media:Extending the functional approach to disclosure motivations and characteristics on social network sites[J].Journal of Communication,2014,64(4):635-657.

[6]Liu C G,Liu I H,Yao W S,et al.K-anonymity against neighborhood attacks in weighted social networks[J].Security and Communication Networks,2015,8(18):3864-3882.

[7]谷勇浩，林九川，郭 達(dá).基于聚類的動態(tài)社交網(wǎng)絡(luò)隱私保護(hù)方法[J].通信學(xué)報，2015，36（Z1）：126-130．

[8]Wang S L,Tsai Y C,Kao H Y,et al.SHORTEST PATHS ANONYMIZATION ON WEIGHTED GRAPHS[J].International Journal of Software Engineering and Knowledge Engineering,2013,23(1):65-79.

[9]Skarkala M E,Maragoudakis M,Gritzalis S，et al.Privacy preservation by k-anonymization of weighted social networks[C]//IEEE/ACM international conference on advances in social networks analysis and mining,2012:423-428.

[10]Li Y,Shen H.Anonymizing graphs against weightbased attacks[C]Data Mining Workshops(ICDMW),2010 IEEE International Conference on.IEEE,2010:491-498.

[11]Liu X,Yang X.Ageneralization based approach for anonymizing weighted social network graphs[M]Web-Age Information Management.Springer Berlin Heidelberg,2011:118-130.

[12]Das S,E?ecio?lu O,El A A.Anonymizing weighted social network graphs[C]//IEEE 26th International Conference on,2010:904-907.

[13]Liu L,Wang J,Liu J,et al.Privacy preserving in social networks against sensitive edge disclosure，University of Kentucky,KY[R],2008.

[14]Stigler S M.Statistics on the table:The history of statistical concepts and methods[M].Harvard University Press,2002.

[15]Freeman L C,Freeman S C.A semi-visible college:structural effects on a social networks group.Electronic Communication:Technology and Impacts Boulder,Westview Press,1980:77-85.

Perturbation-based privacy preserving method in social networks

FAN Guo-ting,YANG Ying,SUN Gang,ZHAO Jia
(School of Computer and Information Engineering,Fuyang Normal University,Fuyang Anhui236041,China)

Perturbation methods are crucial privacy-protecting approaches for social networks.The Gaussian perturbing randomly algorithm and greedy perturbation algorithm were put forward for the weights protection of the social networks.Gaussian perturbing randomly algorithm was simple to protect the weights of dynamic social networks.The edges were classified in the greedy perturbation algorithm,so that make minimum spanning tree same,meanwhile which can protect the weight privacy in static social networks.Experiment results show that two algorithms can effectively protect the weight information in social networks.The Gaussian perturbing randomly algorithm is fit for dynamic social networks while greedy perturbation algorithm can better protect static social networks.

social network；privacy preserving；perturbation；weight

TP309文獻(xiàn)識別碼：A

1004-4329（2017）04-055-06

10.14096/j.cnki.cn34-1069/n/1004-4329（2017）04-055-06

2017-07-25

安徽省高校省級重點科研項目（KJ2017A332，KJ2016A549）資助。

范國婷(1985－ )，女，碩士，助教，研究方向：信息安全域隱私保護(hù)。