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

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

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

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

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

現(xiàn)有的社交網絡去匿名方法主要是基于網絡結構，對網絡結構進行學習與表示是去匿名的關鍵。用戶身份鏈接（user identity linkage）的目的是檢測來自不同社交網絡平臺的同一個用戶?；谏疃葘W習的跨社交網絡用戶對齊技術，很好地學習了不同社交網絡的結構特征，實現(xiàn)了跨社交網絡的用戶對齊。將該技術用于同一社交網絡匿名用戶識別，實驗結果優(yōu)于傳統(tǒng)去匿名方法。

匿名；去匿名；隱私；社交網絡；圖數(shù)據(jù)

1 引言

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

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

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

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

2 相關工作

2.1 用戶身份鏈接技術

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

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

2.2 圖數(shù)據(jù)去匿名技術

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

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

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

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

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

3.1 社交網絡匿名方法

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

3.2 網絡結構采樣

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

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

3.3 用戶向量嵌入

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

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

3.4 多層神經網絡

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

4 實驗

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

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

（1）維度對結果的影響

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

表1 維度與準確率的關系

（2）迭代輪數(shù)對結果的影響

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

表2 本文方法與DeepLink對比

（3）與DeepLink實驗對比

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

圖1 迭代次數(shù)與準確率關系

Figure 1 The relationship between iterations and accuracy

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

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

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

5 結束語

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

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

[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] 尹贏, 吉立新, 黃瑞陽, 等. 網絡表示學習的研究與發(fā)展[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

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