高 偉,張 敏

1(中國科學(xué)院大學(xué),北京 100049)

2(中國科學(xué)院 軟件研究所,北京 100190)

基于推文與屬性的社交網(wǎng)絡(luò)用戶重識別方法①

高 偉1,2,張 敏2

1(中國科學(xué)院大學(xué),北京 100049)

2(中國科學(xué)院 軟件研究所,北京 100190)

大數(shù)據(jù)隱私安全正成為各界關(guān)注的熱點. 攻擊者通過識別用戶不同網(wǎng)站的賬戶,可以構(gòu)建用戶的完整畫像,對用戶隱私形成威脅. 模擬評估攻擊者的重識別能力是進行用戶隱私保護的前提. 因此,本文提出一種高相似同天同行為算法. 該算法通過檢測賬戶在不同網(wǎng)站是否存在多次同天發(fā)表相近或相同內(nèi)容的行為,判斷賬戶是否屬于同一用戶,并通過為用戶屬性構(gòu)建一種權(quán)重計算模型,進一步提高用戶重識別的準(zhǔn)確率. 經(jīng)過對兩個國內(nèi)主流社交網(wǎng)站的一萬多用戶進行實驗,本文算法表現(xiàn)出良好的效果. 實驗表明,即使不考慮用戶社交關(guān)系,用戶的推文與屬性依然提供了足夠的信息使攻擊者將用戶不同網(wǎng)站的賬戶相關(guān)聯(lián),從而導(dǎo)致更多的隱私被泄露.

社交網(wǎng)絡(luò); 用戶重識別; 推文; 屬性; 相似度

1 引言

目前社交網(wǎng)絡(luò)已廣泛普及. 截止2016年,全球最大社交網(wǎng)站facebook月活躍用戶數(shù)已突破16.5億,新浪微博、QQ月活躍用戶分別突破了3.9億、8.5億,社交網(wǎng)絡(luò)的迅猛發(fā)展為社會帶來了巨大機遇. 在社交網(wǎng)絡(luò)上,每天有大規(guī)模數(shù)據(jù)產(chǎn)生,如推文內(nèi)容、簽到信息、照片等. 隨著“云計算”和“大數(shù)據(jù)”技術(shù)的不斷深入,眾多研究機構(gòu)、高校、互聯(lián)網(wǎng)公司開始廣泛搜集這些碎片化信息,通過對這些大規(guī)模數(shù)據(jù)的建模分析,可以了解用戶多維度的的畫像,如購物習(xí)慣、興趣愛好等,以此進行廣告精準(zhǔn)投放或者好友推薦等,具有極大的商業(yè)價值和實用價值.

但這同時也帶來了用戶隱私泄露的威脅. 攻擊者采集用戶不同網(wǎng)站的信息,通過對這些信息的鏈接并加以建模抽象,可構(gòu)建用戶的完整畫像. 當(dāng)攻擊者對這些信息進行非法利用時,會嚴(yán)重破壞用戶的隱私,甚至直接威脅到用戶的人身財產(chǎn)安全. 因此,保護用戶隱私就顯得相當(dāng)重要. 在此情形下為保護用戶隱私,需首先了解,攻擊者判定來源于不同社交網(wǎng)站的賬戶屬于同一人所采用的技術(shù)手段,即用戶重識別技術(shù).

用戶重識別就是通過采集多個社交網(wǎng)站的數(shù)據(jù),通過對這些公開數(shù)據(jù)的比對,來識別用戶不同網(wǎng)站賬戶的一種技術(shù). 目前,用戶重識別技術(shù)正受到國內(nèi)外前所未有的關(guān)注. 2009年Jan[1]分別采用不同精度的匹配方法對Facebook和StudiVZ社交網(wǎng)站的用戶姓名、生日、性別、高中、地址等進行了相似度計算,并結(jié)合權(quán)重完成了用戶的重識別工作. 2013年Goga[2]提出了基于多社交網(wǎng)站大規(guī)模賬戶的相關(guān)性識別算法. 分別采用Jaro Distance、哈希感知算法等對用戶姓名、用戶頭像及其他屬性進行了相似度計算,最后采用機器學(xué)習(xí)方法進行用戶的匹配. 2013年Goga[3]根據(jù)用戶推文的地理位置、發(fā)表時間和內(nèi)容風(fēng)格對Twitter、Flickr、Yelp的用戶展開重識別研究. 2014年Cecaj[4]根據(jù)用戶電話記錄與推文記錄的發(fā)生時間差?t和距離差?s,對某地區(qū)的用戶進行重識別. 基于社交關(guān)系的用戶重識別主要根據(jù)用戶在不同的社交網(wǎng)絡(luò)有著相似的朋友圈這一經(jīng)驗,通過選定部分已知種子匹配用戶,根據(jù)網(wǎng)絡(luò)拓?fù)潢P(guān)系、圖結(jié)點的度數(shù)等進行用戶的重識別研究. 如2009年Narayanan[5]提出的基于種子匹配的重識別算法,2016年Zhou[6]提出的基于好友相似度的重識別算法FRUI. 2012年Bartunov[7]利用用戶屬性和社交關(guān)系綜合計算了Facebook和Twitter的用戶相似度.2013年Kong[8]將用戶的發(fā)推地理位置變化規(guī)律、時間變化規(guī)律、推文內(nèi)容關(guān)鍵字出現(xiàn)頻率相結(jié)合,完成用戶的匹配工作. Fu[9]利用用戶屬性、社交關(guān)系,采用圖結(jié)點算法進行了用戶重識別研究.

