具有敏感邊緣權重的加權社會網絡匿名算法

畢紅凈，盧立蕾

計算機科學與自動化技術

具有敏感邊緣權重的加權社會網絡匿名算法

畢紅凈，盧立蕾

（唐山師范學院 計算機科學系，河北 唐山 063000）

針對大型數據網絡隱私保護問題，首先構造了一個k-度匿名網絡。為保證發布數據的可用性，提出了貪心邊權重擾動（GEWP）算法，該算法通過發布網絡數據時擾亂某些邊緣的權重防止隱私泄露，同時保留原始網絡中敏感節點對之間最短路徑和路徑的長度。仿真實驗顯示的結果和理論分析相符合。

加權社會網絡；敏感邊緣權重；K-匿名；隱私保護

1 引言

社會網絡是由實體以及連接實體的邊組成的特殊圖形結構。實體或節點表示用戶，連接實體的邊緣表示這些用戶之間的關系或交互。連接實體之間的邊可用來表示金融交換、朋友關系、沖突可能性、網絡鏈接、疾病傳播（流行病學）等。第三方發布數據集之前，數據所有者必須保證用戶隱私信息不被泄露，因此，社會網絡圖的匿名化過程成為一個重要的問題。Ferri等人[1]的研究表明，盡管有一些用戶群體不介意數據擁有者共享數據，但高達90%的成員不同意這個原則。Backstrom等人[2]指出，發布實際網絡之前，刪除頂點的身份來匿名網絡的簡單技術并不能保證用戶的隱私不被泄露。事實上，攻擊者可以通過一些背景知識來推斷用戶的隱私信息。因此，為保護機密、敏感和安全信息不被披露需要加快社會網絡隱私保護技術的發展，這就需要在保護機密信息和最大化社會網絡的效用分析之間進行最佳權衡。

為了保護隱私，在不公開原始數據并且保證數據分析結果盡可能接近原始數據的前提下，已經發布了各種技術。k-anonymity模型是最具代表性的隱私保護方法。k-anonymity模型表明雖然攻擊者設法找到與匿名數據集中出現的用戶相關的外部知識，但是不能區分不同的k個記錄或個人，因此，攻擊者不能重新識別概率大于1/k的個體。k-度匿名的主要目標是所有頂點至少有k-1個其它頂點共享相同的度數。Salas等人[3]提出了一種k-degree匿名方法，保證每個近似值在度序列中至少有k個元素，當匿名度序列的度數之和為偶數時，使用歐幾里德距離得到k-degree匿名的最優解。LiuK等人[4]提出無向圖匿名概念，利用貪心策略增加邊的方法實現匿名，抵御節點度攻擊。Casas等人[5]提出UMGA算法實現K-度匿名。Chester等人[6]也考慮了k度匿名問題，但是通過在假頂點和假頂點之間添加新的邊來修改網絡結構。Bhattacharya等人[7]提出了一種迭代算法來生成給定社會網絡圖的k-匿名頂點度序列，以保護圖免受被動攻擊。Hartung等人[8]提出動態規劃和啟發式方法實現k-度匿名，提高處理大規模社會網絡無向圖的效率。Li Y等人[9]提出隨機稀疏化和隨機擾動化的手段，使用概率的方法對社會網絡無向圖進行隨機修改。Tsai等人[10-11]提出了基于加權社會網絡的k-匿名保護方法，添加和刪除社會網絡中的加權邊緣，防止攻擊者根據度數信息重新識別節點。基于層次社會機構，張曉琳等人[12]提出了一種保護鏈接關系的分布式匿名算法PLRD-(k,m)，既保證了數據的可用性，又不讓攻擊者通過度和標簽識別出目標個體。

2 背景知識與問題定義

定義1（加權社會網絡圖）用G={V,E,W}表示一個加權社會網絡圖，其中V={vi|1≤i≤n}，為圖G中節點個數，V(G)為圖G的節點集；E={ei,j}，ei,j表示節點的邊，E(G)為圖G的邊集；W={wi,j}，wi,j為邊ei,j的權重，W(G)為圖G的邊權重集合。

圖1 加權社會網絡圖

