一種保持節點可達性的圖擾動算法

張換香 張曉琳 何曉玉 李海榮

1(內蒙古科技大學工程訓練中心 內蒙古 包頭 014010)2(內蒙古科技大學信息工程學院 內蒙古 包頭 014010)

0 引 言

隨著社會網絡的發展，用戶之間互動和交流產生了大量的數據，社會網絡數據隱私信息的安全性成為當今隱私保護研究的熱點問題。為了保護社會網絡中的隱私信息，研究者提出匿名圖化隱私保護技術，通過修改社會網絡圖，從而使攻擊者無法準確獲知用戶信息，并最大可能地保證匿名圖的數據可用性。但是隱私保護過程中并沒有考慮匿名技術對可達性的影響，導致可達性查詢存在很大的信息損失。

節點間的可達性問題，是指判定圖中兩節點u、v間是否存在路徑，如果存在，則稱節點u可達v，記作u→v。節點間的可達性查詢在社會網絡中有著廣泛的應用，例如可以提高用戶粘度的好友推薦系統。社會網絡分析會泄露用戶間的鏈接關系，對某些用戶來說，這種鏈接關系并不希望被外人知曉。

圖1 社會網絡圖G

研究者提出通鏈接擾動，即通過刪除、添加邊來保護鏈接關系，例如，在圖1中，為了保護鏈接<1,4>，可以從圖中刪除<1,4>，并將節點1與圖中其他節點鏈接。然而，鏈接擾動技術并沒有考慮節點間的可達性。如圖2所示，G1和G2是圖1鏈接擾動后得到的匿名圖。盡管G1和G2都隱藏了鏈接<1,4>，但兩者在保護節點可達性的效果上并不相同。具體來說，若將<1,4>中目的節點用節點3替換，則節點1到節點4之間不再可達。但是若將<1,4>中目的節點用節點5替換，則節點1到節點4仍然可達。因此，前者比后者更好地保持了節點間的可達性。

圖2 圖G的兩個匿名圖

針對此問題，本文提出一種可達性保持的圖擾動RPP(Reachability Preserving Perturbation)算法。該算法利用“統一刪除，逐一擾動”策略和添加偽節點的方法，以一定概率擾動社會網絡中的邊，從而在保持節點可達性的同時很好地保護圖的其他結構性質。

1 相關工作

為了保護社會網絡中的鏈接關系，研究者提出通過圖擾動技術來保護敏感鏈接，即通過對社會網絡圖進行隨機修改，使得攻擊者不能準確推測出原始圖中真實數據。文獻[1]提出一種鄰居隨機的邊擾動技術，以一定概率保留邊，若需要刪除，則用邊代替，其中節點w是節點u的r(r≥2)跳鄰居節點。文獻[2]提出利用安全分組保護交互型社會網絡的鏈接關系，其思想是：將網絡抽象成二分圖，然后將網絡節點分組，并且同一分組內節點在鏈接關系上不可區分。文獻[3]對文獻[2]做出擴展用于保護高緯數據。文獻[4]針對網絡中的公眾節點和隱私節點，提出添加偽節點和修改邊的鏈接關系的保護方法。文獻[5-6]針對算法執行的復雜度和發布數據的可用性，提出通過添加、刪除和交換邊保護隱私信息。文獻[7]根據兩個等價類之間的鏈接密度，提出了一種計算鏈接識別概率的方法。在此基礎上，應用最小化刪除或交換邊數目的貪心策略，使鏈接識別的可能性降低到給定的閾值之下。文獻[8]提出了基于子圖結構的鏈接擾亂，即將原始圖分割成若干子圖，隨機的在子圖中增加、刪除m條邊。文獻[9]為了保護鏈接的關聯性，首先利用邊鄰居中心性計算每條邊的移除概率p并依據概率p從原始圖G中移除w條邊，然后在G的補圖中選出w條邊添加到圖G。文獻[10]通過引入馬爾科夫鏈并建立傳遞矩陣P，提出一種基于隨機游走機制的圖擾動策略，在保護鏈接隱私的同時降低擾動過程對圖數據可用性的影響。文獻[11]針對敏感鏈接關系設計了一個LinkMirage模型，模型中在保護數據可用性的前提下，模糊社會網絡圖中的社交拓撲結構和提供帶有模糊社交關系視圖的不受信任的外部應用，從而抵御鏈接關系再識別攻擊。