以上方案基于不同特征對用戶重識別進行了研究,但在推文方面,用戶重識別的準(zhǔn)確率還較低,利用用戶發(fā)布的大量推文進一步提高準(zhǔn)確率仍有很大探索空間.此外,用戶屬性包含著一個人的重要信息,對用戶重識別具有一定的意義. 然而隨著社交網(wǎng)絡(luò)的不斷發(fā)展,用戶的安全意識越來越強,很多用戶的關(guān)鍵屬性信息被隱藏,為這些僅存的屬性信息構(gòu)建權(quán)重計算模型,面臨著較大的困難.

為解決以上問題,本文提出一種高相似同天同行為算法. 該算法通過檢測賬戶在不同網(wǎng)站是否存在多次同天發(fā)表相近或相同內(nèi)容的行為,判斷賬戶是否屬于同一用戶. 此外,為利用用戶屬性進一步提高重識別準(zhǔn)確率,本文構(gòu)建了一種屬性權(quán)重計算模型. 為評估所提算法的性能,本文以國內(nèi)兩個主流的社交網(wǎng)站(以下簡稱“Q”、“R”)作為實驗對象,分別采集了 Q 網(wǎng)站的16173個用戶的300余萬推文、R網(wǎng)站的10027個用戶的70余萬推文,經(jīng)人工標(biāo)注了776對真實匹配用戶.實驗表明,本文所提算法有著良好的效果,明顯優(yōu)于其他模型.

2 用戶重識別方法

本文提出的用戶重識別方法主要基于用戶發(fā)表的推文與用戶屬性,并在此基礎(chǔ)上,將二者結(jié)合進行用戶重識別. 首先,定義以下基本符號.

2.1 符號定義

2.2 基于推文的用戶重識別方法

推文內(nèi)容與用戶聯(lián)系緊密,不同的用戶其推文內(nèi)容也顯示出較大差異,因此在一定程度上,推文內(nèi)容可以反映用戶特征、代表用戶身份. 基于推文的用戶重識別方法包括四部分. 1) 推文向量及相似度計算方法.通過word2vec[10,11]工具訓(xùn)練獲得每個詞的向量,然后將推文中詞的向量累加得到推文的向量,推文相似度采用推文向量夾角的余弦值來表示. 2) 高相似同天同行為計算方法. 很多用戶都有在同一日期于不同社交網(wǎng)站發(fā)表相似推文的經(jīng)歷,因此在一定意義上,高相似的推文對可以為用戶重識別提供線索. 該方法正是基于此思想,發(fā)現(xiàn)具有相同發(fā)推日期的高相似推文對. 3)熱點事件處理方法. 在一些特殊節(jié)日、熱點事件時,大量相似的推文會同時出現(xiàn)于不同的社交網(wǎng)站,將嚴(yán)重影響用戶的重識別結(jié)果,因此該方法根據(jù)一定條件對與熱點事件有關(guān)的推文記錄進行刪除,以降低其負(fù)面影響. 4) 高相似多推文計算方法. 用戶在兩個社交網(wǎng)站的推文在整體上具有一致的情感、用詞習(xí)慣等,所以對于不同網(wǎng)站的賬戶,可以根據(jù)它們推文的整體相似度,展開用戶重識別的研究工作.

2.2.1 推文向量及相似度計算方法

為計算推文相似度,需要首先將推文內(nèi)容使用數(shù)字向量表示. 因此,推文相似度的計算就轉(zhuǎn)化為數(shù)字向量的計算. 根據(jù)推文的特點,本文將按照圖1所示流程進行推文向量的計算.

圖1 推文向量計算圖

預(yù)處理: 去除推文中的亂碼、符號. 如果推文只包含亂碼或者符號等非文字性語言,則不做處理.

分詞: 采用ICTCLAS分詞工具將推文分為單獨的詞.

詞向量獲取: 從已訓(xùn)練好的詞向量表中獲取對應(yīng)詞的數(shù)字向量. 該表中的詞向量是利用Google的開源工具word2vec,經(jīng)過對20G大規(guī)模維基百科語料訓(xùn)練而成,其包含每個詞的50維度語義向量.

推文向量計算: 推文由詞組成,其中每個詞的向量為:

推文的向量由各個詞的向量累加而成,即:

本文曾將每條推文看作一個文本,所有推文看作文檔總數(shù)據(jù)集. 利用TF-IDF算法計算每個詞在對應(yīng)推文中的權(quán)重,將權(quán)重乘以對應(yīng)詞的向量得到該詞在推文中的語義向量,然后將推文中所有的詞向量累加,得到該推文的向量. 但在后續(xù)實驗中,其效果與直接將詞向量累加得到的推文向量所進行的實驗效果幾乎一致.經(jīng)分析,其原因可能有以下兩種: 1) 大部分推文屬于短文本,用戶在不同網(wǎng)站同天發(fā)表相近含義的推文時,用詞基本一致,極少部分用詞不一致的相似推文也只是一些非關(guān)鍵詞不同,對用戶重識別的影響很小. 2) 如果推文屬于長文本,用戶往往在另一個網(wǎng)站發(fā)表的是該推文的拷貝版本,二者完全相同. 所以,出于算法與系統(tǒng)的整體效率考慮,本文采用將詞向量直接累加的結(jié)果來表示推文向量.