定義3（匿名度序列）如果度序列中不同節點的度數出現至少k次，則該度序列是k-匿名的，用d～表示。

定義4（匿名加權社會網絡圖G～）用G～ ={V～,E～,W～}表示一個匿名加權社會網絡圖，如果節點匿名度序列滿足k-度匿名，那么G～也是k-度匿名的。

定義5（敏感節點對） 用H表示敏感節點對(si,sj)的集合，其中si,sj∈V。敏感節點對是指需要保留節點對之間的最短路徑psi,sj以及相應的路徑長度dsi,sj，并使匿名后的路徑長度盡可能的與原始路徑長度保持一致。

定義6（未訪問邊NV）對于?(si,sj)∈H，如果evi,vj?psi,sj均成立，那么邊evi,vj為未訪問邊緣，即所有敏感節點對的最短路徑均不經過未訪問邊緣。

定義7（全訪問邊AV）對于?(si,sj)∈H，如果evi,vj∈psi,sj均成立，那么邊evi,vj為全訪問邊緣，即所有敏感節點對的最短路徑均經過全訪問邊緣。

定義8（部分訪問邊PV）對于?(si,sj)∈H，(sk,sl)?H，如果evi,vj∈psi,sj，evi,vj?psk,sl，那么邊evi,vj為部分訪問邊緣，所有敏感節點對的最短路徑只有一部分經過部分訪問邊緣。

如圖1所示的加權社會網絡圖G，假設敏感節點對H={(1,7)，(3,7)，(5,7)}，pv1,v7=e12,e26,e67，pv3,v7=e32,e26,e67，pv5,v7=e56,e67，根據前面定義可得：

NV={e13,e34,e25,e57}

AV={e67}

PV={e12,e26,e32,e56}

2.1 k-度匿名算法

首先以原始網絡G的度序列d-={d-1，...，d-n}為基礎，構造一個k度匿名序列d～={d1～，...，dn～}。使用函數Δd表示從匿名度序列到原始度序列的距離，計算公式為：

Δd的值越低，則匿名網絡的信息損失就越低。

然后，利用基本的邊修改操作，構造一個新的網絡G～=V～，E～），其度序列等于d～。這些操作允許根據匿名化程度序列（d～）修改網絡結構。添加的虛擬邊的權重賦值為原始圖中最大權重值。圖的修改有三種基本操作：邊轉換、邊添加和邊刪除。

邊轉換：如果(vi,vk)∈E和(vj,vk)?E，可以刪除Vj(vi,vk)并連接(vj,vk)。如圖2(1)顯示了這個基本操作。邊轉換操作對度序列的影響為di～=di-1和dj～=dj+1，操作前后網絡圖中邊緣的數量保持不變，vi的度數減1，vj增加1，vk保持相同的度數。

邊添加：選擇兩個頂點vi,vj∈V，其中(vi,vj)?E并創建它。邊添加操作對度序列的影響為di～=di+1和dj～=dj+1，如圖2(2)所示。

邊刪除：選擇四個頂點vi，vj，vk，vl∈V，其中(vi,vk)∈E，(vj,vl)∈E，(vk,vl)?E。刪除(vi,vk)和(vj,vl)之間的邊并添加一個新的邊(vk,vl)，如圖2(3)所示。邊刪除操作對度序列的影響為di～=di-1，dj～=dj-1，dk～=dk和dl～=dl。

對于匿名度序列用向量δ=d～-d表示哪些結點需要改變度數，δ表明哪個頂點必須增加或減少其度數才能達到所需的k-度匿名。使用圖2中描述的三種基本操作對圖進行修改，得到需要減少其度數的頂點列表δ-={vi:δi<0}，需要增加的頂點列表δ+={vi:δi>0}。

圖2 3種基本邊操作

因為要保持敏感節點對之間的最短路徑psi,sj以及相應的路徑長度dsi,sj不變，還要使匿名后的路徑長度盡可能與原始路徑長度保持一致，因此，在圖修改過程中只能選擇對敏感節點對路徑沒有影響的邊，即只能對未訪問邊緣進行基本邊操作，而對部分訪問邊緣和全訪問邊緣不能進行邊刪除或邊轉換操作。另外，對于加權社會網絡，新添加邊的權重設置為原始圖中最大的權重值。

