基于信息熵的跨社交網絡用戶身份識別方法

吳 錚，于洪濤，劉樹新，朱宇航

(國家數(shù)字交換系統(tǒng)工程技術研究中心，鄭州 450002)

(*通信作者電子郵箱wzxuexizhuanyong@163.com)

基于信息熵的跨社交網絡用戶身份識別方法

吳 錚*，于洪濤，劉樹新，朱宇航

(國家數(shù)字交換系統(tǒng)工程技術研究中心，鄭州 450002)

(*通信作者電子郵箱wzxuexizhuanyong@163.com)

針對主觀分配屬性項權重的方法忽視了各屬性項在身份匹配的應用領域中具有的特殊含義與作用，導致識別準確率低的問題，提出了一種基于信息熵的跨網絡用戶身份識別算法(IE-MSNUIA)。首先，該算法分析不同屬性項的數(shù)據類型及物理含義，相應地采用不同的相似度計算方法；然后根據各屬性的信息熵值賦予權值，進而充分挖掘各屬性的潛在信息；最后融合各個屬性進行決策判定賬號是否匹配。理論分析和實驗結果表明，與機器學習算法和主觀賦權算法相比，所提算法的各個性能參數(shù)值均有所提升，在不同數(shù)據集上的平均準確率可以達到97.2%,平均召回率達到94.1%，平均綜合性能值達到95.6%，可以準確地識別出用戶在不同社交網絡中的多個賬號身份。

用戶身份識別；屬性相似度；信息熵；信息融合；在線社交網絡

0 引言

隨著互聯(lián)網時代的到來，以及社交網絡的迅速普及與廣泛應用，人們的生活方式發(fā)生了深刻的改變。越來越多的人習慣每天通過微信、QQ等社交工具與家人、好友、同事進行即時通信，在微博、朋友圈發(fā)布信息，在頭條、騰訊上閱讀新聞并進行評論。一個人往往在多個社交網絡中注冊賬號，進行不同的社交活動，留下了豐富的用戶社交元數(shù)據信息。然而，目前由于“單點登錄”技術還不夠完善，同一個用戶在不同社交網絡中注冊的多個賬號之間往往是孤立開來的。如果可以跨網絡識別用戶，即識別出同一個用戶在不同網絡中的多個賬號，就可以實現(xiàn)數(shù)據的融合，最大限度地收集、整合與完善用戶的個人信息，從而能夠對用戶海量社交元數(shù)據進行充分挖掘。

跨網絡用戶識別技術在商業(yè)應用、信息檢索、網絡空間安全等許多領域都具有重大的研究意義與實用價值[1]。按照用戶在社交網絡中擁有的三種維度的信息，目前跨網路用戶識別技術大多可以分為三類：基于網絡結構信息[2-4]、基于屬性信息[5-10]以及基于行為信息[11-14]的用戶身份識別方法。當用戶的屬性信息可以被利用時，該方法的準確率高于其他兩類。目前基于屬性信息的用戶身份識別方法主要是判斷不同網絡中兩個賬號的檔案信息是否匹配，用戶檔案信息通常包括用戶名、地址、興趣等多個屬性，把賬號檔案所有屬性項映射到一種多維特征的分向量，向量中的每一維度的值是不同網絡中的兩個賬號在各個屬性信息上的相似度，通過給不同屬性設定權重融合多個屬性的相似度，最終計算得出檔案相似度，再與預定閾值相比較，判定是否屬于同一用戶。相關的研究成果有很多，如Vosecky等[5]首次提出將用戶的檔案信息表示為由多個屬性字段組成的n維向量，各個用戶的相似度用向量相似性計算方法來計算，它的缺點是屬性與領域是緊耦合的，每次個性化應用的改變都需要權重的重新計算。Raad等[6]將用戶的配置信息轉移到FOAF(Friend-Of-A-Friend)詞匯表，利用判定算法計算兩個賬號的相似度，該方法的問題在于識別時使用電子郵件地址作為用戶唯一標識符，而該私人信息能被其他人獲取，所以算法的應用受限。Motoyama等[7]收集了Facebook和Myspace中用戶賬號的學歷程度、職業(yè)等檔案信息，把它們作為單詞集合，通過比較單詞的相似度來衡量賬號的相似度。Zamani等[8]綜合考慮不同社交網絡中用戶賬號的單位、地址、專業(yè)興趣以及過往經歷等信息，并使用了從簡單的均等評價模型到復雜的訓練混合模型等一系列方法來融合多個檔案信息屬性的相似度，通過實驗驗證了準確識別用戶身份的可能性。Ye等[9]提出一種社交網絡中主觀導向的客觀賦權方法用于合成屬性信息，計算用戶檔案相似度。Esfandyari等[10]則提出了一種新的訓練集中反面案例選擇方法，相比傳統(tǒng)的隨機選擇法，提出基于重疊屬性項的選擇方法使得訓練出來的模型魯棒性更強。

