具有敏感邊緣權(quán)重的加權(quán)社會(huì)網(wǎng)絡(luò)匿名算法

畢紅凈，盧立蕾

計(jì)算機(jī)科學(xué)與自動(dòng)化技術(shù)

具有敏感邊緣權(quán)重的加權(quán)社會(huì)網(wǎng)絡(luò)匿名算法

畢紅凈，盧立蕾

（唐山師范學(xué)院 計(jì)算機(jī)科學(xué)系，河北 唐山 063000）

針對(duì)大型數(shù)據(jù)網(wǎng)絡(luò)隱私保護(hù)問題，首先構(gòu)造了一個(gè)k-度匿名網(wǎng)絡(luò)。為保證發(fā)布數(shù)據(jù)的可用性，提出了貪心邊權(quán)重?cái)_動(dòng)（GEWP）算法，該算法通過發(fā)布網(wǎng)絡(luò)數(shù)據(jù)時(shí)擾亂某些邊緣的權(quán)重防止隱私泄露，同時(shí)保留原始網(wǎng)絡(luò)中敏感節(jié)點(diǎn)對(duì)之間最短路徑和路徑的長(zhǎng)度。仿真實(shí)驗(yàn)顯示的結(jié)果和理論分析相符合。

加權(quán)社會(huì)網(wǎng)絡(luò)；敏感邊緣權(quán)重；K-匿名；隱私保護(hù)

1 引言

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

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

2 背景知識(shí)與問題定義

定義1（加權(quán)社會(huì)網(wǎng)絡(luò)圖）用G={V,E,W}表示一個(gè)加權(quán)社會(huì)網(wǎng)絡(luò)圖，其中V={vi|1≤i≤n}，為圖G中節(jié)點(diǎn)個(gè)數(shù)，V(G)為圖G的節(jié)點(diǎn)集；E={ei,j}，ei,j表示節(jié)點(diǎn)的邊，E(G)為圖G的邊集；W={wi,j}，wi,j為邊ei,j的權(quán)重，W(G)為圖G的邊權(quán)重集合。

圖1 加權(quán)社會(huì)網(wǎng)絡(luò)圖

定義3（匿名度序列）如果度序列中不同節(jié)點(diǎn)的度數(shù)出現(xiàn)至少k次，則該度序列是k-匿名的，用d～表示。

定義4（匿名加權(quán)社會(huì)網(wǎng)絡(luò)圖G～）用G～ ={V～,E～,W～}表示一個(gè)匿名加權(quán)社會(huì)網(wǎng)絡(luò)圖，如果節(jié)點(diǎn)匿名度序列滿足k-度匿名，那么G～也是k-度匿名的。

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

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

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

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

如圖1所示的加權(quán)社會(huì)網(wǎng)絡(luò)圖G，假設(shè)敏感節(jié)點(diǎn)對(duì)H={(1,7)，(3,7)，(5,7)}，pv1,v7=e12,e26,e67，pv3,v7=e32,e26,e67，pv5,v7=e56,e67，根據(jù)前面定義可得：

NV={e13,e34,e25,e57}

AV={e67}

PV={e12,e26,e32,e56}

2.1 k-度匿名算法

首先以原始網(wǎng)絡(luò)G的度序列d-={d-1，...，d-n}為基礎(chǔ)，構(gòu)造一個(gè)k度匿名序列d～={d1～，...，dn～}。使用函數(shù)Δd表示從匿名度序列到原始度序列的距離，計(jì)算公式為：

Δd的值越低，則匿名網(wǎng)絡(luò)的信息損失就越低。

然后，利用基本的邊修改操作，構(gòu)造一個(gè)新的網(wǎng)絡(luò)G～=V～，E～），其度序列等于d～。這些操作允許根據(jù)匿名化程度序列（d～）修改網(wǎng)絡(luò)結(jié)構(gòu)。添加的虛擬邊的權(quán)重賦值為原始圖中最大權(quán)重值。圖的修改有三種基本操作：邊轉(zhuǎn)換、邊添加和邊刪除。

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

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

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

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

圖2 3種基本邊操作

因?yàn)橐３置舾泄?jié)點(diǎn)對(duì)之間的最短路徑psi,sj以及相應(yīng)的路徑長(zhǎng)度dsi,sj不變，還要使匿名后的路徑長(zhǎng)度盡可能與原始路徑長(zhǎng)度保持一致，因此，在圖修改過程中只能選擇對(duì)敏感節(jié)點(diǎn)對(duì)路徑?jīng)]有影響的邊，即只能對(duì)未訪問邊緣進(jìn)行基本邊操作，而對(duì)部分訪問邊緣和全訪問邊緣不能進(jìn)行邊刪除或邊轉(zhuǎn)換操作。另外，對(duì)于加權(quán)社會(huì)網(wǎng)絡(luò)，新添加邊的權(quán)重設(shè)置為原始圖中最大的權(quán)重值。

2.2 最短路徑保持的貪心邊權(quán)重?cái)_動(dòng)（GEWP）算法