2.2.2 高相似同天同行為計算方法

為開展Q與R網(wǎng)站用戶的重識別工作,定義以下概念:

(3) 高相似次數(shù): 用戶UQi與URj具有的高相似同天同行為推文對的總次數(shù),稱為該用戶對的高相似次數(shù).

基于推文的用戶重識別研究方法需要首先計算Q網(wǎng)站每個用戶UQi與R網(wǎng)站所有用戶的高相似同天同行為,其原理如圖2所示.

圖2中白色部分與灰色部分對稱,分別表示Q、R網(wǎng)站的推文信息. 其中白色部分從左至右的每一列分別表示: Q網(wǎng)站用戶發(fā)推日期Tx列表、日期Tx對應(yīng)的推文集合TWQx列表、推文集合TWQx包含的推文twqh列表. 其中“×”表示對推文集合計算笛卡爾積,然后計算結(jié)果集中每個推文對元素的相似度. 完成以上計算后,判斷該推文對元素是否屬于高相似同天同行為,是則保存,否則丟棄.

圖2 所有用戶的高相似同天同行為計算圖

其偽代碼算法如下:

Algorithm 1. High Similarity 1.For c= 0to n do2. TQ=TQ∪TQc#計算Q網(wǎng)站所有用戶的發(fā)推日期并集3.End For4.For d= 0to m do5. TR=TR∪TRd# 計算R網(wǎng)站所有用戶的發(fā)推日期并集6.End For7.TQR=TQ∩TR# 計算Q與R網(wǎng)站用戶發(fā)推日期的交集8.For each Tx∈TQR do9.TWQR=TWQx×TWRx# 作笛卡爾積得到同天同行為推文對10. For each pair of(twqf,twre) ∈TWQR11. If Sim(twqf,twre) >S# 判斷是否高相似12. getUsers(twqf,twre) #獲取推文所屬用戶UQi,URj13. store(UQi,URj,Tx,twqf,twre,Sim(twqf,twre)) #存儲信息14. End If15. End For16.End For

經(jīng)過以上計算,即可得到Q網(wǎng)站的每一個用戶UQi與R網(wǎng)站所有用戶的高相似同天同行為.

2.2.3 熱點事件處理方法

在特殊節(jié)日、熱點事件時,很多用戶都會發(fā)表含義相近的推文于不同網(wǎng)站. 在這種情形下,一個用戶會與很多用戶存在高相似同天同行為,而大部分用戶是非真實匹配用戶. 如果以此為基礎(chǔ),根據(jù)用之間的高相似次數(shù)決定匹配用戶,其結(jié)果很有可能是不準(zhǔn)確的,同時這些過多的干擾數(shù)據(jù),也會給系統(tǒng)的運行帶來壓力,增大損耗. 如圖3所示的真實案例.

圖3 用戶UQ0經(jīng)高相似同天同行為方法計算后的結(jié)果表

由圖可知,Q網(wǎng)站用戶UQ0共有兩條推文產(chǎn)生高相似同天同行為,對應(yīng)R網(wǎng)站的6個候選匹配用戶,且高相似次數(shù)都為1. 按照常理判斷,其最可能的匹配用戶應(yīng)該是UR0. 因為UR0與UQ0對應(yīng)的高相似推文相對其它推文,出現(xiàn)率較低. 且其余候選匹配用戶的發(fā)推日期均相同,推文互相之間也都是高相似的,所以對應(yīng)的推文極有可能描述的是同一熱點事件. 如果不對該類推文進行處理,算法隨機選擇匹配用戶,能準(zhǔn)確識別的概率僅為1/6,但如果將該類推文記錄刪除,算法就能準(zhǔn)確識別UQ0的匹配用戶.

因此,對熱點事件進行處理很有必要. 首先需要明確熱點事件的判定條件. 一般從網(wǎng)絡(luò)角度而言,所謂熱點事件,就是有大量網(wǎng)民都在同一時間段內(nèi)發(fā)表有關(guān)該事件的推文、評論等. 所以,對于推文twz,判定其屬于熱點事件的條件為,由其產(chǎn)生的候選匹配用戶數(shù)|CandidateUsersz|大于某個系數(shù)時,即可判定該推文屬于熱點事件. 即:

α: 熱點事件系數(shù)(取值將在后續(xù)實驗中確定). 含義: 如果發(fā)表于日期Tm的推文twz產(chǎn)生多于α個候選匹配用戶,則該推文描述的內(nèi)容屬于熱點事件.

當(dāng)判定一條推文屬于熱點事件后,還需判定其是否滿足相應(yīng)處理條件,才能決定是否將其刪除,否則可能會降低用戶重識別結(jié)果的準(zhǔn)確率. 例如: 假設(shè)圖3中的用戶UR0沒有在2011-03-31發(fā)表如上推文,而是也在 2011-02-02 發(fā)表了類似“新年快樂”的推文. 此時,用戶UQ0的候選匹配用戶還是6個,都由推文“新年快樂！”產(chǎn)生,高相似次數(shù)也都為1,如果此時該推文滿足熱點事件的判定條件,將對應(yīng)推文記錄刪除,則用戶UQ0沒有了匹配用戶. 很明顯,相對于刪除前,算法的準(zhǔn)確率反而有所下降. 因此,對于熱點事件進行處理還需滿足相應(yīng)的處理條件.