目前基于賬號屬性信息的跨網絡用戶身份識別方法主要將不同屬性的值都看作字符串，通過計算字符串相似度刻畫屬性相似度。該類處理方法具有計算簡單、適用于大規(guī)模數(shù)據集的特點。此外該方法在融合多個屬性信息時，多采用主觀導向的客觀修正法，即專家根據各屬性的重要程度主觀確定權重系數(shù)，然后根據結果反饋進行權重修正，提高識別準確率。上述方法雖然取得了一定的效果，但是仍然存在以下問題：1)將屬性信息統(tǒng)一按照字符串進行處理，忽略了某些屬性的特殊性，在相似度刻畫中存在缺陷，造成匹配結果精度受限；2)主觀賦權導向的客觀修正法是基于特定網絡訓練出來的，推廣到其他網絡中時模型的合理性受到質疑，面對新的網絡時需要訓練新的模型，會增加復雜度。

針對上述問題，本文基于用戶檔案中多個屬性信息的身份識別問題進行建模與分析，對不同類型的屬性制定了適用于賬號匹配領域的科學合理的相似度計算方法，并綜合考慮了各屬性項所含信息量與對賬號匹配的貢獻程度，提出了一種可以適應不同網絡環(huán)境、魯棒性強的基于信息熵的權重賦予方法，通過判定算法計算兩個檔案的相似度，識別出同一用戶在多個網絡中的賬號身份，從而進一步融合多個社交網絡中的用戶身份信息，為社交網絡的數(shù)據挖掘與分析打下堅實基礎。本文通過在爬取到的社交網絡用戶信息真實數(shù)據上進行實驗，驗證了所提算法的有效性。

1 相關工作

1.1 用戶屬性建模

本文利用賬號檔案中的多個屬性信息構成一個多維特征向量，用來表征用戶在特定網絡中的身份。

可以被識別的用戶是指在目標網絡中可以找到一個賬號Fd與源網絡中的賬號Fs相匹配。選取不同網絡中賬號的用戶身份向量，通過計算兩個向量中各個屬性項的相似度，構建賬號相似度向量。

SimFunc()函數(shù)用來計算各個屬性項的相似度，如果兩個屬性項完全一致，則SimFunc()函數(shù)返回值為1；如果兩個屬性信息完全不同，則SimFunc()函數(shù)返回值為0。不同的屬性信息，用來計算相似度的SimFunc()函數(shù)形式也會不同。

1.2 字符串相似度計算方法

大多數(shù)的屬性項都存儲為字符串類型，因此利用計算字符串序列之間相似程度就可以獲取該屬性項的相似度。字符串相似度的計算已經建立了成熟的理論和模型，并且已經被廣泛應用，其中來自統(tǒng)計學、數(shù)據庫、人工智能領域的學者都從自身的研究領域出發(fā)，提出了不同的相似度計算方法。常見的字符串距離公式有：

1)Levenshtein距離。Levenshtein距離dlev又叫作編輯距離，它是通過計算使兩個字符串相等所需的單個字符編輯(增加、刪除、替換)步數(shù)，以此作為操作代價衡量兩個字符串的差異性。字符串li和lj的Levenshtein相似度計算方法如式(1)：

(1)

其中|li|和|lj|表示字符串中字符的個數(shù)。

2)Jaro距離。Jaro距離是基于公共字符的個數(shù)與順序的方法，最初是用在人口普查中判定健康記錄中兩個名字是否相同，因此非常適用于用戶名的匹配。字符串li和lj的Jaro距離計算方法如式(2)：

(2)

其中：|li|和|lj|是每個字符串的長度，m是公共字符的個數(shù)，t是換位的個數(shù)。字符串li和lj的Jaro相似度計算方法如式(3)：

(3)

3)Dice系數(shù)。對于多值屬性字符串，Dice系數(shù)的計算方式是兩個字符串ni和nj的交集信息的2倍除以ni和nj的元素總和，如式(4)：

(4)

例如對于兩個多值屬性字符串“sports music movie”和“music reading traveling”，交集信息為{“music”},所以相似度為2/6≈0.33。

對于單值屬性字符串，Dice系數(shù)的計算方式是兩個字符串li和lj的交集信息的2倍除以li和lj的長度總和，如式(5)：

(5)

其中當定義好字符組包含的字符個數(shù)為N時，交集信息|li∩lj|是指兩個字符串相同的字符組個數(shù)。例如當定義N=2時，對于兩個字符串“Jon”和“Jone”，“Jon”的字符組是{“Jo”，“on”},“Jone”的字符組是{“Jo”，“on”,“ne”},交集信息為{“Jo”，“on”}，所以相似度為2×2/5=0.8。