2.2 最短路徑保持的貪心邊權重擾動（GEWP）算法

k-度匿名算法保護了加權社會網絡圖結構信息，滿足圖結構的k-度匿名。假定社會網絡中所有節點對的最短路徑并非都被認為是重要的，敏感節點對是由數據的擁有者設置的，也就是說數據擁有者決定哪條最短路徑需要被保護，哪一條不需要被保護。在數據擁有者的約束下，為實現最大程度保留圖的權重信息、盡量保證原始圖與擾動圖的信息不變，我們提出了最短路徑保持的貪心邊權重擾動（GEWP）算法。GEWP算法在擾動期間保持敏感節點對的最短路徑相同，并且保持擾動的最短路徑長度接近原始路徑的長度，這樣得到的匿名網絡圖滿足以下條件：

V*=V，E*=E (1)

對于?(si,sj)∈H

在社會網絡G={V,E,W}(||V||=n)中，生成最短路徑列表集P和相應的n*n長度鄰接矩陣D，每個條目psi,sj是表示si和sj之間的最短路徑的鏈表（即si和sj分別是最短路徑的開始和結束節點）。例如，p1,7=(v1→v2→v6→v7)，表明最短路徑p1,7連續通過v1，v2，v6和v7。在鄰接矩陣D中，每個dsi,sj是連接si和sj的最短路徑的長度。

圖3 擾動未訪問邊緣和全訪問邊緣

社會網絡中，非訪問邊緣和全訪問邊緣的權值可以顯著改變，而不影響H中的任何最短路徑，因此算法主要擾動部分訪問邊緣PV。為了最小化原始最短路徑的長度與相應的擾動最短路徑的長度之間的差異，在PV邊上提出了兩個擾動方案。如果擾動最短路徑的當前長度大于原始最小路徑的當前長度，可以減少此路徑中一條邊的權重。否則，需要增加它的權重，以保持擾動的最短路徑的長度接近原始路徑。

2.2.1 增加擾動邊緣權重

圖4 增加部分訪問邊緣權重

其中

2.2.2 減少擾動邊緣權重

擾動前后所有敏感節點對的最短路徑，部分路徑長度。

3 實驗結果與分析

實驗創建1 000個節點的合成數據集G，其對應的鄰接矩陣是1 000*1 000對稱矩陣。邊緣權重設定0-50的隨機數，當其權重為0時，則表示兩節點不連通。假設數據集中20%敏感節點對H，利用Bellman-Ford算法計算敏感節點對的最短路徑并得出其長度，遍歷所有最短路徑經過的邊，找出部分訪問邊緣進行擾動策略，實現匿名。實驗結果如圖6所示。

圖6 保持20%目標對時最短路徑長度隨匿名程度的變化

在圖6中，x軸為匿名程度k，y軸為最短路徑長度平均變化率隨匿名程度的變化。最短路徑長度平均變化率是指匿名路徑上所擾動邊的權重修改量之和占原始邊權重之和的百分比。將匿名擾動前后的矩陣進行比較，發現隨著k值的增加，最短路徑長度與擾動前近似相等，說明GEWP算法能夠很好地保持原始圖的數據信息。另外，H中所有敏感節點對的最短路徑被精確保留。

從圖6還可以看出，保持20%目標對時，即使大量目標對希望保持完全相同的最短路徑和最短路徑長度，擾動的最短路徑長度仍然非常接近原始路徑長度。除此之外，20%目標對的最短路徑在擾動后保持不變。

4 結論

基于邊緣集使用三個基本操作對原始加權社會網絡進行修改，達到所需的k度匿名值，建立了一種保留社會網絡中重要邊緣的方法。該方法考慮邊緣相關性并保留社會網絡中重要邊緣，保留原始網絡圖中某些節點對之間的最短路徑和最短路徑長度。實驗證明，使用這種方法，可以明顯改善數據的效用，減少匿名數據的信息損失。

