基于DeepLink的社交網絡去匿名方法

王培，賈焰，李愛平，蔣千越

基于DeepLink的社交網絡去匿名方法

王培，賈焰，李愛平，蔣千越

（國防科技大學計算機學院，湖南 長沙 410073）

現有的社交網絡去匿名方法主要是基于網絡結構，對網絡結構進行學習與表示是去匿名的關鍵。用戶身份鏈接（user identity linkage）的目的是檢測來自不同社交網絡平臺的同一個用戶。基于深度學習的跨社交網絡用戶對齊技術，很好地學習了不同社交網絡的結構特征，實現了跨社交網絡的用戶對齊。將該技術用于同一社交網絡匿名用戶識別，實驗結果優于傳統去匿名方法。

匿名；去匿名；隱私；社交網絡；圖數據

1 引言

隨著互聯網技術的發展，基于社交網絡大數據的應用，在為各行各業帶來巨大收益的同時，推動著大數據分析在各行業中的應用和進步。用戶隱私是大數據行業的一個關鍵問題，社交網絡從一開始出現就與這個問題息息相關，在未來挖掘和研究社交數據的道路上，只有注重對用戶隱私的保護[1]，才能形成可持續的研究與發展。

社交網絡可以用圖結構來表示，用節點來表示用戶，邊來表示用戶關系。許多網絡的研究可以抽象成基于圖結構網絡的研究，如Wi-Fi軌跡、藍牙軌跡、即時消息、社交網絡等。

在對基于圖結構網絡的研究過程中，為了保護用戶的隱私，會對網絡進行匿名處理。通過對匿名社交網絡進行去匿名，可以測試匿名技術的效果，從而促進匿名技術的發展，更好地保護用戶的隱私。

Zhou等[2]提出的DeepLink是基于深度學習的跨社交網絡用戶對齊技術，充分地學習了不同社交網絡的結構特征，實現了跨社交網絡的用戶對齊。本文將DeepLink技術用于同一社交網絡匿名用戶識別，取得了不錯的結果。

2 相關工作

2.1 用戶身份鏈接技術

用戶身份鏈接的目的是檢測來自不同社交網絡平臺的同一個用戶。解決這一問題的方法眾多，主要有基于用戶特征的方法、基于用戶產生內容的方法、基于用戶行為的方法。此外，包括從有監督、無監督到基于子空間的學習方法。上述方法通常需要提取用戶相關特征（如用戶ID、昵稱、坐標、簽名、標簽、行為習慣等）來對不同社交網絡中的用戶進行建模。但這些特征主要基于先驗知識，而且會隨平臺和應用的變化而變化。

基于近年來自動提取特征方面的成功經驗，Zhou等[2]提出了基于深度神經網絡的用戶身份鏈接算法——DeepLink。它是一種半監督的學習方式，主要基于網絡結構，不涉及任何用戶特征提取與建模，在與IONE[3]、ONE[3]、MAH[4]、MAG[4]、CRW[5]等方法的對比實驗中效果突出。

2.2 圖數據去匿名技術

圖數據去匿名技術通過對比同一網絡的不同匿名圖，識別來自本網絡的用戶。現有的去匿名技術主要包括基于種子節點的去匿名技術和無種子節點的去匿名技術。

基于種子節點的去匿名技術首先將某些用戶識別為種子節點。Backstrom等[6]提出基于種子節點進行主動攻擊和被動攻擊，這種方法不可擴展，且容易防御。針對Backstrom的不足，Narayanan和Shmatikov[7]對其作出了改進，提出了可擴展的兩階段攻擊方法。Nilizadeh[8]等提出基于社區的去匿名方法，該方法也增強了其他基于種子節點的攻擊，如Srivatsa[9]和Ji[10]的方法。

無種子節點的去匿名關鍵在于對網絡結構的表示與學習[11]，現有的完全無種子節點去匿名技術相對較少。Pedarsani[12]主要依賴到其他節點的距離和度數來進行去匿名。Ji[10]提出的是一種基于冷啟動的優化算法。

3 基于DeepLink的去匿名方法設計

DeepLink具有良好的網絡學習與表示能力，本文將該方法用于社交網絡的去匿名。匿名社交網絡及其輔助網絡屬于同一社交網絡的不同匿名圖。

3.1 社交網絡匿名方法

采用Hay[13]提出來的方法對Twitter網絡進行匿名處理生成匿名網絡和輔助網絡。該方法是基于邊的匿名方法。首先隨機刪除一定數量的邊，其次隨機添加同樣數量的邊，該方法應用較為普遍。

3.2 網絡結構采樣

為了將用戶嵌入一個潛在的空間，通過隨機游走為每個用戶生成多個序列，每個序列都是對用戶社會關系的編碼，所有的序列合起來形成語料庫，并將其用來學習用戶的嵌入向量。