4)MN(Matching Name)距離。MN用戶名匹配算法[5]包括兩個步驟：先是預處理，將用戶名中含有的特殊字符或表情刪除；然后將精確匹配與部分匹配結合，得到最終的匹配結果值。

1.3 圖像數(shù)據相似度計算方法

圖像類數(shù)據相似性的計算方法較為復雜，主要是因為不同網絡中頭像圖片的格式、類型可能不同，而且拍攝時角度的不同也會帶來圖像的差異。

針對各種圖像變形的問題，采用兩種技術聯(lián)合計算圖像相似度，因為感知哈希算法(Perceptual Hash Algorithm，PHA)[15]不擅長處理圖像角度變換的情況，而尺度不變特征變換(Scale-Invariant Feature Transform, SIFT)算法[16]不擅長處理計算機生成的圖片，兩者結合互補可以使相似度算法具有更好的魯棒性。

1.4 地理位置之間距離計算方法

li和lj分別表示賬號i和賬號j的地理位置，地點li的經緯度坐標為(lati,loni)，地點lj的經緯度坐標為(latj,lonj)，兩個全球定位系統(tǒng)(Global Positioning System, GPS)坐標之間的距離采用大圓距離的計算方法計算[17]，大圓距離指的是從地球的一點出發(fā)到達球面上另外一點所經過的最短路徑長度，計算方法如式(6)所示，

(6)

其中：R為地球半徑(6 371 km),d(li,lj)的單位為km。

2 基于信息熵的用戶身份識別算法

2.1 身份識別問題建模

用戶是現(xiàn)實生活中的真實個體，賬號表示該人在虛擬網絡中的身份。每個用戶在社交網絡中存在兩種身份標識：一種是特定社交網絡中唯一辨識用戶身份的ID號；另一種是可以跨網絡識別用戶的身份標識。前者由社交網站進行管理，而后者實際上并不存在，通過某種技術手段將同一人在不同社交網絡中的多個ID號連接起來，可以識別出用戶的多個賬號身份，從而全面融合用戶信息，實現(xiàn)相關的數(shù)據挖掘與應用。

2.2 屬性相似度計算

目前屬性信息相似度的測量方法很多，只有針對不同的類型和領域信息選擇不同的比較方法，才最能真實地反映相似程度，取得最佳的匹配準確率與效率。本文選擇用戶的用戶名、自我描述、興趣愛好、網頁鏈接、地理位置、頭像共6類屬性信息作為賬號相似度的衡量基準。按照屬性項的數(shù)值所屬的不同數(shù)據類別，可以分為三類：字符串類型、圖像類型以及數(shù)字類型。其中屬于字符串類型的有用戶名、自我描述、興趣愛好和網頁鏈接，屬于圖像類型的是用戶頭像，屬于數(shù)字類型的是地理位置，各自的相似度計算方法如下。

1)用戶名。用戶名是最容易獲得的屬性信息，通常也包含在用戶檔案主頁統(tǒng)一資源定位符(Uniform Resoure Locator, URL)中。相關研究表明，用戶在不同網絡中注冊賬號時，傾向于在一個用戶名的基礎上做一些微小的變化，例如在原有用戶名中插入特殊符號、簡寫部分字符串、改寫部分字符、交換部分字符串、添加具有特殊含義的字符串等,從而衍生出多個相似的用戶名。如原有用戶名為“Alfred Gin”,則用戶可能會在其他網站中注冊賬號為“**Alfred Gin**”“A Gin”“Alfr@d Gin”“Twitter Alfred”“Alfred Gin Twitter”等。根據文獻[5]的研究表明，與其他算法相比，MN算法計算的用戶名相似度更加客觀真實、合乎邏輯，所以本文采用MN算法計算用戶名相似度。

2)自我描述。自我描述是一段類似于自我介紹的話，告訴他人自己的興趣、特長、觀點、理念等，向他人“推銷”自己，從而吸引志同道合的人添加好友關系。自我描述通常是一段字符串，利用詞頻-逆文檔頻率(Term Frequency-Inverse Document Frequency, TF-IDF)構建關鍵詞向量，通過計算向量的余弦相似度作為不同網絡中自我描述的相似度。

3)興趣愛好。用戶在社交網站中會關注自己所感興趣的話題，加入特定主題的群組，以及經常閱讀、分享自己喜歡的文章等，從這些行為中都可以抽取出用戶的興趣愛好。以所有描述用戶興趣主題的詞構建“興趣標簽詞袋”，每個賬號依據各自的興趣從“興趣標簽詞袋”中抽取出部分詞標簽集，利用Dice算法計算多詞屬性相似度，作為不同網絡中興趣愛好相似度。