綜上所述，當前基于圖擾動思想的隱私保護技術忽視了對節點可達性的保護，導致匿名圖在節點可達性(兩節點在圖中是否存在路徑)查詢的低可用性。針對此問題，本文提出一種能有效保護節點可達性的圖擾動算法，在匿名社會網絡的同時降低節點可達信息損失。

2 背景知識及定義

在本文中，社會網絡表示成簡單有向圖G=(V,E)，其中V是節點集，代表社會網絡中的用戶；E是有向邊集，其中是一條有向鏈接，表示由用戶u到v。

定義1(邊擾動) 已知社會網絡有向圖G=(V,E)，節點u，v是節點集V中不同的兩個節點。是E中的鏈接，即∈E，節點w是圖中不同于u，v的節點且?E，邊擾動是指做如下操作：

?E且∈E

即刪除邊，并添加到有向圖，稱為擾動邊，節點w稱為u的假目的節點。

以圖G為例，若刪除<1,4>并添加<1,5>到圖G，則稱完成一次邊擾動操作，其中節點5稱作節點1的假目標節點。

定義2(可達節點) 已知社會網絡有向圖G=(V,E)，u，v是圖中兩個不同的節點，若存在路徑L，使得節點u沿此路徑能夠到達節點v，則稱節點v是節點u的可達節點，節點對(u,v)稱為可達節點對。

以圖G為例，節點4與節點7存在路徑{<4,5>,<5,7>}，則節點7是節點4的可達節點，節點對(4,7)稱為可達節點對。

定義3(r-鄰居)r是給定的非負整數，節點對(u,v)是有向圖G中的一個可達節點對，dist(u,v)表示可達節點對(u,v)的最短路徑長度，若節點v滿足條件：

dist(u,v)≤r

則稱節點v是節點u的r-鄰居，并把所有滿足條件的節點集合記作Nr(u)。其中，在社會網絡有向圖G中，源節點u的所有可達的節點表示為N*(u)；源節點u的1跳鄰居節點集合表示為Dst(u)。

以圖G為例，并令u=5，則Dst(5)={4,6,7}，N1(5)={5,4,6,7}，N2(5)={5,4,6,7,2}，N3(5)={5,4,6,7,2,1,3}，N4(5)=N3(5)，N*(5)={5,4,6,7,2,1,3}。

定義4(假目標節點集) 已知社會網絡有向圖G=(V,E)，∈E，假目標節點集PDNS(u,r,s)是指，源節點u的假目的節點w的集合。其中r指源節點u的r-鄰居半徑(r≥2)，s指PDNS(u,r,s)中包含的節點個數，s≥|Dst(u)|。假設s1=|Nr(u)|-|N1(u)|，s2=|N*(u)|-|N1(u)|。并且s2≥s1≥s，選取PDNS(u,r,s)集合可以分為以下三種情況：

(1)s1≥s，即Nr(u)-N1(u)中節點數目不少于s，則PDNS(u,r,s)={Nr(u)-N1(u)}。

(2)s1

(3)s2

以圖G中的節點5為例，并假設r=2、s=2，則PDNS(5,2,2)={2}，由于s1=1

3 保持可達性的圖擾動算法