k-度匿名算法保護(hù)了加權(quán)社會(huì)網(wǎng)絡(luò)圖結(jié)構(gòu)信息，滿足圖結(jié)構(gòu)的k-度匿名。假定社會(huì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)的最短路徑并非都被認(rèn)為是重要的，敏感節(jié)點(diǎn)對(duì)是由數(shù)據(jù)的擁有者設(shè)置的，也就是說數(shù)據(jù)擁有者決定哪條最短路徑需要被保護(hù)，哪一條不需要被保護(hù)。在數(shù)據(jù)擁有者的約束下，為實(shí)現(xiàn)最大程度保留圖的權(quán)重信息、盡量保證原始圖與擾動(dòng)圖的信息不變，我們提出了最短路徑保持的貪心邊權(quán)重?cái)_動(dòng)（GEWP）算法。GEWP算法在擾動(dòng)期間保持敏感節(jié)點(diǎn)對(duì)的最短路徑相同，并且保持?jǐn)_動(dòng)的最短路徑長(zhǎng)度接近原始路徑的長(zhǎng)度，這樣得到的匿名網(wǎng)絡(luò)圖滿足以下條件：

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

對(duì)于?(si,sj)∈H

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

圖3 擾動(dòng)未訪問邊緣和全訪問邊緣

社會(huì)網(wǎng)絡(luò)中，非訪問邊緣和全訪問邊緣的權(quán)值可以顯著改變，而不影響H中的任何最短路徑，因此算法主要擾動(dòng)部分訪問邊緣PV。為了最小化原始最短路徑的長(zhǎng)度與相應(yīng)的擾動(dòng)最短路徑的長(zhǎng)度之間的差異，在PV邊上提出了兩個(gè)擾動(dòng)方案。如果擾動(dòng)最短路徑的當(dāng)前長(zhǎng)度大于原始最小路徑的當(dāng)前長(zhǎng)度，可以減少此路徑中一條邊的權(quán)重。否則，需要增加它的權(quán)重，以保持?jǐn)_動(dòng)的最短路徑的長(zhǎng)度接近原始路徑。

2.2.1 增加擾動(dòng)邊緣權(quán)重

圖4 增加部分訪問邊緣權(quán)重

其中

2.2.2 減少擾動(dòng)邊緣權(quán)重

擾動(dòng)前后所有敏感節(jié)點(diǎn)對(duì)的最短路徑，部分路徑長(zhǎng)度。

3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)創(chuàng)建1 000個(gè)節(jié)點(diǎn)的合成數(shù)據(jù)集G，其對(duì)應(yīng)的鄰接矩陣是1 000*1 000對(duì)稱矩陣。邊緣權(quán)重設(shè)定0-50的隨機(jī)數(shù)，當(dāng)其權(quán)重為0時(shí)，則表示兩節(jié)點(diǎn)不連通。假設(shè)數(shù)據(jù)集中20%敏感節(jié)點(diǎn)對(duì)H，利用Bellman-Ford算法計(jì)算敏感節(jié)點(diǎn)對(duì)的最短路徑并得出其長(zhǎng)度，遍歷所有最短路徑經(jīng)過的邊，找出部分訪問邊緣進(jìn)行擾動(dòng)策略，實(shí)現(xiàn)匿名。實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 保持20%目標(biāo)對(duì)時(shí)最短路徑長(zhǎng)度隨匿名程度的變化

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

從圖6還可以看出，保持20%目標(biāo)對(duì)時(shí)，即使大量目標(biāo)對(duì)希望保持完全相同的最短路徑和最短路徑長(zhǎng)度，擾動(dòng)的最短路徑長(zhǎng)度仍然非常接近原始路徑長(zhǎng)度。除此之外，20%目標(biāo)對(duì)的最短路徑在擾動(dòng)后保持不變。

4 結(jié)論

基于邊緣集使用三個(gè)基本操作對(duì)原始加權(quán)社會(huì)網(wǎng)絡(luò)進(jìn)行修改，達(dá)到所需的k度匿名值，建立了一種保留社會(huì)網(wǎng)絡(luò)中重要邊緣的方法。該方法考慮邊緣相關(guān)性并保留社會(huì)網(wǎng)絡(luò)中重要邊緣，保留原始網(wǎng)絡(luò)圖中某些節(jié)點(diǎn)對(duì)之間的最短路徑和最短路徑長(zhǎng)度。實(shí)驗(yàn)證明，使用這種方法，可以明顯改善數(shù)據(jù)的效用，減少匿名數(shù)據(jù)的信息損失。

[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):保護(hù)鏈接關(guān)系的分布式k-度-m-標(biāo)簽?zāi)涿椒╗J].計(jì)算機(jī)科學(xué)與探索, 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

河北省自然科學(xué)基金（F2019105134），河北省教育廳科學(xué)技術(shù)研究項(xiàng)目（ZC2021030），唐山師范學(xué)院科研基金（2017C06）

2020-12-10

2021-10-09

畢紅凈（1983-），女，河北唐山人，碩士，講師，研究方向?yàn)殡[私保護(hù)、信息安全。

（責(zé)任編輯、校對(duì)：田敬軍）