4)網頁鏈接。網頁鏈接是該用戶其他網絡中賬號主頁的URL，它可以唯一標識用戶的身份，本文選取的策略為當兩個賬號的網頁鏈接相同則網頁鏈接相似度為1，否則為0。

5)地理位置。地址信息是社交網站中常見的屬性信息，由于不同網絡中地址信息書寫格式不同，若采用字符串匹配則會帶來誤判，而且依據字符串比較不同地理名稱的相似性沒有實際意義，所以通過百度地圖應用程序編程接口(Application Programming Interface, API)將地理名稱轉化為相應的經緯度坐標，利用式(6)計算兩地之間的距離，從而判斷地理位置是否相同。

6)頭像。本文選取的屬性中，用戶頭像屬于圖像類數(shù)據。主要采用兩種方法計算頭像圖片的相似度：一是PHA技術，該技術通過比較圖片的“指紋”來判斷兩幅圖片是否相似；另一個是SIFT技術，該技術通過匹配檢測出的局部特征來比較兩幅圖片的相似度。

上述的屬性信息中，利用網頁鏈接、地理位置和頭像進行身份識別時，由于其現(xiàn)實意義的特殊性，衡量這些屬性的相似度應當具有“斷層”性質，即大于“斷層式”閾值則認定為相同，相似度為1，否則不相同，相似度為0，其余的相似度值對于身份匹配應用而言沒有意義。所以本文對于這些屬性的利用，在傳統(tǒng)的相似度計算基礎上，設置了二值判定，從而使得匹配結果更加科學合理。

2.3 信息熵確定屬性權重

在確定檔案信息中各項屬性對于相似度決策判定的權重系數(shù)時，傳統(tǒng)的專家主觀賦權法是與屬性領域緊耦合的，算法魯棒性較差，而客觀賦權法依賴于足夠的樣本數(shù)據，通用性和參與性差。

為解決以上問題，本文提出了基于信息熵的賦權方法。熵權法的基本思想是認為指標的差異程度越大越重要,則權重相應也越大。計算時,如何實現(xiàn)各指標間熵值與熵權的轉換是關鍵環(huán)節(jié),其直接影響著各指標客觀權重的正確性,進而關系著方案評價的合理性、可靠性。在信息論中,熵值反映了信息無序化程度：其值越小,系統(tǒng)越有序,攜帶的信息越多；其值越大，系統(tǒng)越混亂，攜帶的信息越少。故可用信息熵評價所獲系統(tǒng)信息的有序度及其效用,即由評價指標值構成的判斷矩陣來確定指標權重,消除各指標權重計算的人為干擾,使評價結果更符合實際。

依據信息熵的定義，當系統(tǒng)可能處于多種不同的狀態(tài)，每種狀態(tài)j出現(xiàn)的概率為pij(j=1,2,…,n)時，系統(tǒng)的熵為：

(7)

其中Ei表示第i個事件。

本文根據用戶各屬性的相似度確定其權重，匹配賬號的相似度與不匹配賬號的相似度差別越大，信息越有序，熵值越小，該屬性攜帶的信息越多，該屬性越有價值，對用戶識別的判斷就越準確，所以熵權應該越大；匹配賬號的相似度與不匹配賬號的相似度差別越小，信息越無序，熵值越大，該屬性攜帶的信息越少，該屬性價值越低，對用戶識別的判斷就越模糊，所以熵權應該越小?；谝陨戏治?，對式(7)中的pij定義為屬性相似度出現(xiàn)的概率，如式(8)：

(8)

(9)

(10)

(11)

2.4 用戶賬號匹配

根據相似度向量的定義，則衡量兩個賬號相似度的計算方法如式(12)所示：

(12)

算法1 檔案相似度計算方法。

輸出Fs和Fd兩個賬號的相似度Similarity(Fs,Fd)。

2) fori=1 ton

4) end

構建賬號相似度向量

6) end

7) fori=1 ton

8) 利用式(8)計算屬性i相似度出現(xiàn)的概率pij

12) end

13) 利用式(12)計算Fs和Fd兩個賬號的相似度Similarity(Fs,Fd)

14) returnSimilarity(Fs,Fd)

通過比較不同賬號對之間的相似度值的大小，確定最佳匹配賬號對。

2.5 身份識別過程

基于屬性信息的跨網絡用戶身份識別過程包括三個步驟：賬號選擇、賬號匹配、剪枝過濾。

1)賬號選擇。

在對一個網絡中的源賬號Fs進行用戶識別時，如果每次都是從另一個網絡中選取所有的目標賬號Fd進行關于檔案信息中所有屬性的相似度計算，則計算量會非常大，尤其是當網絡中注冊賬號的規(guī)模十分龐大時，逐一比較更是不現(xiàn)實、不可行的。因此在選取目標賬號Fd與源賬號Fs進行相似度計算時，有必要根據條件C對另一網絡中的目標賬號進行篩選，采用單個較為簡單的屬性作為篩選器，從全集中過濾出與源賬號Fs有較高匹配概率的候選賬號集合，從而降低計算量。