假設(shè)Q網(wǎng)站用戶UQi經(jīng)過高相似同天同行為方法計算后,他在日期T0到Tm發(fā)表的推文產(chǎn)生了高相似同天同行為,且由這些推文產(chǎn)生的候選匹配用戶對應(yīng)的高相似次數(shù)分別為:

于日期Tx(0≤x≤m)發(fā)表的推文twz產(chǎn)生的候選匹配用戶對應(yīng)的高相似次數(shù)分別為:

當(dāng)以上高相似次數(shù)滿足如下條件時,推文twz對應(yīng)的高相似記錄應(yīng)該被刪除. 即:

以上式子中左側(cè)括號( )表示,由推文twz產(chǎn)生的候選匹配用戶的高相似次數(shù)之和不等于用戶UQi所有候選匹配用戶的高相似次數(shù)之和,即除了推文twz產(chǎn)生候選匹配用戶外,還有其他推文也產(chǎn)生了候選匹配用戶; 右側(cè)括號 ( )表示,由推文twz產(chǎn)生的候選匹配用戶的高相似次數(shù)兩兩相等. 當(dāng)以上兩個條件都成立時,才可對推文twz的相應(yīng)記錄執(zhí)行刪除操作. 因為此時,由推文twz產(chǎn)生的候選匹配用戶的高相似次數(shù)均相等,且除了該推文外,還有其他推文也產(chǎn)生了高相似同天同行為,所以執(zhí)行刪除操作后,不僅提高了算法的識別準(zhǔn)確率,還有效降低了因這些干擾數(shù)據(jù)帶來的系統(tǒng)損耗,提升了系統(tǒng)的整體運行效率.

經(jīng)過高相似同天同行為計算方法、熱點事件處理方法操作后,即可得到Q網(wǎng)站每個用戶UQi與其候選匹配用戶的高相似次數(shù).

2.2.4 高相似多推文計算方法

Q與R網(wǎng)站屬于類似的社交網(wǎng)站,用戶經(jīng)常在上面發(fā)表與生活、工作相關(guān)的推文. 因此如果兩個網(wǎng)站的某用戶屬于同一個人,則他們于各自平臺上的推文在整體上會展現(xiàn)出相似的情感、用詞習(xí)慣、行文風(fēng)格等特征.

根據(jù)調(diào)研,Q與R網(wǎng)站用戶的人均推文數(shù)都較少,大部分用戶的推文數(shù)小于50條,而每條推文的字?jǐn)?shù)也很少,所以一個用戶的推文總字?jǐn)?shù)也相對不多,經(jīng)統(tǒng)計,一般在500-2000之間. 推文的風(fēng)格與用戶的性格、發(fā)推時的心情、興趣愛好有很大關(guān)系,所以推文的格式也比較零散、隨意,且每條推文所表示的含義也不盡相同. 因此,如果將每個用戶的所有推文看作一個整體,很難通過提取一個明確的主題來表示用戶. 而word2vec工具在訓(xùn)練詞向量時,充分的考慮了上下文,所以在一定意義上,詞向量綜合了該詞多方面的因素.因此,根據(jù)推文特點,本文將對用戶所有推文的詞向量進行累加,將所得結(jié)果稱為用戶的多推文向量. 用戶的相似度采用多推文向量的相似度表示,具體計算方式如下所示.

假設(shè)Q網(wǎng)站用戶UQi與R網(wǎng)站用戶URj的推文集合分別為:

則UQi與URj的多推文相似度為:

根據(jù)高相似次數(shù)、多推文相似度在重識別用戶時所占的重要程度,分別賦予不同的權(quán)重,通過綜合計算得到用戶之間的相似度. 然后選擇與用戶UQi相似度最大的用戶,作為其匹配用戶.

2.3 基于屬性的用戶重識別方法

用戶屬性往往包含著一個人的重要信息,它在用戶重識別領(lǐng)域扮演著重要角色. 本文將利用同時存在于Q與R網(wǎng)站的屬性: 昵稱、性別、生日、情感狀態(tài)、家鄉(xiāng)、所在地展開用戶重識別研究. 其主要步驟如圖4所示.

圖4 基于屬性的用戶相似度計算流程圖

預(yù)處理: 將屬性處理為統(tǒng)一格式,如生日: yyyymm-dd、家鄉(xiāng): **省**市

各屬性相似度計算:

圖5 昵稱相似度計算規(guī)則圖

對于英文昵稱,由于其代表含義廣泛,且很多屬于用戶自創(chuàng),難以根據(jù)語義進行相似度度量. 因此本文采用流行的最小編輯距離算法計算其相似度. 對于中文昵稱,由于Q網(wǎng)站的用戶昵稱往往非真實姓名,而R網(wǎng)站屬于實名制社交平臺,用戶昵稱往往是真實姓名,因此,二者相似度可比較性較小,本文采用精確匹配進行比較. 對于其它格式的昵稱,本文不進行比較,將其相似度置為0.

