社交網絡的結點隱私性量化.pdf

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

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

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

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

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

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