通過對人們生活習慣的觀察與分析，用戶在不同網絡中傾向于使用相似的用戶名，又因為用戶名的相似度計算在所有屬性中是最簡單的，所以本文使用用戶名作為篩選器，選擇一個合適的閾值來平衡候選集規(guī)模與覆蓋率之間的關系，求得一個折中值。

2)賬號匹配。

通過賬號選擇步驟，選出了滿足條件C的與源賬號Fs有可能匹配的候選賬號集合，然后依次對集合中的候選賬號與源賬號Fs進行基于屬性信息的相似度計算，選出其中與源賬號Fs相似度最高的候選賬號Fd作為待匹配賬號，然后與預先設定閾值(通常情況下選取閾值為0.5)，如果大于閾值則判定為匹配，反之不匹配。

3)剪枝過濾。

得到最終匹配結果后，為了確保精確度，有時需要剪枝過濾的過程去除一些錯誤的匹配。本文對兩個網絡G1和G2中的賬號進行識別時，以網絡G1中的賬號Fs作為源賬號在網絡G2中尋找匹配的目標賬號Fd后，再以網絡G2中的Fd作為源賬號在網絡G1中尋找匹配的目標賬號，如果匹配的是Fs，則保留該對匹配賬號，否則舍棄該對賬號。

算法2 基于信息熵的跨網絡用戶身份識別算法(Information Entropy based Multiple Social Networks User Identification Algorithm, IE-MSNUIA)。

輸出 與Fs匹配的賬號Fd。

4)c++

6) end

7)max=0

9) 利用算法1計算檔案相似度Similarity(Fs,CFj)

10) ifSimilarity(Fs,CFj)>max

11)max=Similarity(Fs,CFj)，d=j

12) end

13) ifmax≥Tp

14) returnFd

15) else return null

3 實驗結果及分析

3.1 數(shù)據集的獲取與設置

在一些社交網絡中，用戶在填寫自己的檔案信息時，往往喜歡添加進自己在其他網絡中的個人主頁鏈接，意在邀請他人與自己在其他網絡中也建立起好友關系，這一行為給驗證個人多個賬號身份提供了可行性。Google+就是此類型的社交網站，該網站上的用戶檔案中有一項屬性是“鏈接”，用戶可以在此張貼自己在其他社交網站上的個人主頁鏈接。為了驗證所提算法的有效性，本文選取從Google+、Facebook和Twitter這三個社交網絡中收集的賬號屬性信息進行用戶身份識別的相關實驗。文獻[18]提供了一份包含5個社交網絡賬號主頁鏈接的公開數(shù)據集，本文以Google+作為收集用戶屬性信息的源網站，過濾選取其中給出Facebook和Twitter主頁鏈接非空、網頁未失效且公開檔案信息訪問權限的Google+賬號，最終得到Google+賬號5 916個，F(xiàn)acebook賬號4 377個，Twitter賬號5 829個。用戶屬性信息獲取流程如下：首先從中抽取出用戶主頁鏈接地址URL，然后借助第三方網站查詢出對應的用戶賬號ID，再通過官方提供的API接口爬取檔案信息數(shù)據，最后將數(shù)據存入數(shù)據庫以供實驗使用。

不同的社交網絡中用戶檔案信息的屬性項個數(shù)與內容并非完全相同，而且同一個用戶在不同網絡中填寫的情況也有差異。網絡中經常出現(xiàn)用戶屬性項缺失的情況，屬性項缺失通常是用戶漏填或者設定隱私保護造成的，所以爬取到的檔案數(shù)據并不能直接使用，需要對待匹配的兩個網絡中的公共屬性項進行篩選與語意匹配。通過綜合分析，本文最終確定在匹配Google+、Facebook和Twitter網絡中賬號時，選取三個網絡中都具備的、通過API可以獲取到且用戶填寫較為齊全的6種屬性項：用戶名(username)、自我描述(biography)、興趣愛好(interests)、網頁鏈接(URL)、地理位置(location)、頭像(avatar)。對于這6項屬性信息中依然存在的缺失數(shù)據以及明顯不符屬性內容的噪聲數(shù)據，采用該項屬性所有用戶的平均值進行補充或者替換。

3.2 評價指標

使用 IE-MSNUIA可以判斷兩個賬號是否匹配，如果賬號的檔案信息相似度大于一定的閾值，則判定為匹配，即兩個賬號對應于現(xiàn)實生活中的同一個用戶，反之則判定為不匹配。本文采用準確率(precision)、召回率(recall)以及綜合評價指標F1作為衡量算法性能的評價標準。具體定義如下，