若要隱藏邊的存在，只需隱藏源節點u或目的節點v就能夠達到目的，因為僅知道源節點u或目的節點v，并不能推測出的存在。本文采用鄰居隨機擾動策略隱藏邊的目的節點，即以某種概率p保留邊的目的節點v，并以概率(1-p)用假目的節點w將其替換[1]。社會網絡中的邊是以概率p保留的，其不可預測性致使文獻[1]并不能保持節點的可達性。以圖G為例，假定首次處理的是邊<1,4>，并且<1,4>的概率為(1-p)，若刪除<1,4>并添加<1,5>。此時，節點1和節點4仍然可達，因為此時圖中其他邊并未擾動；若邊<5,4>概率仍是(1-p)，則需要刪除<5,4>，導致節點1和節點4不再可達。

為了保持社會網絡擾動圖的節點可達性，提出一種“統一刪除，順序擾動”UD&OP(Unified Delete&Order Perturbation)策略，所謂的“UD&OP”策略，是指是指首先同時刪除概率為(1-p)的邊，然后逐一處理這些刪除邊。算法的思想是：首先，以概率p和(1-p)為社會網絡中的邊賦值，刪除所有概率為(1-p)的邊，并將與相應的PDNS(u,r,s)存放入ECN表；其次，順序擾動ECN表中每條邊，直到ECN表為空。表1顯示了ECN的數據結構，ECN由兩部分構成，其中ECN.edge保存概率為(1-p)的邊，而ECN.CN則保存所對應的假目標節點集。

表1 邊-候選節點

本算法包括UD和OP兩部分，而UD過程中需要將概率為(1-p)的邊和相應的假目標節點集存入ECN表中，如何產生假目標節點集是關鍵問題。對此，提出相應的生成算法PDNSA(Pseudo Destination Node Set)，具體如算法1所示。

算法1Pseudo Destination Node Set

Input: 社會網絡圖G=(V,E)；源節點u;源節點u的r-鄰居半徑r,r≥2;PDNS中節點數目。

Output: PDNS(u,r,s)。

1: Dijkstra(G,u)

//計算源節點到圖G其他節點的所有最短路徑;

2:N1(u)={u}Dst(u);

3: 計算節點u在r范圍內所有可達節點，并存入Nr(u);

4: 計算節點u在圖G中的所有可達節點，存入N*(u);

5: 計算s1，s2；

6: ifs1>s

7: PDNS(u,r,s)={Nr(u)-N1(u)};

8: else

9: ifs≤s2

10: PDNS(u,r,s)={Nr(u)-N1(u)}∪RandomSelect {N*(u)-Nr(u),s-s1};

11: elses2

12: PDNS(u,r,s)={N*(u)-N1(u)}∪RandomSelect {V-N*(u),s-s2};

13: return PDNS(u,r,s);

PDNSA算法基于單源最短路徑，首先，得到節點u與圖G中其他節點最短路徑，然后根據參數r和s生成PDNS(u,r,s)。以圖1中節點1為例并假定r=2、s=2，根據PDNSA算法第1行，得到節點1的所有最短路徑：<1,4>、<1,4,2>、<1,4,2,3>、<1,4,5>、<1,4,5,6>、<1,4,5,7>,則此時N1(1)={1,4}；節點1的r范圍可達，則是指與節點1最短路徑長度不大于r的節點，由上述最短路徑可知N2(1)={1,4,2,5}；N*(1)則是所有最短路徑中的節點，N*(1)={1,4,2,3,5,6,7}；此時，N2(1)-N1(1)={2,5}，包含2個節點(大于等于S)，因此，PDNS(1,2,2)={2,5}。

為了保護節點的可達性，提出基于UD&OP策略的RPP算法，其基本思想是：首先，為圖G的每條邊以概率p和(1-p)賦予權重1或-1；其次，若邊的權重值為-1，則將從圖G中移除，并將和相應的PDNS(u,r,s)存放在ECN表中，得到初始匿名圖G*；最后，將ECN表中的邊標記為“unanonymized”，然后做以下操作：

(1) 判斷其PDNS(u,r,s)中是否存在節點w，節點w在匿名圖G*可達v，若存在則向G*添加鏈接。

(2) 若PDNS(u,r,s)中不存在節點w，判斷G*中是否存在其他節點s可達v，若可達，將鏈接添加到G*。

