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

基于DeepLink的社交網(wǎng)絡(luò)去匿名方法

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

（國防科技大學(xué)計算機(jī)學(xué)院，湖南 長沙 410073）

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

匿名；去匿名；隱私；社交網(wǎng)絡(luò)；圖數(shù)據(jù)

1 引言

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

社交網(wǎng)絡(luò)可以用圖結(jié)構(gòu)來表示，用節(jié)點(diǎn)來表示用戶，邊來表示用戶關(guān)系。許多網(wǎng)絡(luò)的研究可以抽象成基于圖結(jié)構(gòu)網(wǎng)絡(luò)的研究，如Wi-Fi軌跡、藍(lán)牙軌跡、即時消息、社交網(wǎng)絡(luò)等。

在對基于圖結(jié)構(gòu)網(wǎng)絡(luò)的研究過程中，為了保護(hù)用戶的隱私，會對網(wǎng)絡(luò)進(jìn)行匿名處理。通過對匿名社交網(wǎng)絡(luò)進(jìn)行去匿名，可以測試匿名技術(shù)的效果，從而促進(jìn)匿名技術(shù)的發(fā)展，更好地保護(hù)用戶的隱私。

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

2 相關(guān)工作

2.1 用戶身份鏈接技術(shù)

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

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

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

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

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

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

3 基于DeepLink的去匿名方法設(shè)計

DeepLink具有良好的網(wǎng)絡(luò)學(xué)習(xí)與表示能力，本文將該方法用于社交網(wǎng)絡(luò)的去匿名。匿名社交網(wǎng)絡(luò)及其輔助網(wǎng)絡(luò)屬于同一社交網(wǎng)絡(luò)的不同匿名圖。

3.1 社交網(wǎng)絡(luò)匿名方法

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

3.2 網(wǎng)絡(luò)結(jié)構(gòu)采樣

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

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

3.3 用戶向量嵌入

通過隨機(jī)游走獲取用戶語料庫之后，采用Skip-Gram模型來更新每個用戶的結(jié)構(gòu)表示。

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

3.4 多層神經(jīng)網(wǎng)絡(luò)

其中，為權(quán)重矩陣，為偏置向量，通過輪迭代直到收斂。將訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)進(jìn)行測試，即可評估本文方法的可行性。

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

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

實(shí)驗(yàn)選取5%的錨節(jié)點(diǎn)作為訓(xùn)練集，95%的節(jié)點(diǎn)用來測試。測試的指標(biāo)選取Precision@(P@)。P@k可以用來衡量用戶識別的準(zhǔn)確率，如式(3)所示。

（1）維度對結(jié)果的影響

本文研究了用戶嵌入向量的維度對準(zhǔn)確率的影響，結(jié)果如表1所示。本實(shí)驗(yàn)中，當(dāng)維度為100時，效果最好。實(shí)驗(yàn)結(jié)果表明：不是維度越高，準(zhǔn)確率越高。

表1 維度與準(zhǔn)確率的關(guān)系

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

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

表2 本文方法與DeepLink對比

（3）與DeepLink實(shí)驗(yàn)對比

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

圖1 迭代次數(shù)與準(zhǔn)確率關(guān)系

Figure 1 The relationship between iterations and accuracy

（4）與Ji[8]、Nilizadeh[9]實(shí)驗(yàn)對比

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

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

5 結(jié)束語

本文將Deeplink技術(shù)用于同一社交網(wǎng)絡(luò)匿名使用戶識別，實(shí)驗(yàn)結(jié)果表明，DeepLink方法在社交網(wǎng)絡(luò)去匿名應(yīng)用中處于領(lǐng)域領(lǐng)先水平。該方法能夠充分學(xué)習(xí)網(wǎng)絡(luò)的結(jié)構(gòu)信息，雖然種子節(jié)點(diǎn)只有5%，但實(shí)驗(yàn)結(jié)果仍然較好。

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

[1] 姚瑞欣, 李暉, 曹進(jìn). 社交網(wǎng)絡(luò)中的隱私保護(hù)研究綜述[J]. 網(wǎng)絡(luò)與信息安全學(xué)報, 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] 尹贏, 吉立新, 黃瑞陽, 等. 網(wǎng)絡(luò)表示學(xué)習(xí)的研究與發(fā)展[J]. 網(wǎng)絡(luò)與信息安全學(xué)報, 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? ），男，山西運(yùn)城人，國防科技大學(xué)碩士生，主要研究方向?yàn)榫W(wǎng)絡(luò)空間安全。

賈焰（1960? ），女，四川成都人，博士，國防科技大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)空間安全。

李愛平（1974? ），男，山東諸城人，博士，國防科技大學(xué)研究員、博士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)空間安全。

蔣千越（1990? ）男，黑龍江齊齊哈爾人，國防科技大學(xué)碩士生，主要研究方向?yàn)榫W(wǎng)絡(luò)空間安全。

論文引用格式：王培, 賈焰, 李愛平, 等. 基于DeepLink的社交網(wǎng)絡(luò)去匿名方法[J]. 網(wǎng)絡(luò)與信息安全學(xué)報, 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

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