precision=tp/(tp+fp)

(13)

recall=tp/(tp+fn)

(14)

F1=2×precision×recall/(precision+recall)

(15)

準確率(precision)是指正確匹配的比率，其中tp表示被算法匹配上并且對應于同一用戶的賬號對數(shù),fp表示被算法匹配上但是對應于不同用戶的賬號對數(shù)；召回率(recall)是指正確識別的比率，其中fn表示未被算法匹配上的對應于同一用戶的賬號對數(shù)；F1是前兩者的調和平均數(shù)，是算法性能的綜合評價指標。

3.3 實驗結果

3.3.1 單屬性匹配性能分析

在實驗中，首先測試了各個單項屬性在賬號匹配中的性能，實驗結果如圖1所示。其中本文設置二值屬性網頁鏈接和頭像各自的“斷層式”閾值為1和0.9；對于地理位置屬性，本文將范圍控制在市級單位，即兩地相距在80 km以內則認為地理位置相似度為1，否則為0。利用屬性項用戶名、網頁鏈接和頭像在匹配時，同一用戶與不同用戶的相似度分布集中且差別較大，該項屬性在匹配時具有較強的區(qū)分性，所以權重應當較大。屬性項自我描述和興趣愛好在匹配時，同一用戶與不同用戶的相似度分布離散且差別較?。粚傩皂椀乩砦恢迷谄ヅ鋾r，同一用戶與不同用戶的相似度有交錯現(xiàn)象，這些屬性項匹配時的分辨力較弱，所以權重應當較小。

圖1 賬號各屬性的相似度分布Fig. 1 Similarity distributions of account attributes

用信息熵確定權重時，對于確定了目標網絡以后，每個源網絡中待匹配賬號Fs都有屬于自己的一個權重分配方案。實驗選擇在Google+和Facebook、Google+和Twitter以及Facebook和Twitter這3組網絡中進行賬號匹配，圖2是在這3組網絡中賬號權重分配的分布圖，從分布來看，用戶名和網頁鏈接的權重都較大，而另外四項屬性的權重都較小，這與上面的分析結果是一致的，驗證了信息熵權的客觀性與合理性。

圖2 賬號各屬性的權重分布Fig. 2 Weight distributions of account attributes

3.3.2 身份識別算法性能分析

本實驗選擇的對比算法包括支持向量機(Support Vector Machine, SVM)算法和隨機森林(Random Forest，RF)法兩種有監(jiān)督的機器學習算法以及Vosecky等[5]、Ye等[9]和Esfandyari等[10]提出的基于主觀賦權的算法。機器學習算法相當于把身份識別看作賬號“匹配”與“不匹配”的二分類問題，將各屬性項的相似度看作輸入的特征數(shù)據，把匹配與否作為輸出的判別類型，模型訓練時正負兩類樣本比例設為1∶1，訓練集和測試集的比例設置為3∶1。Vosecky等[5]根據不同屬性項的字符串特點，對不同的屬性項采取精確匹配、部分匹配和模糊匹配三種不同的方法計算字符串相似度，利用主觀經驗初始化各屬性項的權重，然后再用控制變量法，以準確率為目標對各權重進行修正。Ye等[9]則是將屬性分為決定性屬性和非決定性屬性兩種，賦權方法采用的是主觀導向的客觀賦權法，即首先依據專家經驗賦權，然后依據相似度對其進行反向客觀修正。Esfandyari等[10]在權重選擇上參照了Vosecky等[5]的方法，但是在訓練集的選取上有所變化，同時選擇正確匹配和錯誤匹配的數(shù)據訓練模型，從而使得算法魯棒性更好。實驗在三組數(shù)據集(Google+&Facebook、Google+&Twitter、Facebook&Twitter)上進行測試，其中機器學習算法采用10折交叉驗證的方法求得最終結果。圖3顯示了不同算法在不同數(shù)據集上的性能參數(shù)對比情況，并且為了表述方便，橫軸的算法A～F分別代表SVM算法、RF法、Vosecky等[5]的方法、Ye等[9]的方法、Esfandyari等[10]的方法和本文的IE-MSNUIA。

實驗結果顯示，本文算法優(yōu)于對比算法，在不同的數(shù)據集上均具有最好的性能。具體分析其原因在于，機器學習算法具有較好的身份識別效果，而且在可用屬性信息充足的條件下采用不同機器學習算法進行身份匹配時，匹配效果的變化并不大；然而由于機器學習算法本身存在的缺點，例如SVM算法對缺失數(shù)據敏感的問題，以及隨機森林法在處理取值劃分較多的屬性時權重不可信的問題，導致性能受限。此外，機器學習算法性能依賴于訓練集數(shù)據組成的問題也限制了其應用的廣度。

