一種保持節(jié)點(diǎn)可達(dá)性的圖擾動(dòng)算法

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

1(內(nèi)蒙古科技大學(xué)工程訓(xùn)練中心 內(nèi)蒙古 包頭 014010)2(內(nèi)蒙古科技大學(xué)信息工程學(xué)院 內(nèi)蒙古 包頭 014010)

0 引 言

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

節(jié)點(diǎn)間的可達(dá)性問題，是指判定圖中兩節(jié)點(diǎn)u、v間是否存在路徑，如果存在，則稱節(jié)點(diǎn)u可達(dá)v，記作u→v。節(jié)點(diǎn)間的可達(dá)性查詢在社會(huì)網(wǎng)絡(luò)中有著廣泛的應(yīng)用，例如可以提高用戶粘度的好友推薦系統(tǒng)。社會(huì)網(wǎng)絡(luò)分析會(huì)泄露用戶間的鏈接關(guān)系，對某些用戶來說，這種鏈接關(guān)系并不希望被外人知曉。

圖1 社會(huì)網(wǎng)絡(luò)圖G

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

圖2 圖G的兩個(gè)匿名圖

針對此問題，本文提出一種可達(dá)性保持的圖擾動(dòng)RPP(Reachability Preserving Perturbation)算法。該算法利用“統(tǒng)一刪除，逐一擾動(dòng)”策略和添加偽節(jié)點(diǎn)的方法，以一定概率擾動(dòng)社會(huì)網(wǎng)絡(luò)中的邊，從而在保持節(jié)點(diǎn)可達(dá)性的同時(shí)很好地保護(hù)圖的其他結(jié)構(gòu)性質(zhì)。

1 相關(guān)工作

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

綜上所述，當(dāng)前基于圖擾動(dòng)思想的隱私保護(hù)技術(shù)忽視了對節(jié)點(diǎn)可達(dá)性的保護(hù)，導(dǎo)致匿名圖在節(jié)點(diǎn)可達(dá)性(兩節(jié)點(diǎn)在圖中是否存在路徑)查詢的低可用性。針對此問題，本文提出一種能有效保護(hù)節(jié)點(diǎn)可達(dá)性的圖擾動(dòng)算法，在匿名社會(huì)網(wǎng)絡(luò)的同時(shí)降低節(jié)點(diǎn)可達(dá)信息損失。

2 背景知識(shí)及定義

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

定義1(邊擾動(dòng)) 已知社會(huì)網(wǎng)絡(luò)有向圖G=(V,E)，節(jié)點(diǎn)u，v是節(jié)點(diǎn)集V中不同的兩個(gè)節(jié)點(diǎn)。是E中的鏈接，即∈E，節(jié)點(diǎn)w是圖中不同于u，v的節(jié)點(diǎn)且?E，邊擾動(dòng)是指做如下操作：

?E且∈E

即刪除邊，并添加到有向圖，稱為擾動(dòng)邊，節(jié)點(diǎn)w稱為u的假目的節(jié)點(diǎn)。

以圖G為例，若刪除<1,4>并添加<1,5>到圖G，則稱完成一次邊擾動(dòng)操作，其中節(jié)點(diǎn)5稱作節(jié)點(diǎn)1的假目標(biāo)節(jié)點(diǎn)。

定義2(可達(dá)節(jié)點(diǎn)) 已知社會(huì)網(wǎng)絡(luò)有向圖G=(V,E)，u，v是圖中兩個(gè)不同的節(jié)點(diǎn)，若存在路徑L，使得節(jié)點(diǎn)u沿此路徑能夠到達(dá)節(jié)點(diǎn)v，則稱節(jié)點(diǎn)v是節(jié)點(diǎn)u的可達(dá)節(jié)點(diǎn)，節(jié)點(diǎn)對(u,v)稱為可達(dá)節(jié)點(diǎn)對。

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

定義3(r-鄰居)r是給定的非負(fù)整數(shù)，節(jié)點(diǎn)對(u,v)是有向圖G中的一個(gè)可達(dá)節(jié)點(diǎn)對，dist(u,v)表示可達(dá)節(jié)點(diǎn)對(u,v)的最短路徑長度，若節(jié)點(diǎn)v滿足條件：

