基于敏感關系的社會網絡隱私保護方法

申艷光，閆晶星＋，買建英，范永健

（1.河北工程大學 信息與電氣工程學院，河北 邯鄲056038；2.解放軍炮兵訓練基地，河北 宣化075100）

0 引 言

用戶隱私信息的非法出售、假冒身份欺詐、社會網站本身存在的漏洞及第三方應用程序的植入等對用戶的個人隱私造成了嚴重的威脅。由于社會網絡的復雜性，攻擊者可能具有大量的背影知識，同時抵御多種類型攻擊的隱私保護成為研究熱點。

目前，社會網絡中節(jié)點間的連接關系可能導致的隱私泄露問題［1，2］受到了人們的廣泛關注。Gao等［3］將兩結點之間的邊連接視為隱私信息，保證在不得知結點之間邊連接情況的同時準確地計算任意兩點之間的最短路徑長度。針對節(jié)點連接關系和社會網絡圖結構可能造成的隱私信息泄露問題，楊俊等［4］提出了一種基于圖自同構的k－Secure社會網絡隱私保護模型，從而有效防止節(jié)點識別、邊識別和路徑長度泄露等隱私攻擊。已有的社會網絡隱私保護大部分只針對單一關系的社會網絡，由于社會網絡的特殊性，多關系的社會網絡中多數(shù)據(jù)類型的隱私保護同樣受到人們的重視。Zhelea等［5］針對單類型節(jié)點多類型邊進行了匿名化處理。（k，2）－匿名模型［6］、l－敏感邊匿名模型［7］等都對節(jié)點間的敏感關系進行了隱私保護。Zheleva等［8］通過現(xiàn)有邊連接間的敏感關系計算節(jié)點間具有敏感關系的概率，實現(xiàn)對被刪除敏感邊的恢復。Campan等［9］提出了p－敏感k－匿名模型。南麗麗等［10］提出了一種基于信息混淆的社會網絡隱私保護機制。王小號等［11］針對攻擊者以社會個體領域信息作為背景知識進行敏感邊識別的攻擊，提出了基于譜約束的敏感區(qū)劃分隨機擾動方法。張健沛等［12］針對等價類與數(shù)據(jù)表間敏感屬性分布的穩(wěn)定性，提出了一種SABuk tcloseness模型。吳宏偉等［13］提出了一種抗復合攻擊的 （k，l）－匿名發(fā)布算法，有效解決了抵御復合攻擊的問題。但是，以上匿名方法并沒有考慮抵御社會網絡中存在的節(jié)點間敏感關系和社會網絡圖結構造成的隱私信息泄露問題。

本文針對社會網絡中敏感邊攻擊、節(jié)點度攻擊和朋友連接攻擊同時存在的問題，提出了一種面向含敏感關系的（k2，l）－匿名模型。

1 面向含敏感關系的 （k2，l）－匿名模型

為了便于研究，社會網絡通常被抽象為圖結構，利用較為成熟的圖論知識對社會網絡進行研究。實際生活中存在多種不同類型的復雜的社會網絡，本文針對含敏感關系的社會網絡進行研究。含敏感關系的社會網絡圖定義如下：

定義1 含敏感關系的社會網絡：社會網絡圖G＝（V，E，T）。其中，V 表示節(jié)點，E 表示節(jié)點間的關系，T表示邊的類型，若T 為1，則表示E 為敏感關系；T 為0，則表示E非敏感關系。

社會網絡中含敏感邊，首先通過添加非敏感邊構建l－敏感邊匿名模型，然后通過添加非敏感邊實現(xiàn) （k2，l）－匿名模型。

定義2 l－敏感邊匿名模型：給定一個圖G＝ （V，E，T），若節(jié)點v有敏感關系，至少存在l個節(jié)點與節(jié)點v 有敏感關系，那么該圖滿足l－敏感邊匿名模型。

定義3 （k2，l）－匿名模型：給定一個圖G＝（V，E，T），對圖中任意具有度對為d2＝ （d1，d2）事件邊的節(jié)點v，至少存在k－1個其它節(jié)點和v具有一個相同度對的事件邊；且若節(jié)點v有敏感關系，則至少存在l個其它節(jié)點與節(jié)點v有敏感關系。那么該圖滿足（k2，l）－匿名模型。

分別通過添加敏感邊和非敏感邊構建匿名模型，社會網絡圖的可用性會降低，本文通過節(jié)點的度衡量社會網絡圖的匿名損失，社會網絡圖匿名信息損失量定義如下：

定義4 匿名度信息損失量：匿名圖G＊與原始圖G 總的度差稱為匿名度信息損失量，定義為式 （1）