相比較而言，另外三種基于主觀賦權修正的對比算法，由于直接對屬性賦權，相比分類器算法，省去了模型訓練的過程，所以較為簡單高效；此外還加入了對權值的修正過程，性能也較分類器算法有一定程度的提升。

本文的IE-MSNUIA綜合考慮了不同屬性項信息自身的數(shù)據特點與現(xiàn)實含義，并沒有像三種基于主觀賦權修正的對比算法那樣將屬性統(tǒng)一按照字符串進行處理，而是制定了更科學合理的相似度計算方法，從而實驗結果更加精確；另一方面，基于信息熵的賦權方法綜合考慮了各屬性項所含信息量與對賬號匹配的貢獻程度，所以各個屬性項權重的可信度更高。從實驗結果可以看出，本文算法的平均準確率可以達到97.2%，平均召回率可以達到94.1%，平均F1值可以達到95.6%，驗證了其有效性。

圖3 各算法性能參數(shù)對比Fig. 3 Comparison of the performance parameters of different algorithms

4 結語

本文提出了一種基于屬性信息的跨網路身份識別算法，通過利用不同社交網絡開放的API接口可以爬取得到的公共用戶屬性信息，構建待匹配賬號相似度向量，并依據信息熵的思想對不同屬性賦予不同權重，計算賬號檔案信息的整體相似度進行賬號匹配，實現(xiàn)了在Google+、Facebook和Twitter三個網絡之間的跨網絡用戶識別?，F(xiàn)有的基于屬性信息進行身份識別的方法在計算不同類型屬性項相似度時統(tǒng)一按照字符串進行處理，而本文則通過分析屬性不同的數(shù)據類型特征采用不同的相似度衡量策略，實驗結果驗證了該算法的有效性與合理性。由于本文算法對每個待識別源賬號都需要計算一套屬性權值分配方案，當社交網絡中待匹配的賬號規(guī)模變大時，屬性項權值計算量也會變大，所以下一步的工作將著眼于如何進一步地改進權值計算方法，降低算法的計算開銷。

References)

[1] 劉東,吳泉源,韓偉紅,等.基于用戶名特征的用戶身份同一性判定方法[J].計算機學報,2015,38(10):2028-2040. (LIU D, WU Q Y, HAN W H, et al. User identification across multiple websites based on username features[J]. Chinese Journal of Computers, 2015, 38(10): 2028-2040.)

[2] NARAYANAN A, SHMATIKOV V. De-anonymizing social networks [C]// SP ’09： Proceedings of the 2009 30th IEEE Symposium on Security and Privacy. Washington, DC: IEEE Computer Society, 2009: 173-187.

[3] KONG X, ZHANG J, YU P S. Inferring anchor links across multiple heterogeneous social networks [C]// CIKM ’13: Proceedings of the 22nd ACM International Conference on Information & Knowledge Management. New York: ACM, 2013: 179-188.

[4] TAN S, GUAN Z, CAI D, et al. Mapping users across networks by manifold alignment on hypergraph [C]// AAAI 2014: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence. Menlo Park, CA: AAAI Press, 2014: 159-165.

[5] VOSECKY J, HONG D, SHEN V Y. User identification across multiple social networks [C]// NDT ’09: Proceedings of the 2009 First International Conference on Networked Digital Technologies. Piscataway, NJ: IEEE, 2009: 360-365.

[6] RAAD E, CHBEIR R, DIPANDA A. User profile matching in social networks [C]// NBIS ’10: Proceedings of the 2010 13th International Conference on Network-Based Information Systems. Washington, DC: IEEE Computer Society, 2010: 297-304.

[7] MOTOYAMA M, VARGHESE G. I seek you: searching and matching individuals in social networks [C]// WIDM ’09: Proceedings of the Eleventh International Workshop on Web Information and Data Management. New York: ACM, 2009: 67-75.

[8] ZAMANI K, PALIOURAS G, VOGIATZIS D. Similarity-based user identification across social networks [C]// Proceedings of the 2015 International Workshop on Similarity-Based Pattern Recognition, LNCS 9370. Berlin: Springer-Verlag, 2015: 171-185.

[9] YE N, ZHAO L, DONG L, et al. User identification based on multiple attribute decision making in social networks [J]. China Communications, 2013, 10(12): 37-49.

[10] ESFANDYARI A, ZIGNANI M, GAITO S, et al. User identification across online social networks in practice: pitfalls and solutions [J/OL]. Journal of Information Science (2016- 10- 01) [2016- 12- 06]. https://doi.org/10.1177/0165551516673480.

[11] ROEDLER R, KERGL D, RODOSEK G D. Profile matching across online social networks based on Geo-tags [C]// NaBIC 2015: Proceedings of the 7th World Congress on Nature and Biologically Inspired Computing, AISC 419. Berlin: Springer-Verlag, 2016: 417-428.