(2) 性別、生日、情感狀態(tài)、家鄉(xiāng)、所在地: 由于這5項屬性均由用戶通過下拉列表選擇,所以經(jīng)過預(yù)處理后,均具有統(tǒng)一的格式. 因此,本文將采用精確匹配的方式計算其相似度.

各屬性權(quán)重計算:

由于每個社交網(wǎng)站的定位不同,所以其開放程度也不同. 而開放程度的不同將直接影響用戶屬性填寫的完整程度. 如微博是開放的社交網(wǎng)站,任何人均可訪問其他用戶的屬性頁面,所以出于隱私保護的目的,用戶將生日、身份證號碼等敏感屬性選擇空置或者隱藏,因此這些屬性的填寫率很低; 而像如昵稱、性別等與用戶隱私程度關(guān)聯(lián)不密切的屬性,填寫率會相對較高.據(jù)此猜想: 一個社交網(wǎng)站中,如果用戶的某項屬性填寫率越低,則說明該屬性的隱私程度越高,在標(biāo)識其身份的唯一性時,所占權(quán)重應(yīng)該越大. 根據(jù)此猜想,用戶各屬性權(quán)重模型的構(gòu)建,可分為以下三個步驟:

① 選擇社交網(wǎng)站用戶數(shù)據(jù)集;

② 統(tǒng)計各屬性填寫率;

③ 計算各屬性權(quán)重——填寫率倒數(shù)和歸一化.

表1以R網(wǎng)站的數(shù)據(jù)集(共10027個用戶)為例,計算各屬性權(quán)重.

表1 R 網(wǎng)站的屬性權(quán)重計算表

表1中,共包含6種屬性,第二行的數(shù)字代表填寫了對應(yīng)屬性的用戶數(shù),第三行表示經(jīng)過計算后,每種屬性的歸一權(quán)重. 其中,各屬性的歸一權(quán)重計算方式如下:

① 填寫率倒數(shù)和歸一化,即:

② 求得p,然后將屬性填寫率的倒數(shù)與p進行乘積計算,結(jié)果即為該屬性的歸一權(quán)重.

用戶相似度:

根據(jù)以上內(nèi)容,可求得每對屬性的相似度大小及各屬性在標(biāo)識用戶身份唯一性時所占的權(quán)重. 則基于屬性的用戶相似度可表示為:

基于屬性的用戶重識別研究正是基于以上方法,計算Q網(wǎng)站的每個用戶UQi與R網(wǎng)站的所有用戶之間的相似度,然后將UQi的候選匹配用戶按照相似度大小進行排序,選擇排序最高者作為UQi的匹配用戶.

2.4 基于推文與屬性相結(jié)合的用戶重識別方法

前面章節(jié)分別敘述了基于推文、屬性進行用戶重識別的詳細方法. 本節(jié)將推文與屬性相結(jié)合,共同進行跨社交網(wǎng)站的用戶重識別研究.

在基于推文的用戶重識別中,如果兩個來自不同社交網(wǎng)站的用戶在同一日期發(fā)表的推文屬于高相似同天同行為,且推文內(nèi)容與熱點事件無關(guān),則他們很可能屬于同一人,而當(dāng)這樣的事件多次發(fā)生時,則他們屬于同一人的概率幾乎接近于1. 而多推文相似度雖然在一定程度上可以代表用戶相似度,但也存在明顯缺陷,例如一個用戶的Q網(wǎng)站推文很多,而R網(wǎng)站推文很少,則它們的多推文向量將相差很大,所以較難取得準(zhǔn)確匹配. 而在屬性方面,由于同時出現(xiàn)于兩個網(wǎng)站的各屬性在標(biāo)志用戶身份的唯一性時,權(quán)重均很低,且在這6項屬性中,很多用戶會具有多項相同屬性,所以單獨使用屬性進行用戶重識別研究也難以取得良好效果.

因此,將推文與屬性相結(jié)合進行用戶重識別的研究,高相似次數(shù)對匹配結(jié)果的準(zhǔn)確率貢獻很大,而多推文相似度與基于屬性的用戶相似度貢獻都較小. 因此,當(dāng)計算用戶之間的相似度得分時,本文將分別賦予它們0.8、0.1、0.1的權(quán)重,以表示它們在衡量用戶相似度時的貢獻. 因此當(dāng)高相似次數(shù)為0時,用戶之間的相似度理論上最大是0.2,這一值在衡量用戶的相似度時,說服力很小. 所以本文將只對用戶之間的高相似次數(shù)大于0的用戶對計算相似度得分,然后將每個UQi用戶的候選匹配用戶按照分值大小進行排序,選擇排序最高者作為UQi的最終匹配用戶.

3 實驗結(jié)果與分析

3.1 數(shù)據(jù)集

為評估所提算法的效果,本文以國內(nèi)流行的社交網(wǎng)站Q、R作為實驗對象. 首先對其進行數(shù)據(jù)采集,并人工標(biāo)注真實匹配用戶對,根據(jù)上述的用戶重識別算法進行實驗,統(tǒng)計識別結(jié)果中真實匹配用戶的對數(shù),以驗證本文所提算法的可行性和有效性. 由于多推文相似度、基于屬性的用戶相似度在單獨進行用戶重識別時,效果較差,所以本文將它們與高相似同天同行為計算方法、熱點事件處理方法相結(jié)合進行用戶的重識別實驗.