式 中：d（G＊）（i）—— （k2，l）－匿 名 圖 節(jié) 點i 的 度，G＊—— （k2，l）－匿名圖；d（G’）（i）——l－敏感邊匿名圖節(jié)點i的度，G’——l－敏感邊匿名圖；n——圖中的節(jié)點數(shù)。

2 面向含敏感關系的 （k2，l）－匿名化方法

本節(jié)首先介紹含敏感關系的 （k2，l）－匿名化方法，然后介紹具體的實現(xiàn)算法。

2.1 面向含敏感關系的 （k2，l）－匿名化

根據(jù) （k2，l）－匿名化要求。首先，對網絡中的節(jié)點添加敏感邊，使每個含敏感關系的節(jié)點至少與l個節(jié)點相連。然后，在滿足l－敏感邊匿名模型的基礎上，提出了基于動態(tài)規(guī)劃的度序列匿名算法 （dynamic programming degree sequence anonymization，DPDSA）和基于貪心算法的度序列匿名算法 （greedy algorithm degree sequence anonymization，GADSA），構建 （k2，l）－匿名模型。度序列匿名算法的基本思想如圖1所示。

圖1 度序列匿名算法基本思想

為了降低匿名成本，在添加敏感邊的過程中首先選擇與不滿足l－敏感邊匿名模型且含有敏感關系的節(jié)點相連，其中l(wèi)的值根據(jù)用戶所需的隱私保護程度而定。在添加非敏感邊時選擇的節(jié)點應遵循以下3個準則：

（1）一個節(jié)點沒有和另一個組中的任何節(jié)點相連；

（2）兩個節(jié)點分別在各自組中度最小；

（3）在兩組節(jié)點中兩點之間路徑最短的節(jié)點。

2.2 算法實現(xiàn)

本節(jié)介紹具體的 （k2，l）－匿名模型實現(xiàn)算法，分為3個主要模塊進行介紹：動態(tài)規(guī)劃分組算法、貪心算法分組算法和構建 （k2，l）－匿名模型算法。

2.2.1 動態(tài)規(guī)劃求分組節(jié)點算法

提取每個節(jié)點的度，按節(jié)點的度降序排列。采用動態(tài)規(guī)劃的分組策略根據(jù)度的相似性進行分組，每個組至少包含k個節(jié)點并將每個組中節(jié)點最大的度作為本組的目標度dx。

算法1：動態(tài)規(guī)劃求分組節(jié)點算法

輸入：滿足l－敏感邊匿名化G’的鄰接矩陣A 和各節(jié)點的度矩陣C；匿名化參數(shù)k；

輸出：分界點矩陣TZ；分組后節(jié)點矩陣TZ

2.2.2 貪心算法求分組節(jié)點算法

在滿足l－敏感邊匿名模型的基礎上，根據(jù)節(jié)點度的大小，按節(jié)點度從大到小進行排序，采用貪心策略根據(jù)節(jié)點度進行分組，使得每個組至少包含k個節(jié)點。

貪心算法首先將遞減度序列的前k 個節(jié)點劃分為一組，然后依次判斷下一個節(jié)點是否合并到前面已經形成的分組或者是否作為一個新組的開頭。判斷的依據(jù)為比較以下兩個匿名度的損失

式中：II（i，j）——將i到j 的所有節(jié)點均變?yōu)閕節(jié)點度的匿名損失度。若KK＜＝KKX，則第 （w＋k＋1）個節(jié)點歸到前面的分組；若相反，則作為一組新的開頭，依次類推，直到處理完所有節(jié)點。具體的貪心算法求分組節(jié)點算法如算法2所示。

算法2：貪心算法求分組節(jié)點算法

輸入：滿足l－敏感邊匿名化G’的鄰接矩陣A 和各節(jié)點的度矩陣C；匿名化參數(shù)k；

1.［x，y］＝sort（C，’descend’）

2.計算將所有節(jié)點都變?yōu)槟繕硕葧r的度差矩陣II

3.FOR（w＝ （k＋1）：length（x）－k－1）%貪心算法求分界點

輸出：分界點矩陣TZ；分組后節(jié)點矩陣TZ

2.2.3 （k2，l）－匿名算法

在滿足l－敏感邊匿名模型的基礎上，首先利用動態(tài)規(guī)劃算法求得分組的分界點。然后，通過添加非敏感邊，使每兩個組之間至少有k 個節(jié)點相連。最后，找到每組中節(jié)點度與目標度差最大的節(jié)點，添加非敏感邊，直到每個組中的節(jié)點滿足步驟每組選擇的目標度，使分組滿足 （k2，l）－匿名模型?；谏鲜鲇懻?，設計了基于動態(tài)規(guī)劃的度序列匿名算法構建 （k2，l）－匿名模型，具體的算法描述如算法3所示。

