基于推文與屬性的社交網絡用戶重識別方法①

高 偉,張 敏

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

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

基于推文與屬性的社交網絡用戶重識別方法①

高 偉1,2,張 敏2

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

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

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

社交網絡; 用戶重識別; 推文; 屬性; 相似度

1 引言

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

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

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

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

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

2 用戶重識別方法

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

2.1 符號定義

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

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

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

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

圖1 推文向量計算圖

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

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

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

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

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

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

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

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

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

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

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

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

其偽代碼算法如下:

Algorithm 1. High Similarity 1.For c= 0to n do2. TQ=TQ∪TQc#計算Q網站所有用戶的發推日期并集3.End For4.For d= 0to m do5. TR=TR∪TRd# 計算R網站所有用戶的發推日期并集6.End For7.TQR=TQ∩TR# 計算Q與R網站用戶發推日期的交集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

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

2.2.3 熱點事件處理方法

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

圖3 用戶UQ0經高相似同天同行為方法計算后的結果表

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

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

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

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

假設Q網站用戶UQi經過高相似同天同行為方法計算后,他在日期T0到Tm發表的推文產生了高相似同天同行為,且由這些推文產生的候選匹配用戶對應的高相似次數分別為:

于日期Tx(0≤x≤m)發表的推文twz產生的候選匹配用戶對應的高相似次數分別為:

當以上高相似次數滿足如下條件時,推文twz對應的高相似記錄應該被刪除. 即:

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

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

2.2.4 高相似多推文計算方法

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

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

假設Q網站用戶UQi與R網站用戶URj的推文集合分別為:

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

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

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

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

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

預處理: 將屬性處理為統一格式,如生日: yyyymm-dd、家鄉: **省**市

各屬性相似度計算:

圖5 昵稱相似度計算規則圖

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

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

各屬性權重計算:

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

① 選擇社交網站用戶數據集;

② 統計各屬性填寫率;

③ 計算各屬性權重——填寫率倒數和歸一化.

表1以R網站的數據集(共10027個用戶)為例,計算各屬性權重.

表1 R 網站的屬性權重計算表

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

① 填寫率倒數和歸一化,即:

② 求得p,然后將屬性填寫率的倒數與p進行乘積計算,結果即為該屬性的歸一權重.

用戶相似度:

根據以上內容,可求得每對屬性的相似度大小及各屬性在標識用戶身份唯一性時所占的權重. 則基于屬性的用戶相似度可表示為:

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

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

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

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

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

3 實驗結果與分析

3.1 數據集

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

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

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

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

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

表2 數據集總量統計表

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

圖6 每條推文字數統計圖

圖7 每個用戶推文數統計圖

圖8 用戶屬性填寫率

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

3.2 實驗結果

根據熱點事件的原理可知,熱點事件系數是獨立的,當數據集越大,得到的值越準確. 因此,本文使用全部數據集進行實驗. 經實驗發現,當熱點事件系數取值為 4 時,準確識別數取得最大值,因此,本文將熱點事件系數取值為4.

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

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

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

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

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

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

圖11、12是設定了相似系數S=0.93,準確率和召回率隨高相似次數HST的變化圖.

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

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

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

圖13、14是設定了高相似次數HST≥3,準確率與召回率隨相似系數S的變化圖.

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

圖13 準確率隨相似系數 S 的變化圖(HST≥3)

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

4 結語

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

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

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

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

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