經(jīng)調(diào)研,Q網(wǎng)站的主要用戶群是18-28歲的年輕人,R網(wǎng)站則主要是大學(xué)生、研究生及部分白領(lǐng)等. 因此,幾乎每個R網(wǎng)站的用戶均同時擁有Q網(wǎng)站的賬戶,所以它們非常適合作為用戶重識別實驗的數(shù)據(jù)來源.根據(jù)需求,本文采集的數(shù)據(jù)主要包含兩部分: (1) 推文信息; (2) 用戶屬性.

(1) 推文信息: 推文一般包含四類: 原創(chuàng)文字推文、原創(chuàng)多媒體推文、轉(zhuǎn)發(fā)文字推文、轉(zhuǎn)發(fā)多媒體推文.一般而言,原創(chuàng)推文在一定意義上唯一標(biāo)識了用戶身份,因此在推文方面,本文只采集原創(chuàng)文字推文與附帶的發(fā)表日期.

(2) 用戶屬性: 在屬性方面,本文只采集同時出現(xiàn)于兩網(wǎng)站的6種屬性: 昵稱、性別、生日、情感狀態(tài)、家鄉(xiāng)、所在地. 其中,昵稱由用戶自創(chuàng),可包含圖形、表情、文字、特殊符號等. 而其余5項均通過下拉列表選擇填入,具有固定的格式.

本文采用廣度優(yōu)先策略,通過爬蟲進行數(shù)據(jù)采集.從種子用戶開始,首先抓取其自身數(shù)據(jù),再抓取其好友的數(shù)據(jù),然后再抓取其好友的好友數(shù)據(jù),通過該種子用戶不斷的向外延伸,訪問不同的用戶. 抓取的數(shù)據(jù)總量如表2所示,Q網(wǎng)站用戶共抓取了16173個,以及這些用戶的300余萬原創(chuàng)文字推文,R網(wǎng)站用戶共抓取了10027個,推文約75萬. R網(wǎng)站推文數(shù)較少的原因可能有兩點: (1) 近些年,R 網(wǎng)站業(yè)績不斷下滑,導(dǎo)致用戶使用率較低; (2) 用戶只在上學(xué)時使用 R 網(wǎng)站,一般年限為 3-7 年,而之后便不再使用. 在 R 網(wǎng)站中,大部分用戶的主頁是開放的,任何人均可訪問. 而在Q網(wǎng)站中,大部分用戶的空間設(shè)置了訪問等級,如只對自己開放、只對其好友開放等,所以對于種子用戶,其好友的空間往往可以訪問,而其好友的好友空間,只有部分可以被訪問,所以在采集的數(shù)據(jù)中,真實匹配用戶數(shù)量較少,僅有人工標(biāo)注的776對.

表2 數(shù)據(jù)集總量統(tǒng)計表

Q與R網(wǎng)站用戶的單條推文長度與推文數(shù)一般都較小. 如由圖6可知,長度為10-20個字的推文占比最大,且隨著長度的增加,相應(yīng)推文逐漸減少,當(dāng)推文長度大于70時,相應(yīng)推文變多,其原因是此統(tǒng)計數(shù)包含了長度大于70的所有推文. 因此可知,Q與R網(wǎng)站推文大部分都是短文本,不適合使用LDA等模型表示推文,所以本文以詞向量累加的方式計算推文向量. 此外,Q網(wǎng)站推文的平均長度均大于R網(wǎng)站推文,其原因可能是: 相較于R網(wǎng)站,Q網(wǎng)站私密性更強,用戶更愿意將推文發(fā)表于Q網(wǎng)站. 由圖7可知,推文數(shù)小于50條的用戶占比最大,且隨著推文數(shù)的增加,相應(yīng)用戶逐漸減少. 經(jīng)過對兩圖的綜合統(tǒng)計可知,一個用戶的原創(chuàng)推文總字?jǐn)?shù)一般在500—2000左右. 且這些推文包羅萬象,沒有明確主題,所以很難通過對這些文字的總體建模,實現(xiàn)良好的用戶重識別效果. 因此本文選擇對單條推文進行研究,以克服這一困難.

圖6 每條推文字?jǐn)?shù)統(tǒng)計圖

圖7 每個用戶推文數(shù)統(tǒng)計圖

圖8 用戶屬性填寫率

由于涉及隱私,導(dǎo)致每個用戶對待屬性的態(tài)度不同,因此填寫情況也不同. 圖8是用戶屬性填寫率的統(tǒng)計圖. 由于網(wǎng)站原因,爬蟲只獲取到Q網(wǎng)站的部分用戶昵稱,所以導(dǎo)致其填寫率很低,而實際每個用戶均有昵稱,其填寫率本該為1. 對于Q網(wǎng)站的用戶生日,網(wǎng)站默認(rèn)將未填寫的用戶生日置為1970-01-01,所以其填寫率在統(tǒng)計時為1. 由于基于屬性的用戶重識別方法核心是計算每對屬性的相似度,其可計算性由該對屬性中填寫率最低的那一項決定,而由圖可知,各項屬性的最低填寫率都很低,且這6項屬性都難以標(biāo)識用戶身份的唯一性. 因此只通過屬性進行用戶重識別的研究很難取得良好效果.

