社交網(wǎng)絡(luò)的結(jié)點隱私性量化.pdf

1、經(jīng)過信息化變革，在線社交網(wǎng)絡(luò)已經(jīng)成為人類社會中不可缺少的重要組成部分，近幾十年以來，在線社交網(wǎng)絡(luò)服務(wù)不但能夠滿足人類的社交需求，更能為用戶提供便捷的生活方式。然而，為了使社交網(wǎng)絡(luò)服務(wù)平臺提供更加多樣化的服務(wù)，平臺會提供第三方接口，便于其他服務(wù)機構(gòu)進行結(jié)點分類、預(yù)測，從而提供其他的推薦服務(wù)，如推薦好友、和廣告等。同時，很多社交網(wǎng)絡(luò)平臺自身的開放性使得大量用戶數(shù)據(jù)公開，非常不利于用戶隱私的保護。
　　匿名方法能夠一定程度保護用戶的身份

2、信息，但是大型圖的結(jié)構(gòu)，尤其是與結(jié)點關(guān)聯(lián)密切的子圖結(jié)構(gòu)依然會泄露很多個人信息，敵手通過挖掘這些結(jié)點結(jié)構(gòu)信息，再通過其他渠道收集一些信息，就能迅速判斷出結(jié)點的身份。近些年，圖的隱私越來越多地受到重視，k-匿名算法[28]、l-closeness[22]、t-closeness[19]、δ-presence[24]等算法紛紛被提出。
　　本文主要研究預(yù)防身份信息挖掘的隱私保護。在保護結(jié)點身份信息方面，k-匿名算法能夠有效對圖結(jié)點進行匿

3、名處理，保證公開圖結(jié)構(gòu)中，對于每個結(jié)點u，都有至少k-1個結(jié)點與它具有相同的度。但原始的k-匿名算法不適用于大規(guī)模結(jié)點處理，2015年，Bhattacharya和Papri[8]對k-匿名算法進行改進，提出k-匿名的迭代算法，方便批量地對結(jié)點進行處理，從而更適用于大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)。
　　雖然改進的k-匿名的迭代算法已經(jīng)能夠進行大規(guī)模結(jié)點處理，但這個算法有明顯的弊端。單純通過加邊操作修改圖結(jié)構(gòu)，會使原始圖結(jié)構(gòu)在修改過后趨于完全圖，不利

4、于第三方接口進行分類、預(yù)測、推薦服務(wù)。
　　本文在圖結(jié)點特征學(xué)習(xí)算法的基礎(chǔ)上，結(jié)合結(jié)點的度和結(jié)點的特征表示向量，第一次給出有權(quán)無向圖的隱私性量化方法。本文提出的量化算法通過在結(jié)點附近進行隨機游走取樣，從而對每個結(jié)點抽取出特征表示向量，結(jié)合特征表示向量之間的距離和度進行計算。當(dāng)量化值超過閾值時，結(jié)點將被系統(tǒng)自動地拋出，視為隱私高危結(jié)點，便于管理員進行處理。本文提出的量化算法尤其適合于對大型圖進行處理，其中結(jié)點的度隱私性量化評價，能夠

5、篩選出結(jié)點的度過大的用戶，管理員可以對其進行減邊操作;基于特征學(xué)習(xí)的隱私性評價能夠篩選出結(jié)點與鄰居結(jié)點明顯不同的用戶，主要是在聯(lián)結(jié)小團體上能夠起到關(guān)鍵作用的結(jié)點，管理員可以對其進行加點、加邊操作。同時，本文通過加權(quán)整合兩種方法，得到綜合性隱私量化評價，評分越高的結(jié)點，隱私泄露危險越大。本文主要討論的是有權(quán)無向圖中的隱私保護，此外，對有權(quán)有向圖，本文也同樣給出了對應(yīng)的修改方案。
　　雖然本文沒有對后續(xù)結(jié)點處理方法給出具體描述，但管理

6、員可以依據(jù)結(jié)點度和結(jié)點周圍結(jié)構(gòu)兩個方面，分別自動地采用學(xué)界已有的減邊方法和加點加邊方法進行處理，在為結(jié)點提供身份信息隱私保護的同時，最大程度地維持原圖結(jié)構(gòu)，方便提供第三方接口服務(wù)。
　　本文提出的隱私性量化算法的時間復(fù)雜度為O(|V|log|V|)，存儲復(fù)雜度為O(|E|2+d|V|)，其中|V|為網(wǎng)絡(luò)結(jié)點數(shù)，|E|為網(wǎng)絡(luò)邊數(shù)，d為特征表示向量維數(shù)。
　　本文采用Zachary Karate數(shù)據(jù)集進行算法測試，詳細解釋算法參