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

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

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

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

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

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

社交網(wǎng)絡；隱私保護；擾動；權值

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

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

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

1 預備知識

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

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

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

2 權值保護策略

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

2.1 高斯隨機擾動策略

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

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

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

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

將上式左右分別相加可得

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

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

2.2 貪心擾動策略

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

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

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

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

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

圖2 貪心擾動策略

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

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

（ⅰ）增大策略

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

（ⅱ）減小策略

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

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

2.3 算法分析

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

3 實驗與分析

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

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

3.2 實驗結果分析

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

3.2.1 隱私保護性能分析

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

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

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

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

圖4 最小生成樹權值和比較

3.2.3 算法復雜度分析

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

圖5 算法運行時間

4 結束語

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

[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)絡數(shù)據(jù)發(fā)布隱私保護技術綜述[J].軟件學報，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]谷勇浩，林九川，郭 達.基于聚類的動態(tài)社交網(wǎng)絡隱私保護方法[J].通信學報，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文獻識別碼：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－ )，女，碩士，助教，研究方向：信息安全域隱私保護。