采樣過程如下：從一個隨機用戶開始，每一步沿著隨機選擇的邊進行，直到達到長度。這樣不僅可以提取隱藏的網絡結構，而且可以捕捉其所代表的社會信息，如網絡中的好友關系和社區屬性。

3.3 用戶向量嵌入

通過隨機游走獲取用戶語料庫之后，采用Skip-Gram模型來更新每個用戶的結構表示。

Skip-Gram是一種無監督學習技術，可以預測給定用戶的相鄰用戶。Skip-Gram可以表示為由輸入層、映射層（隱藏層）和輸出層組成的神經網絡。輸入層中每個用戶由One-hot編碼方式表示，即所有用戶均表示成一個維向量，其中，為用戶表中用戶的總數。在向量中，每個用戶都將與之對應的維度置為1，其余維度的值均為0。輸出層向量的值可以通過映射層向量（維），以及連接映射層和輸出層之間的×維權重矩陣計算得到。輸出層也是一個維向量，每維與用戶表中的一個用戶相對應。最后對輸出層向量應用softmax激活函數，可以計算每一個用戶的生成概率。訓練神經網絡的權重，使語料庫中所有用戶的整體生成概率最大，使網絡盡可能地預測所有用戶的社會信息。Skip-Gram最終的學習目的是通過訓練好神經網絡，獲得映射矩陣，將每個用戶映射到相應的特征向量。為了提高效率，采用負采樣的方法進行優化。

3.4 多層神經網絡

其中，為權重矩陣，為偏置向量，通過輪迭代直到收斂。將訓練好的神經網絡進行測試，即可評估本文方法的可行性。

4 實驗

實驗使用NIlizadeh[8]提供的Twitter數據集，該數據集包括9 745個用戶和50 164種用戶關系。通過Hay等[13]提出的匿名算法，從網絡中隨機刪除、增加15%的邊，分別產生匿名網絡與輔助網絡。本實驗為了充分獲取結構信息，對網絡進行了10輪的隨機游走，游走長度為40。

實驗選取5%的錨節點作為訓練集，95%的節點用來測試。測試的指標選取Precision@(P@)。P@k可以用來衡量用戶識別的準確率，如式(3)所示。

（1）維度對結果的影響

本文研究了用戶嵌入向量的維度對準確率的影響，結果如表1所示。本實驗中，當維度為100時，效果最好。實驗結果表明：不是維度越高，準確率越高。

表1 維度與準確率的關系

（2）迭代輪數對結果的影響

本文研究了迭代次數對準確率的影響，實驗結果如圖1所示。該實驗中，用戶嵌入向量的維度為50。實驗結果表明：隨著訓練輪數的上升，各個準確度指標都有所提高，在接近10 000輪訓練的時候，準確度趨于穩定。

表2 本文方法與DeepLink對比

（3）與DeepLink實驗對比

本文對比了DeepLink在不同的兩個場景下的表現，兩個場景分別是本文中提出的同質網絡和文獻[2]中使用的非同質網絡。對比結果如表2所示。對比結果表示DeepLink在同質網絡中取得了更好的結果。原因在于本文中的匿名網絡和輔助網絡屬于同一個社交網絡，結構比較相似，DeepLink能夠充分地利用網絡結構信息。

圖1 迭代次數與準確率關系

Figure 1 The relationship between iterations and accuracy

（4）與Ji[8]、Nilizadeh[9]實驗對比

本節將本文方法與Ji、Nilizadeh的方法進行對比，結果如表3所示。實驗中數據集相同，匿名圖與輔助圖也相同。實驗結果表明，本文的方法與Nilizadeh的實驗結果一樣，比Ji的方法準確率高。

表3 本文方法與Ji、Nilizadeh對比

5 結束語

本文將Deeplink技術用于同一社交網絡匿名使用戶識別，實驗結果表明，DeepLink方法在社交網絡去匿名應用中處于領域領先水平。該方法能夠充分學習網絡的結構信息，雖然種子節點只有5%，但實驗結果仍然較好。

該方法還有值得進一步討論與改進的地方。一是可以增加改動的邊數來提高網絡的匿名水平。二是可以采用不同的匿名方法對社交網絡進行匿名處理，研究該方法對不同匿名技術的還原能力。三是可以采用LINE[14]、GraRep[15]等其他方法生成用戶節點的語料庫，探索節點表示的其他可能性。四是可以增加種子節點的比例來探究網絡的去匿名能力。

[1] 姚瑞欣, 李暉, 曹進. 社交網絡中的隱私保護研究綜述[J]. 網絡與信息安全學報, 2016, 2(4): 33-43.

YAO R X, LI H, CAO J. Overview of privacy preserving in social network[J]. Chinese Journal of Network and Information Security, 2016, 2(4): 33-43.

[2] ZHOU F, LIU L. DeepLink: a deep learning approach for user identity linkage[C]//IEEE International Conference on Computer Communications. 2018: 1313-1321.