dist(u,v)≤r

則稱節(jié)點(diǎn)v是節(jié)點(diǎn)u的r-鄰居，并把所有滿足條件的節(jié)點(diǎn)集合記作Nr(u)。其中，在社會(huì)網(wǎng)絡(luò)有向圖G中，源節(jié)點(diǎn)u的所有可達(dá)的節(jié)點(diǎn)表示為N*(u)；源節(jié)點(diǎn)u的1跳鄰居節(jié)點(diǎn)集合表示為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(假目標(biāo)節(jié)點(diǎn)集) 已知社會(huì)網(wǎng)絡(luò)有向圖G=(V,E)，∈E，假目標(biāo)節(jié)點(diǎn)集PDNS(u,r,s)是指，源節(jié)點(diǎn)u的假目的節(jié)點(diǎn)w的集合。其中r指源節(jié)點(diǎn)u的r-鄰居半徑(r≥2)，s指PDNS(u,r,s)中包含的節(jié)點(diǎn)個(gè)數(shù)，s≥|Dst(u)|。假設(shè)s1=|Nr(u)|-|N1(u)|，s2=|N*(u)|-|N1(u)|。并且s2≥s1≥s，選取PDNS(u,r,s)集合可以分為以下三種情況：

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

(2)s1

(3)s2

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

3 保持可達(dá)性的圖擾動(dòng)算法

若要隱藏邊的存在，只需隱藏源節(jié)點(diǎn)u或目的節(jié)點(diǎn)v就能夠達(dá)到目的，因?yàn)閮H知道源節(jié)點(diǎn)u或目的節(jié)點(diǎn)v，并不能推測出的存在。本文采用鄰居隨機(jī)擾動(dòng)策略隱藏邊的目的節(jié)點(diǎn)，即以某種概率p保留邊的目的節(jié)點(diǎn)v，并以概率(1-p)用假目的節(jié)點(diǎn)w將其替換[1]。社會(huì)網(wǎng)絡(luò)中的邊是以概率p保留的，其不可預(yù)測性致使文獻(xiàn)[1]并不能保持節(jié)點(diǎn)的可達(dá)性。以圖G為例，假定首次處理的是邊<1,4>，并且<1,4>的概率為(1-p)，若刪除<1,4>并添加<1,5>。此時(shí)，節(jié)點(diǎn)1和節(jié)點(diǎn)4仍然可達(dá)，因?yàn)榇藭r(shí)圖中其他邊并未擾動(dòng)；若邊<5,4>概率仍是(1-p)，則需要?jiǎng)h除<5,4>，導(dǎo)致節(jié)點(diǎn)1和節(jié)點(diǎn)4不再可達(dá)。

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

表1 邊-候選節(jié)點(diǎn)

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

算法1Pseudo Destination Node Set

Input: 社會(huì)網(wǎng)絡(luò)圖G=(V,E)；源節(jié)點(diǎn)u;源節(jié)點(diǎn)u的r-鄰居半徑r,r≥2;PDNS中節(jié)點(diǎn)數(shù)目。

Output: PDNS(u,r,s)。

1: Dijkstra(G,u)

//計(jì)算源節(jié)點(diǎn)到圖G其他節(jié)點(diǎn)的所有最短路徑;

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

3: 計(jì)算節(jié)點(diǎn)u在r范圍內(nèi)所有可達(dá)節(jié)點(diǎn)，并存入Nr(u);

4: 計(jì)算節(jié)點(diǎn)u在圖G中的所有可達(dá)節(jié)點(diǎn)，存入N*(u);

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

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

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

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

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

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

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

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

算法2Reachability Preserving Perturbation

Input: 社會(huì)網(wǎng)絡(luò)圖G=(V,E)；鏈接保留概率p；參數(shù)s；參數(shù)r，r≥2。

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

Output: 匿名圖G*。

1:PDNSA(G);

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

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

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

4:ifECN非空

5:forfirstinECN

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

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

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

7:Add to G*;

//添加邊到G*

//G*存在其他節(jié)點(diǎn)s可達(dá)v