(3) 若(1)和(2)均為成功，則添加偽節點t，并向G*添加邊和。

(4) 經過(1)、(2)、(3)后，將邊標記為“anonymized”，并從ECN表中移除，得到新的匿名圖G*。處理ECN中下一條標記為“unanonymized”的邊。

(5) 重復步驟(1)、(2)、(3)、(4)直到ECN表為空，得到最終的匿名圖G*。

RPP算法的具體過程如算法2所示。

算法2Reachability Preserving Perturbation

Input: 社會網絡圖G=(V,E)；鏈接保留概率p；參數s；參數r，r≥2。

由于清洗節氣門后，沒有對其進行匹配，所以導致進氣量、噴油量、點火正時嚴重偏離了正常范圍。該發動機控制系統的控制方式比較奇特。由于積炭導致的節氣門開度過大，發動機電腦記憶的初始節氣門位置就會過大，在針對節氣門進行清洗作業后，如果沒有進行節氣門初始化的話，其節氣門開度不會自動減小，使通過節氣門的進氣量過大，相應的噴油量也會過大，導致清洗后的短時間內發動機轉速急劇增加，達到2 000r/min左右，但由于此時的加速踏板位置信號處于全閉狀態，電腦又不允許出現轉速過高的情況。

Output: 匿名圖G*。

1:PDNSA(G);

//利用算法1得到所有節點的PDNS(u,r,s)。

2: 對圖G中邊以概率p和(1-p)賦予權重1或-1。

3: 移除圖G中所有權重為-1的邊得到初始匿名圖G*,并將邊與對應的PDNS(u,r,s)存入ECN表。

4:ifECN非空

5:forfirstinECN

//處理ECN表中第一條邊。

6:ifwPDNS(u,r,s)滿足w v

//若PDNS(u,r,s)中存在w可達v

7:Add to G*;

//添加邊到G*

//G*存在其他節點s可達v

9:AddtoG*;

//添加邊到G*

10:else

11:AddNewnodettoG*andadd, to G*;

//添加偽節點和偽邊

12:updataG*;

//匿名完成后，更新匿名圖G*

13:removefromECN;

//從ECN刪除邊

14:else

15:returnG*

下面以圖1為例，敘述RPP算法的邊擾動過程，并假設r=2、s=2，RPP算法通過1-3行，得到如圖3所示的ECN表和初始匿名圖G*。

圖3 ECN表和匿名圖G*

RPP算法執行第4行，由于ECN，則擾動第一條邊<1,4>，其PDNS(1,2,2)={2,5}，從G*中可知，此時節點5可達節點4，則添加<1,5>到G*并將<1,4>從ECN表中刪除，得到新的匿名圖G*,如圖4所示。

圖4 新的ECN表和匿名圖G*

圖5 最終匿名圖G*

此時ECN非空集，算法執行4～12行，由于<3,6>所對應的PDNS(3,2,2)={2,7}并沒有節點可達6，因此需要判斷G*是否有節點可達6，此時圖G*中節點1、4、5都可達6，考慮到最短路徑的變化，選擇節點5，因為這樣才使得節點3和6的最短距離變化最小，添加<3,5>到G*。同理，處理邊<2,3>，此時{4,6}和G*中沒有可達3的節點，因此向G*添加偽節點8，并添加邊<2,8>和<8,3>，得到最終的匿名圖G*，如圖5所示。

4 實 驗

實驗對RPP算法進行性能分析和評價。實驗采用SNAP網站提供的兩個真實社會網絡圖數據集Wiki-Vote和p2p-Gnutella04進行分析和測試。

4.1 實驗數據集及實驗環境

Wiki-Vote是維基百科2008年1月份的投票數據，其中有向邊表示用戶u向用戶v投出選票，Wiki-Vote數據集包含7 115個節點，103 689條鏈接；p2p-Gnutella04數據集來源于Gnutella網絡2008年8月4日以來的數據，節點代表網絡中的主機，有向邊表示主機之間的鏈接，p2p-Gnutella04數據集共包含10 876個節點和39 994條邊。