[1] Ferri F, Grifoni P, Guzzo T. New forms of social and professional digital relationships: the case of Facebook[J]. Soc Netw Anal Min, 2011, 2(2): 121-137.

[2] Backstrom L, Dwork C, Kleinberg. Wherefore art thou r3579x? Anonymized social networks, hidden patterns, and structural steganography[J]. Communications of the ACM, 2011, 54(12): 133-141.

[3] Julian Salas, Vicenc Torra. Graphic sequences, distances and k-degree anonymity[J]. Discrete Applied Mathematics, 2015, 188(1): 25-31.

[4] Liu K, Terzi E. Towards identity anonymization on graphs[A]. Laks V. S. Lakshmanan, Raymond T. Ng, Dennis Shasha. Proceedings of the 2008 ACM SIGMOD international conference on Management of data[C]. New York, USA: ACM Press, 2008: 93–106.

[5] Casas Roma J, Herrera Joancomart, Jordi, Torra, Vicen?. k-Degree Anonymity And Edge Selection: Improving Data Utility In Large Networks[J]. Knowledge & Information Systems, 2017, 50(2): 1-28.

[6] Chester S, Kapron BM, Ramesh G, Srivastava G, Thomo A, Venkatesh S. Why Waldo befriended the dummy? k-anonymization of social networks with pseudo-nodes[J]. Soc Netw Anal Min, 2013, 3(3): 381-399.

[7] Bhattacharya M, Mani P. Preserving privacy in social network graph with k-anonymize degree sequence gener- ation[A]. IEEE: 2015 9th International Conference on Software, Knowledge, Information Management and Applications (SKIMA)[C]. Washington D. C., USA: IEEE Press, 2015: 1-7.

[8] Hartung S, Hoffmann C, Nichterlein A. Improved upper and lower bound heuristics for degree anonymization in social networks[A]. Joachim G, Jyrki K. International Symposium on Experimental Algorithms, Copenhagen, Jun 29-Jul 1, 2014[C]. Berlin, Heidelberg: Springer, 2014: 376-387.

[9] Li Y, Li Y, Yan Q, et al. Privacy leakage analysis in online social networks[J]. Computers & Security, 2015, 49(C): 239-254.

[10] Tsai Y C, Wang S L, Hong T P, et al. [K1, K2]–anony- mization of shortest paths[A]. Tao Y H, Chen L M, Lee C N. Proceedings of the 12th International Conference on Advances in Mobile Computing and Multimedia[C]. New York, USA: ACM Press, 2014: 317- 321.

[11] Tsai Y C, Wang S L, Hong T P, et al. Extending[K1, K2] -anonymization of shortest paths for social networks[M] //Jerry C W L, Ting I H, Tang T, Wang K. Multidisci- plinary social networks research. Berlin: Springer, 2015: 187-199.

[12] 張曉琳,何曉玉,張換香,等.PLRD-(k,m):保護鏈接關系的分布式k-度-m-標簽匿名方法[J].計算機科學與探索, 2019,13(1):74-86.

Anonymity Algorithm for Weighted Social Networks with Sensitive Edge Weights

BI Hong-jing, LU Li-lei

(Department of Computer Science, Tangshan Normal University, Tangshan 063000, China)

Focusing on the privacy preserving of large data networks, a k-degree anonymous network was constructed. A greedy edge weighted perturbation (GEWP) algorithm for shortest path keeping was proposed for the utility of publishing data. It disturbed the weights of some edges to prevent the privacy disclosure problem and preserve the shortest path and length of the path between certain pairs of sensitive nodes in the original network. Simulation results matched theoretical analysis well.

weighted social network; sensitive edge weights; k-anonymity; privacy protection

TP309.2

A

1009-9115(2021)06-0041-05

10.3969/j.issn.1009-9115.2021.06.011

河北省自然科學基金（F2019105134），河北省教育廳科學技術研究項目（ZC2021030），唐山師范學院科研基金（2017C06）

2020-12-10

2021-10-09

畢紅凈（1983-），女，河北唐山人，碩士，講師，研究方向為隱私保護、信息安全。

（責任編輯、校對：田敬軍）