9:AddtoG*;

//添加邊到G*

10:else

11:AddNewnodettoG*andadd, to G*;

//添加偽節(jié)點(diǎn)和偽邊

12:updataG*;

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

13:removefromECN;

//從ECN刪除邊

14:else

15:returnG*

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

圖3 ECN表和匿名圖G*

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

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

圖5 最終匿名圖G*

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

4 實(shí) 驗(yàn)

實(shí)驗(yàn)對RPP算法進(jìn)行性能分析和評(píng)價(jià)。實(shí)驗(yàn)采用SNAP網(wǎng)站提供的兩個(gè)真實(shí)社會(huì)網(wǎng)絡(luò)圖數(shù)據(jù)集Wiki-Vote和p2p-Gnutella04進(jìn)行分析和測試。

4.1 實(shí)驗(yàn)數(shù)據(jù)集及實(shí)驗(yàn)環(huán)境

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

實(shí)驗(yàn)將文獻(xiàn)[1]的匿名算法實(shí)現(xiàn)并記作NR，用于對比RPP算法。實(shí)驗(yàn)的軟硬件環(huán)境如下：

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

(2) 操作系統(tǒng)：Win10 專業(yè)版。

(3) 編程語言：Python 3.5。

4.2 算法性能分析

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

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

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

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

實(shí)驗(yàn)從添加節(jié)點(diǎn)數(shù)目、節(jié)點(diǎn)的度中心性以及接近中心性三方面測試RPP算法在數(shù)據(jù)可用性上的表現(xiàn)。節(jié)點(diǎn)的度中心性是社會(huì)網(wǎng)絡(luò)分析中衡量節(jié)點(diǎn)中心性最直接度量指標(biāo)，一個(gè)節(jié)點(diǎn)的度越大，說明此節(jié)點(diǎn)在社會(huì)網(wǎng)絡(luò)中的度中性越高；節(jié)點(diǎn)的接近中心性，是衡量節(jié)點(diǎn)與社會(huì)網(wǎng)絡(luò)中其他節(jié)點(diǎn)親密度的指標(biāo)，節(jié)點(diǎn)的接近中心性越高，說明節(jié)點(diǎn)傳遞消息越迅速。實(shí)驗(yàn)通過計(jì)算原始圖以及擾動(dòng)圖中的節(jié)點(diǎn)排名等級(jí)列表的斯皮爾曼相似性[16]來判斷度中心性和接近中心性的變動(dòng)情況，相似性值越大，數(shù)據(jù)可用性越高。

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

圖7 p和r改變時(shí)添加節(jié)點(diǎn)數(shù)變化情況

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

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

圖9 數(shù)據(jù)集p2p隨參數(shù)r變化的接近中心性的變化情況

從實(shí)驗(yàn)結(jié)果中可以看出，RPP算法要略低于NR算法，這是因?yàn)镽PP算法為了保持節(jié)點(diǎn)間的可達(dá)性，向圖中添加了一定量的偽節(jié)點(diǎn)，這些偽節(jié)點(diǎn)致使節(jié)點(diǎn)的度中性有所降低。但隨著邊保留概率p的增大，RPP算法逐漸逼近NR算法，這是因?yàn)殡S著p的增大，添加的節(jié)點(diǎn)數(shù)目逐漸減少的原因。

5 結(jié) 語

針對圖擾動(dòng)過程中，匿名圖在節(jié)點(diǎn)間可達(dá)性查詢可用性低的問題，提出一種“統(tǒng)一刪除，順序擾動(dòng)”的局部鄰居隨機(jī)的社會(huì)網(wǎng)絡(luò)隱私保護(hù)方法，該方法通過統(tǒng)一刪除需要擾動(dòng)的邊，并將邊連同假目標(biāo)節(jié)點(diǎn)集存放于ECN表中，然后擾動(dòng)ECN表中的邊，達(dá)到保持節(jié)點(diǎn)可達(dá)性的目的。下一步將對RPP算法做進(jìn)一步優(yōu)化，提高算法的執(zhí)行效率，減少偽節(jié)點(diǎn)的添加數(shù)目。