[3] LIU L, CHEUNG W K, LI X, et al. Aligning users across social networks using network embedding[C]//International Joint Conference on Artificial Intelligence. 2016: 1774-1780.

[4] TAN S, GUAN Z, CAI D, et al. Mapping users across networks by manifold alignment on hypergraph[C]//AAAI Conference on Artificial Intelligence. 2014: 159-165.

[5] ZHANG J, YU P S. Integrated anchor and social link predictions across social networks[C]//International Joint Conference on Artificial Intelligence. 2015: 2125-2132.

[6] BACKSTROM L, DWORK C, KLEINBERG J. Wherefore art thou r3579x? anonymized social networks, hidden patterns, and structural steganography[C]//International World Wide Web Conference. 2007: 181-190.

[7] NARAYANAN A, SHMATIKOV V. De-anonymizing social networks[C]//IEEE Symposium on Security and Privacy. 2009: 173-187.

[8] NILIZADEH S, KAPADIA A, AHN Y Y. Community-enhanced de-anonymization of online social networks[C]//ACM Conference on Computer and Communications Security. 2014: 537-548.

[9] SRIVATSA M, HICKS M. Deanonymizing mobility traces: using social networks as a side-channel[C]//ACM Conference on Computer and Communications Security. 2012: 628-637.

[10] JI S, LI W, SRIVATSA M, et al. Structure based data de-anonymization of social networks and mobility traces[C]//Information Security Conference. 2014: 237-254.

[11] 尹贏, 吉立新, 黃瑞陽, 等. 網絡表示學習的研究與發展[J]. 網絡與信息安全學報, 2019, 5(2): 77-87.

YIN Y, JI L X, HUANG R Y, et al. Research and development of network representation learning[J]. Chinese Journal of Network and Information Security, 2019, 5(2): 77-87.

[12] PEDARSANI P, FIGUEIREDO D R, GROSSGLAUSER M. A bayesian method for matching two similar graphs without seeds[C]//The 51st Annual Allerton Conference on Communication, Control & Computing. 2013: 1598-1607.

[13] HAY M, MIKLAU G, JENSEN D, et al. Anonymizing social networks[C]// Computer Science Department Faculty Publication Series. 2007: 180-196.

[14] TANG J, QU M, WANG M, et al. Line: large- scale information network embedding[C]//International World Wide Web Conference. 2015: 1067-1077.

[15] CAO S, LU W, XU Q. Grarep: learning graph representations with global structural information[C]//ACM International on Conference on Information & Knowledge Management. 2015: 891-900.

De-anonymiation method for networks based on DeepLink

WANG Pei, JIA Yan, LI Aiping, JIANG Qianyue

College of Computer, National University of Defense Technology, Changsha 410073, China

Existing de-anonymization technologies are mainly based on the network structure. To learn and express network structure is the key step of de-anonymization. The purpose of the user identity linkage is to detect the same user from different social networking platforms. DeepLink is a cross-social network user alignment technology. It learns the structural of the social networks and align anchor nodes through deep neural networks. DeepLink was used to identify de-anonymization social networks, and the results outperforms the traditional methods.

anonymization, de-anonymization, privacy, social network, graph data

s: The National Key R&D Program of China (2017YFB0802204, 2016YFB0800303, 2017YFB0803301, 2016QY03D0603, 2016QY03D0601, 2016QY01W0101), The National Natural Science Foundation of China ( 61732004, 61732022, 61502517, 61472433, 61672020, U1803263), DongGuan Innovative Research Team Program (2018607201008)

TP183

A

10.11959/j.issn.2096?109x.2020045

王培（1991? ），男，山西運城人，國防科技大學碩士生，主要研究方向為網絡空間安全。

賈焰（1960? ），女，四川成都人，博士，國防科技大學教授、博士生導師，主要研究方向為網絡空間安全。

李愛平（1974? ），男，山東諸城人，博士，國防科技大學研究員、博士生導師，主要研究方向為網絡空間安全。

蔣千越（1990? ）男，黑龍江齊齊哈爾人，國防科技大學碩士生，主要研究方向為網絡空間安全。

論文引用格式：王培, 賈焰, 李愛平, 等. 基于DeepLink的社交網絡去匿名方法[J]. 網絡與信息安全學報, 2020, 6(4): 104-108.

WANG P, JIA Y, LI A P, et al. De-anonymiation method for networks based on DeepLink[J]. Chinese Journal of Network and Information Security, 2020, 6(4): 104-108.

2019?07?16；

2019?09?17

李愛平，liaiping@nudt.edu.cn

國家重點研究發展計劃基金（2017YFB0802204, 2016YFB0800303, 2017YFB0803301, 2016QY03D0603, 2016QY03D0601, 2016QY01W0101）；國家自然科學基金（61732004, 61732022, 61502517, 61472433, 61672020, U1803263）；東莞創新研究團隊計劃（2018607201008）