實驗將文獻[1]的匿名算法實現并記作NR，用于對比RPP算法。實驗的軟硬件環境如下：

(1) 硬件環境：Intel Core i7-2720QM，CPU 2.2 GHz，16 GB RAM，120 GB SSD。

(2) 操作系統：Win10 專業版。

(3) 編程語言：Python 3.5。

4.2 算法性能分析

實驗測試了算法執行時間隨參數p以及r值變化的情況，實驗結果如圖6所示，其中“X-NR”表示用文獻[1]中匿名方法處理數據消耗的時間，“X-RPP”是利用RPP算法匿名數據消耗的時間，p表示邊的保留概率，r表示鄰居半徑。從圖6中可以看出，NR算法和RPP算法匿名圖所消耗的時間會隨r值的變大而增加，隨著邊保留概率p的增大而降低。從實驗結果可知，當邊的保留概率大于0.5時，RPP算法在執行效率上接近與NR算法，而當r不大于4時，兩者的執行效率差別也不大。

(a) 時間隨參數p值變化的情況

(b) 時間隨參數r值變化的情況圖6 時間隨參數p以及r值變化的情況

4.3 數據可用性分析

實驗從添加節點數目、節點的度中心性以及接近中心性三方面測試RPP算法在數據可用性上的表現。節點的度中心性是社會網絡分析中衡量節點中心性最直接度量指標，一個節點的度越大，說明此節點在社會網絡中的度中性越高；節點的接近中心性，是衡量節點與社會網絡中其他節點親密度的指標，節點的接近中心性越高，說明節點傳遞消息越迅速。實驗通過計算原始圖以及擾動圖中的節點排名等級列表的斯皮爾曼相似性[16]來判斷度中心性和接近中心性的變動情況，相似性值越大，數據可用性越高。

為了評估匿名圖G*中新添加的節點所占的比例，定義節點添加率=Na/N*，其中Na是添加的節點數目，N*是匿名圖G*中的節點數目。圖7給出了兩個數據集隨著保留概率p和鄰居半徑r變化添加節點數目的變化情況。實驗結果顯示,添加的節點數目隨著保留概率p的增大而減少,但隨著參數r的增而增多。由此可知，適當選取p和r的閾值能有效降低節點的添加率，提高數據的可用性。

圖7 p和r改變時添加節點數變化情況

圖8和圖9分別展示了，數據集Wiki-Vote和p2p隨參數p、r變化的接近中心性的變化情況，其中NR是利用文獻[1]處理的結果，“RPP”是利用所提出的RPP算法所得到的結果。可以看出，兩種方法的變化趨勢基本一致，都隨p的增大而提高可用性，隨r的增大可用性降低。RPP算法NR算法基本持平，部分略高于后者，同NR算法相比，在接近中心性方面表現更好。

圖8 數據集wiki-vote隨參數p變化的接近中心性的變化情況

圖9 數據集p2p隨參數r變化的接近中心性的變化情況

從實驗結果中可以看出，RPP算法要略低于NR算法，這是因為RPP算法為了保持節點間的可達性，向圖中添加了一定量的偽節點，這些偽節點致使節點的度中性有所降低。但隨著邊保留概率p的增大，RPP算法逐漸逼近NR算法，這是因為隨著p的增大，添加的節點數目逐漸減少的原因。

5 結 語

針對圖擾動過程中，匿名圖在節點間可達性查詢可用性低的問題，提出一種“統一刪除，順序擾動”的局部鄰居隨機的社會網絡隱私保護方法，該方法通過統一刪除需要擾動的邊，并將邊連同假目標節點集存放于ECN表中，然后擾動ECN表中的邊，達到保持節點可達性的目的。下一步將對RPP算法做進一步優化，提高算法的執行效率，減少偽節點的添加數目。