[12] GOGA O, LEI H, PARTHASARATHI S H K, et al. Exploiting innocuous activity for correlating users across sites [C]// WWW ’13: Proceedings of the 22nd International Conference on World Wide Web. New York: ACM, 2013: 447-458.

[13] ZAFARANI R, LIU H. Connecting corresponding identities across communities [C]// ICWSM 2009: Proceedings of the 3rd International AAAI Conference on Weblogs and Social Media. Menlo Park, CA: AAAI Press, 2009: 354-357.

[14] PERITO D, CASTELLUCCIA C, KAAFAR M A, et al. How unique and traceable are usernames? [C]// PETS 2011: Proceedings of the 2011 International Symposium on Privacy Enhancing Technologies Symposium, LNCS 6794. Berlin: Springer-Verlag, 2011: 1-17.

[15] 張慧,張海濱,李瓊,等.基于人類視覺系統(tǒng)的圖像感知哈希算法[J].電子學報,2008,36(S1):30-34. (ZHANG H, ZHANG H B, LI Q, et al. Image perceptual hashing based on human visual system [J]. Acta Electronica Sinica, 2008, 36(S1):30-34.)

[16] 陳志華,吳彩榮,趙建鋒,等.SIFT算法的介紹和應用[J]. 企業(yè)科技與發(fā)展,2011(19):50-51. (CHEN Z H, WU C R, ZHAO J F, et al. The introduction and application of SIFT[J]. Enterprise Science and Technology & Development, 2011(19): 50-51.)

[17] 袁適之,李晶,李石君,等.一種基于位置社交網絡的地點推薦算法[J].計算機應用研究,2016,33(7):2003-2006. (YUAN S Z, LI J, LI S J, et al. Location recommendation algorithm based on location-based social networks[J]. Application Research of Computers, 22016, 33(7): 2003-2006.)

[18] YAN M, SANG J, XU C. Unified youtube video recommendation via cross-network collaboration [C]// ICMR ’15： Proceedings of the 5th ACM on International Conference on Multimedia Retrieval. New York: ACM, 2015: 19-26.

This work is partially supported by the National Natural Science Foundation of China (61379151), the National Key Technology R&D Program (2014BAH30B01).

WUZheng, born in 1992, M. S. candidate. His research interests include big data analysis, complex network.

YUHongtao, born in 1970, Ph. D., research fellow. His research interests include big data analysis， communication and information system.

LIUShuxin, born in 1987, Ph. D., assistant research fellow. His research interests include complex network, link prediction.

ZHUYuhang, born in 1982, M. S., assistant research fellow. His research interests include graph mining.

Useridentificationacrossmultiplesocialnetworksbasedoninformationentropy

WU Zheng*, YU Hongtao, LIU Shuxin, ZHU Yuhang

(NationalDigitalSwitchingEngineering&TechnologicalResearchCenter,ZhengzhouHenan450002,China)

The precision of user identification is low since the subjective weighting algorithms ignore the special meanings and effects of attributes in applications. To solve this problem, an Information Entropy based Multiple Social Networks User Identification Algorithm (IE-MSNUIA) was proposed. Firstly, the data types and physical meanings of different attributes were analyzed, then different similarity calculation methods were correspondingly adopted. Secondly, the weights of attributes were determined according to their information entropies, thus the potential information of each attribute could be fully exploited. Finally, all chosen attributes were integrated to determine whether the account pair was the matched one. Theoretical analysis and experimental results show that, compared with machine learning based algorithms and subjective weighting algorithms, the performance of the proposed algorithm is improved, on different datasets, the average precision of it is up to 97.2%, the average recall of it is up to 94.1%, and the average comprehensive evaluation metric of it is up to 95.6%. The proposed algorithm can accurately identify user accounts across multiple social networks.

user identification; attribute similarity; information entropy; information integration; online social network

TP391.4; TP181

A

2017- 02- 08;

2017- 03- 15。

國家自然科學基金資助項目(61379151)；國家科技支撐計劃項目(2014BAH30B01)。

吳錚(1992—)，男，江蘇徐州人，碩士研究生，主要研究方向：大數(shù)據分析、復雜網絡； 于洪濤(1970—)，男，遼寧丹東人，研究員，博士，主要研究方向：大數(shù)據分析、通信與信息系統(tǒng)； 劉樹新(1987—)，男，山東濰坊人，助理研究員，博士，主要研究方向：復雜網絡、鏈路預測； 朱宇航(1982—)，男，江蘇徐州人，助理研究員，碩士，主要研究方向：圖挖掘。

1001- 9081(2017)08- 2374- 07

10.11772/j.issn.1001- 9081.2017.08.2374