3.2 實驗結(jié)果

根據(jù)熱點事件的原理可知,熱點事件系數(shù)是獨立的,當(dāng)數(shù)據(jù)集越大,得到的值越準(zhǔn)確. 因此,本文使用全部數(shù)據(jù)集進行實驗. 經(jīng)實驗發(fā)現(xiàn),當(dāng)熱點事件系數(shù)取值為 4 時,準(zhǔn)確識別數(shù)取得最大值,因此,本文將熱點事件系數(shù)取值為4.

為確定相似系數(shù)的取值,本文分別選取包含100、500對真實匹配用戶的數(shù)據(jù)集,使相似系數(shù)S從1以0.01的幅度依次遞減至0.90進行實驗,觀察經(jīng)多種處理后的準(zhǔn)確識別數(shù)的變化趨勢,實驗結(jié)果如圖9、10所示. 在圖中,高相似表示只經(jīng)過高相似同天同行為方法計算后的結(jié)果; 熱點表示經(jīng)過高相似、熱點事件處理后的結(jié)果; 多推文表示經(jīng)過高相似、熱點、高相似多推文計算后的結(jié)果; 屬性表示經(jīng)過高相似、熱點、多推文、基于屬性的相似度計算后的結(jié)果.

圖9 多種處理后準(zhǔn)確識別數(shù)變化圖(100對用戶)

圖10 多種處理后準(zhǔn)確識別數(shù)變化圖(500對用戶)

由圖9、10可知,當(dāng)數(shù)據(jù)集分別包含100、500對真實匹配用戶,相似系數(shù)取值 0.93、{0.94,0.93}時,準(zhǔn)確識別數(shù)都達到了最大值,說明相似系數(shù)的取值不會隨著數(shù)據(jù)規(guī)模的擴大而發(fā)生顯著變化,均能在其取值為0.93時,使的準(zhǔn)確識別數(shù)達到最大值. 因此,本文的相似系數(shù)S取值為0.93.

由上圖還可得知,當(dāng)相似系數(shù)取值不低于0.96時,熱點事件處理方法、高相似多推文計算方法對準(zhǔn)確識別數(shù)的提升效果較小,但當(dāng)相似系數(shù)小于0.96時,它們對準(zhǔn)確識別數(shù)的提升效果明顯,尤其是多推文處理. 說明它們對重識別的效果有著良好的影響. 屬性計算方法在相似系數(shù)變化的整個過程中,一直對重識別的結(jié)果有著積極作用.

在確定了各項系數(shù)的取值后,本文與Goga[3]的方法進行了對比. Goga根據(jù)推文的地理位置、發(fā)表時間、內(nèi)容風(fēng)格分別進行了用戶重識別研究,由于本文數(shù)據(jù)不包含推文的地理位置,因此本文與Goga均只綜合其余兩項特征完成實驗. 實驗結(jié)果如圖11至圖14所示.圖中本文方法簡記為“HS”,Goga 方法簡記為“Goga”.

圖11、12是設(shè)定了相似系數(shù)S=0.93,準(zhǔn)確率和召回率隨高相似次數(shù)HST的變化圖.

圖11 準(zhǔn)確率隨高相似次數(shù)HST的變化圖(S=0.93)

圖12 召回率隨高相似次數(shù)HST的變化圖(S=0.93)

由圖11、12可知,當(dāng)相似系數(shù)取值 0.93時,本文方法的準(zhǔn)確率迅速上升,當(dāng)高相似次數(shù)HST=3時,準(zhǔn)確率達90%,當(dāng)高相似次數(shù)HST≥6時,準(zhǔn)確率達到了100%,明顯優(yōu)于Goga. 但隨著高相似次數(shù)HST的不斷增加,本文方法的召回率也明顯下降,當(dāng)高相似次數(shù)HST=1 時,召回率最高,達到了 70.12%,此后下降趨勢逐漸緩和. 當(dāng)高相似次數(shù)HST≥4后,召回率低于Goga.

圖13、14是設(shè)定了高相似次數(shù)HST≥3,準(zhǔn)確率與召回率隨相似系數(shù)S的變化圖.

由圖13、14 可知,當(dāng)高相似次數(shù) HST≥3,本文方法的準(zhǔn)確率保持較高,均達到了90%以上,當(dāng)相似系數(shù)S≥0.98時,準(zhǔn)確率達到了100%,此后隨著相似系數(shù)的減小,準(zhǔn)確率也緩慢下降,整個變化過程明顯優(yōu)于Goga. 本文方法的召回率隨著相似系數(shù)的增大一直趨于上升趨勢,當(dāng)相似系數(shù) S≥0.94 時,Goga 的召回率優(yōu)于本文方法,隨著相似系數(shù)的減小,當(dāng) S≤0.93 后,本文方法的召回率優(yōu)于Goga.

圖13 準(zhǔn)確率隨相似系數(shù) S 的變化圖(HST≥3)

圖14 召回率隨相似系數(shù) S 的變化圖(HST≥3)

4 結(jié)語