算法3：（k2，l）－匿名算法

輸入：含敏感邊的社會網絡G 的鄰接矩陣result；整數(shù)l；

3 實驗結果及分析

本實驗運行環(huán)境為：Microsoft Windows 7Professional操作系統(tǒng)，2GB 內存，2.26GHz CPU，采用Matlab編程實現(xiàn)。

本文采用Pajek 軟件 （http：／／vlado.fmf.uniljsi／pub／networks／pajek／）生成的包含多類型邊的社會網絡圖作為本文實驗數(shù)據(jù)集。社會網絡圖中包含節(jié)點數(shù)｜V｜＝380，邊的數(shù)量｜E｜＝630。邊的類型分別為同學關系、朋友關系、家人關系3種，本文將家人關系看作節(jié)點間的敏感關系。本實驗對實現(xiàn)不同匿名模型的運行時間進行了對比分析。通過改變社會網絡圖的匿名化參數(shù)，對通過不同匿名算法實現(xiàn)匿名后的社會網絡度信息損失和其性能進行分析對比。

3.1 執(zhí)行時間分析

如圖2為k＝5，l＝2時基于動態(tài)規(guī)劃和貪心算法實現(xiàn)3種不同匿名模型的運行時間比較。從以下兩圖中均可看出，實現(xiàn) （k2，l）－匿名模型比實現(xiàn)其它兩個匿名模型時間較長，因為 （k2，l）－匿名算法在滿足這兩個匿名模型的基礎上，要求每兩組之間至少有k個節(jié)點相連，若隨機的添加非敏感邊，運行時間會減少，卻以大量的度信息損失為代價。所以在添加邊時通過找到度差最大的節(jié)點添加非敏感邊，以提高匿名圖的可用性。隨著數(shù)據(jù)集的增大、節(jié)點數(shù)的增多，運行時間也會越來越長。圖2 （b）中運行時間比圖2 （a）中運行時間較短，在考慮運行時間的同時還要考慮使用不同算法匿名后社會網絡圖的可用性。以下通過3個方面根據(jù)不同匿名參數(shù)比較兩種算法的可用性，同時對不同匿名模型匿名后的社會網絡圖可用性進行了分析比較。

圖2 不同匿名算法的CPU 運行時間對比

3.2 匿名圖的度信息損失分析

在本文的算法中，通過匿名圖的度信息損失表示匿名成本。圖3、圖4為分別通過動態(tài)規(guī)劃和貪心算法實現(xiàn)不同匿名模型的匿名成本隨k值變化的情況。圖3、圖4 （a）和（b）中分別給出了當l為2和3時，各算法的匿名成本隨k值變化的情況。當l一定時，隨著k值的逐漸增大，匿名度信息損失呈上升趨勢，而k－匿名的匿名成本要遠小于其它兩種匿名算法，但是k－匿名算法只能抵御度的攻擊； （k，l）－匿名算法和（k2，l）－匿名算法的匿名度信息損失在k值較小的情況下不相上下，隨著k值的增大，（k2，l）－匿名度信息損失要略微高于 （k，l）－匿名算法的度信息損失。當l＝3時，3種匿名算法的匿名成本要大于l為2時的情況。

在圖5 中，對通過動態(tài)規(guī)劃和貪心算法實現(xiàn) （k2，l）－匿名模型的匿名度信息損失進行了比較，在k 值小于6時，兩種算法的匿名度信息損失上下相當。在k值大于6時，動態(tài)規(guī)劃實現(xiàn)匿名模型的度信息損失要小于貪心算法。并且隨著k值的不斷增大，動態(tài)規(guī)劃的優(yōu)勢越來越明顯。隨著k值和l值的不斷增大，社會網絡圖的匿名效果會越來越好，而社會網絡圖的可用性會隨之降低。所以，用戶可以根據(jù)自己不同的需求，調整l和k 的值，達到滿意的匿名程度。

圖3 動態(tài)規(guī)劃實現(xiàn)不同匿名模型隨k值變化的度信息損失

圖4 貪心算法實現(xiàn)不同匿名模型隨k值變化的度信息損失

圖5 不同算法的 （k2，l）－匿名模型隨k值變化的度信息損失

3.3 平均最短路徑差值分析

圖6、圖7 （a）和 （b），為l分別等于2和3時，平均最短路徑差值隨k值變化的情況。當l一定時，k－匿名的平均最短路徑差值要小于其它兩個算法的值，隨著k 值不斷增大，3種匿名社會網絡圖的差值呈緩慢上升趨勢， （k2，l）－匿名圖的平均最短路徑差值要略大于 （k，l）－匿名圖的平均最短路徑差值。而 （k，l）匿名圖和 （k2，l）－匿名圖的差值都要大于k－匿名圖。

圖8中兩種算法實現(xiàn) （k2，l）－匿名模型的平均路徑差值進行了對比。在k 小于6的情況下，兩種算法的平均最短路徑差值基本相同，在k 大于6的情況下，隨著k 值的增大，基于貪心算法的平均路徑差值上升趨勢逐漸加快。

3.4 聚類系數(shù)差值分析

圖9、圖10 （a）和 （b），為l分別等于2和3時，聚類系數(shù)差值隨k值的變化情況。在圖9 （a）和圖9 （b）可以看出，k－匿名模型的聚類系數(shù)差值遠小于其它兩種匿名模型的差值。在l一定的情況下，隨著k值的不斷增大，聚類系數(shù)差值呈上升趨勢，（k2，l）－匿名圖的聚類系數(shù)差值與 （k，l）－匿名圖差值相差較小，隨著k 值不斷增大，網絡圖的可用性也隨之降低。

圖6 動態(tài)規(guī)劃實現(xiàn)不同匿名模型隨k值變化的平均路徑差值

圖7 貪心算法實現(xiàn)不同匿名模型隨k值變化的平均路徑差值

圖8 不同算法的（k2，l）－匿名模型隨k值變化的平均路徑差值

圖9 動態(tài)規(guī)劃實現(xiàn)不同匿名模型隨k值變化的聚類系數(shù)差值

圖10 貪心算法實現(xiàn)不同匿名模型隨k值變化的聚類系數(shù)差值

圖11中，k值小于6時，貪心算法聚類系數(shù)差值較小。在k 大于6的情況下，基于動態(tài)規(guī)劃算法的聚類系數(shù)差值要較小。在k小于6的情況下，動態(tài)規(guī)劃算法并沒有太大的優(yōu)勢，隨著k 值得增加，動態(tài)規(guī)劃算法的優(yōu)勢越來越明顯，k值大于6的情況下選擇基于動態(tài)規(guī)劃算法實現(xiàn)較好。

從以上實驗結果中可看出，在k 值和l 值一定的情況下，k－匿名圖的可用性最好， （k，l）－匿名圖比 （k2，l）－匿名圖的可用性略微要好，然而 （k2，l）－匿名圖可以進一步的抵御朋友鏈接攻擊。進一步對兩種算法的不同系數(shù)差值進行分析對比，在k 值小于6的情況下動態(tài)規(guī)劃和貪心算法均可選擇，隨著k 值不斷增大，動態(tài)規(guī)劃算法的優(yōu)勢越來越明顯。

在本文中，貪心算法先將遞減度序列前k 個節(jié)點劃分為一組，均變?yōu)楸窘M的目標節(jié)點，然后考慮后續(xù)節(jié)點，只是保證了在當前狀態(tài)下的子序列是最優(yōu)的，而動態(tài)規(guī)劃算法是將所有節(jié)點可能出現(xiàn)的所有分組全部進行比較，比較完后自底向上選擇分組節(jié)點，在k 值較小的情況下，由于度序列按降序排列，每個組的節(jié)點變?yōu)楸窘M節(jié)點目標度時，每組的度損失相對k 值較大的情況下較小。所以，動態(tài)規(guī)劃算法的優(yōu)勢并不明顯，隨著k 值不斷增大，每個分組的度損失也會相差較多，則優(yōu)勢也會越來越明顯。用戶可以根據(jù)自己的不同需求，根據(jù)k值和l值的不同選擇不同的匿名算法，在保證社會網絡圖可用性較好的前提下，達到用戶滿意的匿名程度。

圖11 不同算法的（k2，l）－匿名模型隨k值變化的聚類系數(shù)差值

4 結束語