針對社交網(wǎng)絡(luò)領(lǐng)域的個人隱私保護問題,本文提出了一個基于推文與屬性的高相似同天同行為用戶重識別算法,其提出的多種方法可有效提高算法的準(zhǔn)確率. 經(jīng)過Q與R網(wǎng)站的1萬多用戶、300多萬推文進行實驗評估,該算法的準(zhǔn)確率為33.84%,召回率為70.12%,明顯優(yōu)于Goga的方法. 且該算法可實現(xiàn)用戶的精確重識別. 實驗還揭示了當(dāng)用戶在不同網(wǎng)站發(fā)表相近或相同的內(nèi)容達到3次及以上時,可以為攻擊者提供足夠的信息,將其不同網(wǎng)站的賬戶相關(guān)聯(lián),從而導(dǎo)致更多的隱私被泄露. 本文的研究方法有多個應(yīng)用領(lǐng)域: (1) 隱私安全研究; (2) 廣告精準(zhǔn)投放; (3) 社交網(wǎng)站好友推薦等.

1Vosecky J,Hong D,Shen VY. User identification across multiple social networks. Proc. of the 1st International Conference on Networked Digital Technologies. Ostrava,Czech Republic. 2009. 360–365.

2Goga O,Perito D,Lei H,et al. Large-scale correlation of accounts across social networks [Technical Report]. TR-13-002. Berkeley,California,USA: International Computer Science Institute,2013.

3Goga O,Lei H,Krishnan SH,et al. Exploiting innocuous activity for correlating users across sites. Proc. of the 22nd International Conference on World Wide Web. Rio de Janeiro,Brazil. 2013. 447–458.

4Cecaj A,Mamei M,Bicocchi N. Re-identification of anonymized CDR datasets using social network data. Proc. of the 2014 IEEE International Conference on Pervasive Computing and Communications Workshops (PERCOM Workshops). Budapest,Hungary. 2014. 237–242.

5Narayanan A,Shmatikov V. De-anonymizing social networks. Proc. of the 30th IEEE Symposium on Security and Privacy. Washington,DC,USA. 2009. 173–187.

6Zhou XP,Liang X,Zhang HY,et al. Cross-platform identification of anonymous identical users in multiple social media networks. IEEE Trans. on Knowledge and Data Engineering,2016,28(2): 411–424. [doi: 10.1109/TKDE.2015.2485222]

7Bartunov S,Korshunov A,Park ST,et al. Joint link-attribute user identity resolution in online social networks. Proc. of the 6th International Conference on Knowledge Discovery and Data Mining,Workshop on Social Network Mining and Analysis. Beijing,China. 2012.

8Kong XN,Zhang JW,Yu PS. Inferring anchor links across multiple heterogeneous social networks. Proc. of the 22nd ACM International Conference on Information & Knowledge Management. San Francisco,California,USA. 2013.179–188.

9Fu H,Zhang A,Xie X. Effective social graph deanonymization based on graph structure and descriptive information.ACM Trans. on Intelligent Systems and Technology (TIST)-Regular Papers and Special Section on Intelligent Healthcare Informatics,2015,6(4): 49.

10Mihalcea R,Corley C,Strapparava C. Corpus-based and knowledge-based measures of text semantic similarity. Proc.of the 21st National Conference on Artificial Intelligence.Boston,Massachusetts,USA. 2006,1. 775–780.

11Islam A,Inkpen D. Semantic text similarity using corpusbased word similarity and string similarity. ACM Trans. on Knowledge Discovery from Data,2008,2(2): 10.

12Levenshtein VI. Methods for obtaining bounds in metric problems of coding theory. Proc. of the IEEE-USSR Joint Workshop on Information Theory (Moscow,1975). New York,USA. 1976. 126–143.

Method for Users Re-Identification across Social Networks Based on Tweets and Attributes

GAO Wei1,2,ZHANG Min2

1(University of Chinese Academy of Sciences,Beijing 100049,China)
2(Institute of Software,Chinese Academy of Sciences,Beijing 100190,China)

Big data Privacy security is becoming the hot spot in the various social industries,because attackers can build an integrate portrait to threaten privacy of users by identifying accounts in different sites. Simulation assessment of the attacker re-identification ability is the precondition of users’ privacy protection. Therefore,this paper proposes a high similarity algorithm in same day with same behaviors. The core idea of the algorithm is as follows: if a couple account issues similar or identical content on the same day,which also appears many times in different websites,then these two accounts may belong to a person with a high possibility. In addition,this paper builds a new weighting model for the users’ attributes to improve the accuracy of user re-identification. After the experiment on more than ten thousand users of the two major domestic social networking site,this algorithm proves to be effective. Experimental results show that even if attacker don’t consider users’ social relations,the users’ tweets,attributes,still provide enough information to make the attacker correlate their different accounts,which will lead to leak of more privacy.

social network; users re-identification; tweets; attributes; similarity

高偉,張敏.基于推文與屬性的社交網(wǎng)絡(luò)用戶重識別方法.計算機系統(tǒng)應(yīng)用,2017,26(12):94–103. http://www.c-s-a.org.cn/1003-3254/6101.html

國家自然科學(xué)基金重點項目(61232005); 國家自然科學(xué)基金(61402456)

2017-03-16; 采用時間: 2017-04-07