為了保證含敏感關系的社會網絡中用戶的隱私不會被同時存在的多種類型的攻擊者獲得。設計了 （k2，l）－匿名模型，可同時抵御敏感關系攻擊、節(jié)點度攻擊和朋友連接攻擊。分別通過動態(tài)規(guī)劃度序列匿名算法和貪心算法度序列匿名算法實現(xiàn) （k2，l）－匿名模型，通過比較不同匿名模型的匿名參數(shù)，證明 （k2，l）－匿名模型的可行性，并比較不同算法的匿名參數(shù)，用戶可根據(jù)不同參數(shù)選擇不同的匿名算法，實現(xiàn) （k2，l）－匿名模型。該方法不僅能夠同時抵御敏感關系攻擊、度攻擊和朋友連接攻擊，而且能夠合理地控制信息損失度。下一步的研究方向：社會網絡是不斷發(fā)展和變化的，可以考慮社會網絡的動態(tài)性；隨著網絡技術的發(fā)展，可以考慮采用并行算法對社會網絡數(shù)據(jù)進行分析處理，提高數(shù)據(jù)匿名化的有效性。

［1］Bhagat S，Cormode G，Krishnamurthy B，et al.Class－based graph anonymization for social network data［C］／／Proc of the 35th Int’l Conf on Very Large Databases，2009：766－777.

［2］LIU Xiangyu，WANG Bin.Survey on privacy preserving tech－niques for publishing social network data ［J］.Journal of Software，2014，25 （3）：142－156 （in Chinese）.［劉向宇，王斌.社會網絡數(shù)據(jù)發(fā)布隱私保護技術綜述 ［J］.軟件學報，2014，25 （3）：142－156.］

［3］Gao J，Xu JY，Jin R，et al.Neighborhood－privacy protected shortest distance computing in cloud ［C］／／Proc of the ACM SIGMOD Int’l Conf on Management of Data，2011：409－420.

［4］YANG Jun，LIU Xiangyu，YANG Xiaochun，et al.Automorphism based k－secure for privacy preserving in social network ［C］／／The 29th China Database Academic Conference，2012：264－271 （in Chinese）. ［楊俊，劉向宇，楊曉春，等.基于圖自同構的k－Secure社會網絡隱私保護方法 ［C］／／第29屆中國數(shù)據(jù)庫學術會議論文集，2012：264－271.］

［5］Zhelea E，Getdoor L.Preserving the privacy of sensitive relationships in graph data ［C］／／Proceedings of the 1st ACM SIGKDD Workshop on Privacy，Security，and Trust in KDD，2007.

［6］LAN Lihui，SUN Yinghui.Privacy preservation of sensitive edges in social networks publication ［J］.Journal of Jilin University，2011，29 （4）：324－331 （in Chinese）. ［蘭麗輝，孫英慧.社會網絡發(fā)布中敏感邊的隱私保護 ［J］.吉林大學學報，2011，29 （4）：324－331.］

［7］Li J，Han J M，Luo F W，et al.K－Sensitive edge anonymity model for sensitive relationship preservation on publishing social network ［C］／／The 3rd International Conference on Information Technology and Computer Science，2011：146－149.

［8］Zheleva E，Getoor L.Preserving the privacy of sensitive relationships in graph data ［C］／／Proc of the 1st ACM SIGKDD Workshop on Privacy，Security，and Trust in KDD，2007：153－171.

［9］Campan A，Truta T M，Cooper N.P－sensitive K－anonymity with generalization constraints［J］.Transactions on Data Privacy Journal，2010，3 （2）：65－89.

［10］NAN Lili，WU Tao.Research on information mixing－based protection mechanism in online social networks［J］.Computer Engineering and Design，2011，32 （10）：3278－3283 （in Chinese）.［南麗麗，吳濤.基于信息混淆的社會網絡隱私保護 機 制 ［J］. 計 算 機 工 程 與 設 計，2011，32 （10）：3278－3283.］

［11］WANG Xiaohao，GENG Hui.Privacy protection disturbance method of society network based on spectrum constraint and sensitive area division ［J］.Journal of Computer Applications，2013，33 （6）：1608－1611 （in Chinese）. ［王小號，耿惠.基于譜約束和敏感區(qū)劃分的社會網絡隱私保護擾動方法 ［J］.計算機應用，2013，33 （6）：1608－1611.］

［12］ZHANG Jianpei，XIE Jing.A t－closeness privacy model based on sensitive attribute values semantics bucketization ［J］.Journal of Computer Research and Development，2014，51（1）：126－137 （in Chinese）.［張健沛，謝靜.基于敏感屬性值語義桶分組的t－closeness隱私模型 ［J］.計算機研究與發(fā)展，2014，51 （1）：126－137.］

［13］WU Hongwei，ZHANG Renwei.（k，l）－anonymity for social networks publication against composite attacks ［J］.Journal of Harbin University of Science and Technology，2013，18（3）：47－53 （in Chinese）.［吳宏偉，張仁偉.抗復合攻擊的社會網絡 （k，l）匿名方法 ［J］.哈爾濱理工大學學報，2013，18 （3）：47－53.］