基于帶權超圖的跨網絡用戶身份識別方法

徐 乾，陳鴻昶，吳 錚，黃瑞陽

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

基于帶權超圖的跨網絡用戶身份識別方法

徐 乾*，陳鴻昶，吳 錚，黃瑞陽

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

隨著各種社交網絡的不斷涌現，越來越多的研究者開始從多源的角度分析社交網絡數據，多社交網絡的數據融合依賴于跨網絡用戶身份識別。針對現有的基于好友關系(FRUI)算法對社交網絡中的異質關系利用率不高的問題，提出了基于帶權超圖的跨網絡用戶身份識別(WHUI)算法。首先，通過在好友關系網絡上構建帶權超圖來準確地描述同一網絡中的好友關系及異質關系，以此提高表示節點所處拓撲環境的準確性；然后，在構建好的帶權超圖的基礎上，根據節點所處拓撲環境在不同網絡中大致相同這一特性，定義節點之間的跨網絡相似性；最后，結合迭代匹配算法，每次選取跨網絡相似性最高的用戶對進行匹配，并加入雙向認證和結果剪枝來保證識別準確率。在合作網絡DBLP和真實社交網絡上進行了實驗，實驗結果表明，在真實社交網絡上,所提算法相比FRUI算法，平均準確率提高了5.5個百分點，平均召回率提高了3.4個百分點，平均F值提高了4.6個百分點。在只有網絡拓撲信息的情況下，所提WHUI算法有效提高了實際應用中身份識別的準確率和召回率。

跨網絡用戶身份識別；帶權超圖；異質關系；節點相似度；迭代匹配

0 引言

多種多樣的社交網絡極大地豐富了人們的生活，人們通過QQ、微信與朋友保持聯系，通過微博關注自己喜愛明星的動態，通過LinkedIn來發展職場社交。然而大多數社交網絡間沒有建立起公開的連接，因此用戶的信息分散在多個社交網絡中。識別出網民在不同網絡中的虛擬賬號的問題就是跨網絡用戶身份識別問題[1]。這一問題的解決在現實應用中具有十分重要的意義：社交網絡的管理者識別出用戶的多個虛擬賬號之后，可以獲取用戶在其他社交網絡中的信息，從而在自己的網絡中進行準確的推薦；公安機關在識別出用戶的多個虛擬賬號之后，可以全面地了解某一用戶，為偵查工作提供支持。除此之外，這項研究還在信息檢索等多個領域有著廣泛的應用前景[2]。

目前，在跨網絡用戶識別技術的研究上，現有的方法主要分為三類：基于屬性信息[2-4]、基于用戶產生內容[5-6]以及基于網絡拓撲結構[7-11]的用戶身份識別方法。基于屬性信息的方法是利用用戶名、所在地、用戶頭像等用戶在注冊社交網絡時填寫的檔案信息進行身份識別；基于用戶產生內容的方法是利用用戶在使用社交網絡過程中產生的微博、狀態及地理位置等信息進行身份識別；基于網絡拓撲結構的方法是利用用戶在社交網絡中的好友關系信息進行身份識別。由于好友關系信息較易被獲取，而且好友關系與他人完全重疊的現象非常少見，所以本文選擇基于網絡拓撲結構進行跨網絡用戶身份識別。

文獻[7]僅僅利用網絡拓撲結構進行識別，將不同網絡中的兩個節點所共有的種子節點數作為節點的跨網絡相似性，選擇相似性較大的進行匹配。文獻[8]提出利用擴展的Adamic-Adar指數、Jaccard相關系數來計算用戶節點間的跨網絡相似性。文獻[9]提出有向網絡上的身份識別，節點的跨網絡相似性使用共有的in/out鄰居個數以及出度、入度來度量。文獻[10]使用屬性信息和網絡結構信息構建目標函數，對目標函數進行優化得到最優的匹配結果，其中節點相似性使用Dice系數進行度量。縱觀現有方法,主要是在好友關系網絡中的拓撲信息的基礎上，利用共同鄰居個數、Adamic-Adar指數等傳統的節點相似性度量方法得到節點之間的跨網絡相似性。然而現實網絡中的節點之間的關系具有異質性，節點之間不僅存在好友關系或者關注與被關注關系，還存在更加復雜多樣的關系，例如多個用戶同時加入了某個興趣小組、同時加入了某次活動、共同關注某一個用戶等。現有的節點相似性計算方法忽略了節點間關系的異質性，因此造成身份識別的準確率不高。

針對上述問題，本文提出了一種基于帶權超圖模型的跨網絡用戶身份識別(Weighted Hypergraph based User Identification, WHUI)算法。該算法分為兩個階段：第一個階段是超圖構建階段，首先從普通好友關系網絡結構出發，在兩個待匹配網絡上分別構建超圖模型來反映網絡中的好友關系及異質關系，其次在超圖模型基礎上定義同一網絡中節點間的相似性，以此實現對于同一網絡用戶節點間相似性的準確刻畫，然后利用種子節點計算得到兩個網絡中未匹配節點之間的跨網絡相似性。第二階段是身份識別階段，這一階段解決的問題是如何根據節點之間的跨網絡相似性進行節點匹配，主要方法是在節點跨網絡相似性的基礎上，每次選取跨網絡相似性最大的節點對進行匹配，并加入雙向認證保證識別的準確率。最后迭代更新種子節點集，以達到跨網絡用戶身份識別的目的。實驗結果表明，該算法在準確率和綜合評價指標上都得到了改善。

1 相關定義

1.1 用戶身份識別

1.2 種子節點

1.3 基于好友關系的跨網絡用戶身份識別

(1)

2 超圖模型構建

2.1 超圖

(2)

2.2 超圖模型

2.3 在好友關系網絡上構建超圖模型

在實際應用中，如果有已知的異質關系信息，例如多個用戶加入了同一個興趣小組，或者同時參加了某個活動，那么就可以直接將這些用戶劃分到一個超邊中，然后通過設置超邊權值來體現超邊中的節點之間具有某種程度的親密關系。但是上述信息通常難以獲取，有時只能獲取用戶好友關系信息。所以本文根據普通的好友關系網絡來得到近似的用戶關系信息，從而構建超圖模型。如果同一個網絡中的兩個用戶v1和v2直接相連，就將v1和v2劃分到同一個超邊中，例如圖2所示的有向圖中，由于v1和v2以及v1和v3之間都是直接相連關系，這種關系通常是反映了現實中的好友關系，在另一個網絡可能也存在這樣的關系，因此分別構建超邊e1={v1,v2}、e2={v1,v3}分別表示v1和v2以及v1和v3之間的好友關系，為下一步計算節點相似性提供支撐。

圖1 用于跨網絡身份識別的超圖模型Fig. 1 Hypergraph model for user identification across social networks

圖2 直接相連關系對應的超邊劃分Fig. 2 Hyperedge construction of direct connected relation

除此之外，本文在擁有共同鄰居的兩個或多個節點上構建超邊，例如圖3所示，v2、v3、v4是v1的所有鄰居節點且都和v1直接相連，在這種網絡結構下，可以認為v2、v3、v4都具有“與v1是好友”這個屬性，因此在其上構建超邊e3={v2,v3,v4}，表示v2、v3、v4所在的拓撲環境有部分相似之處，從而為下一步計算節點相似性提供支撐。

圖3 擁有共同鄰居的兩個或多個節點上的超邊劃分Fig. 3 Hyperedge construction of two or more nodes with common neighbors

2.3.1 超邊權重設定

通過上述分析可知，超圖不僅保留了好友關系網絡中原始的拓撲信息，而且還可以體現網絡中的異質關系。這些關系有些是緊密的關系，有些則是相對疏遠的關系,因此需要通過設置超邊的權重來表示超邊內節點的親密度,權重越大則認為超邊中的節點關系越緊密。對于在直接相連關系上建立起的超邊，超邊內節點對應的是社交網絡中的好友關系，將這種超邊權重設置為p，p相對較大;對于在擁有共同好友的節點上構建的超邊，由于超邊內節點彼此之間不一定直接相連，因此這種超邊節點關系通常比直接相連的好友關系疏遠,將這種超邊權重統一設置為q，q相對較小。本文的實驗部分，會考察p和q的設置對于實驗結果的影響。

2.3.2 超圖模型構建算法

基于以上分析，本文給出在好友關系網絡上構建帶權超圖的算法，算法描述如算法1所示。

算法1 帶權重超圖構建算法。

輸入 好友關系網絡G(V,E)，超邊權重p、q；

輸出 帶權超圖Gh(Vh,Eh)。

HypergraphConstruction(G,p,q)

1)

初始化Vh=V，Eh={}，i=1

2)

forv∈Vhdo

3)

foru∈Neighbor(v) do

4)

ei={v,u}

5)

if 超邊集中含有僅包含v,u且超邊權重為p的超邊 do

6)

continue

7)

else

8)

Eh=Eh+ei，w(ei)=p，i=i+1

9)

end if

10)

end for

11)

ifNeighbor(v)中含有兩個或兩個以上的節點

12)

ei=Neighbor(v)

13)

Eh=Eh+ei，w(ei)=q，i=i+1

14)

end if

15)

end for

16)

return (Vh,Eh)

上述算法中，Neighbor(v)是v的所有鄰居節點組成的集合，第3)～10)行是在直接相連的兩個節點上構建超邊，第11)～14)行是在擁有共同好友的兩個或多個節點上構建超邊。

3 基于帶權超圖的用戶身份識別

3.1 節點相似性計算

由于好友關系在不同社交網絡中非常容易保持一致性[14]，所以兩個網絡中互相匹配的兩個節點，它們與種子節點的相似性也具有跨網絡的一致性。這種一致性可以用來計算未匹配節點間的跨網絡相似性，進而判斷這兩個節點是否匹配。由于超圖可以準確地描述網絡中節點之間的關系，所以本文利用超圖來計算身份未識別節點與種子節點的同網絡相似性，然后根據的跨網絡一致性，定義不同網絡中節點間的跨網絡相似性，為下一步節點匹配提供支撐。

3.1.1 同一網絡中的節點間相似性

已知用戶好友關系網絡G(V,E)，根據在其上構建的超圖Gh(Vh,Eh)，超圖Gh中的兩個節點vi∈Vh和vj∈Vh的相似性計算方法如式(3)所示：

(3)

式(3)體現的思想是，如果vi和vj同時所在的超邊個數越多，vi和vj的相似度就越高。w(ek)是超邊的權重，它體現超邊中各個節點關系的緊密性，權重越大說明超邊中的節點關系越密切，相似度越高。δ(ek)是超邊的度，δ(ek)=2時超邊中的節點在好友關系網絡中是直接相連的關系，此時超邊中的兩個節點之間的關系較為緊密，相似度較高;δ(ek)>2時，超邊中的節點在好友關系網絡中只是擁有共同關注的好友，它們可能并不直接相連，所以此時超邊中的節點之間的關系相對疏遠，相似度較低。h(v,e)是節點-超邊函數，當v∈e時，h(v,e)=1，否則h(v,e)=0。

3.1.2 跨網絡的節點間相似性

對于互相匹配的兩個節點，它們與種子節點的相似性具有跨網絡一致性,所以本文利用未識別節點與種子節點的同網絡相似性來計算兩個節點跨網絡的相似性。

(4)

(5)

3.2 跨網絡節點匹配

有了跨網絡相似性之后，接下來面對的問題就是如何進行跨網絡節點的匹配，算法在身份識別階段解決的就是這一問題。本文將跨網絡節點匹配分解成逐步迭代求取的過程(如圖4所示)，在每一步迭代的過程里，算法的計算過程分為節點選擇、節點匹配和雙向認證，在每一步迭代過程中選取當前跨網絡相似性最大的兩個節點進行匹配，加入到種子節點集S中，新加入的種子節點也作為計算跨網絡相似性所參照的種子節點，從而提高識別準確度。當沒有可以匹配的節點時，算法停止迭代。最終通過結果剪枝，刪除一部分算法后期挖掘出的種子節點以保證準確率，剪枝后的結果即為最終的結果。算法進行跨網絡匹配的流程如圖4所示。

圖4 WHUI算法在身份識別階段的流程Fig. 4 Flow chart of WHUI algorithm at identification stage

3.2.1 節點選擇

WHUI算法在用戶身份識別階段，每一次迭代運行的第一個步驟就是從兩個網絡中選擇一個最有可能在另一個網絡中存在匹配的節點。由于用戶使用社交網絡的習慣很大程度上受好友的影響，用戶的好友中種子節點越多，他在另一個網絡中存在匹配節點的概率就越大，因此本文優先選擇好友中種子節點數量多的優先進行匹配，算法描述如算法2所示。

算法2 節點選擇算法。

輸出 待匹配的用戶節點vselect。

1)

if unmapped queue非空 then

2)

return 隊列中第一個元素

3)

end if

4)

5)

計算v0的鄰居中種子節點的個數

6)

end for

7)

8)

9)

10)

11)

else

12)

13)

end if

14)

returnvselect

其中unmapped queue表示未匹配隊列，未匹配隊列中的節點，是在之前迭代過程中被選中了但并未成功匹配的節點。第4)～8)行是在計算兩個網絡中每一個節點相鄰的種子節點的個數，并且對兩個網絡中的節點集合，按照之前計算的相鄰的種子節點個數進行降序排列。第9)～13)行是在對比兩個網絡中排在首位的節點，返回較大的作為最終選中的節點。

3.2.2 節點匹配

當得到節點選擇過程中返回的待匹配節點vselect，接下來就需要基于3.1.2節提出的跨網絡相似性進行匹配。節點匹配算法首先需要確定該用戶節點是來自于網絡X還是來自于網絡Y；然后選擇與vselect跨網絡相似性最高的節點vmatch作為最有可能的匹配返回。節點匹配算法描述如算法3所示。

算法3 節點匹配算法。

輸出 候選匹配節點vmatch。

1)

ifvselect來自網絡Xthen

2)

3)

4)

end for

5)

6)

returnvmatch

7)

else

8)

9)

end if

3.2.3 雙向認證

考慮到在節點選擇和節點匹配階段都需要用到種子節點，根據已有的種子節點來選擇待匹配節點vselect及候選匹配節點vmatch，使得因此一個錯誤的種子節點將會對接下來的迭代過程造成誤導，并且這種壞的影響會不斷積累導致算法失敗。因此本文使用雙向認證的方法來保證每次產生的種子節點的準確性。即驗證與vmatch跨網絡相似性最大的節點是否為vselect：如果是則將(vmatch,vselect)加入到種子節點集；如果不是，則將vselect加入到未匹配隊列中等待機會再匹配，并將vselect重置為vmatch進入新的一輪迭代。雙向認證算法描述如算法4所示。

算法4 雙向認證算法。

輸出 一個新的種子節點。

CrossMatching(vselect,vmatch,S)

1)

2)

3)

S=S∪vnew

4)

5)

6)

vselect=NULL

7)

return NULL

8)

else

9)

將vselect加入到unmapped queue中

10)

vselect=vmatch

11)

12)

return (vselect,vmatch)

13)

end if

其中vnew表示新生成的種子節點。第3)～7)行是在雙向認證成功后，將匹配成功的節點對從尚未匹配的節點集合中刪除，并將它們加入到種子節點集中。第9)～12)行是算法在雙向認證失敗后，將vselect加入到unmapped queue中等待合適的節點與之匹配,并將vselect和vmatch互換并返回，返回之后將會在vselect和vmatch基礎上繼續執行雙向認證過程。

3.2.4 結果剪枝

考慮到本文僅僅利用拓撲信息進行匹配，因此即使加入了雙向認證的過程，算法前期的準確率也不能夠達到100%，也就是說在算法的最后階段，會產生大量的錯誤配對，因此需要一個剪枝的過程將結果中錯誤的匹配排除在結果之外。由于算法在身份識別階段優先選擇最有可能匹配的節點并且使用雙向認證算法，因此有理由相信，早期產生的種子節點有很高的可信度，而后面產生的種子節點錯誤的可能性比較大。所以本文采取一個非常簡單的方式，也就是只選取前期產生的結果作為最終結果。選擇95%、90%或者其他百分比，這個取決于具體的網絡環境。本文實驗部分驗證了剪枝百分比對準確率的影響。

3.3 WHUI算法

算法5展示了基于帶權超圖的跨網絡用戶身份識別(WHUI)算法的完整過程。輸入兩個好友關系網絡及種子節點集合，然后通過在好友關系網絡上構建超圖從而得到節點的跨網絡相似性，最終在身份識別階段通過持續的選擇、匹配、雙向認證，最終對結果剪枝得到完整的結果。

算法5 雙向認證算法。

輸入 好友關系網絡GX(VX,EX)和GY(VY,EY)，超圖權重p、q，匹配前已知的種子用戶集合S；

輸出 最終的種子用戶集合Sresult。

1)

2)

3)

Sresult=S

4)

初始化空隊列unmapped queue

5)

6)

ifvselect=NULL then

7)

8)

9)

end if

10)

(vselect,vmatch)=CrossMatching(vselect,vmatch,Sresult)

11)

end while

12)

對Sresult進行結果剪枝

13)

returnSresult

3.4 時間復雜度分析

一部分是超圖的構建，由于算法在直接相連節點和具有共同好友的節點上構建超邊，因此復雜度分別為O(|VX|+|EX|)和O(|VY|+|EY|)。

另一部分是跨網絡賬號匹配產生的復雜度，在賬號選擇過程中,需要計算每一個未匹配節點的好友中種子節點的個數，它隨種子節點的增加而改變。因此第一次花銷為M+N；第二次只需要計算與新加入的種子節點直接相連的未匹配節點，在最壞的情況下，每一個未匹配節點都需要計算，花銷為M-1+N-1；第三次需要M-2+N-2。以此類推，每一項的通項公式為M+N-2n，到N-1次后算法結束，所以總時間為(M+N)(N-1)-N(N-1)，化簡后為M(N-1)。接著要計算的是賬號匹配和雙向認證階段，需要找出與vselect跨網絡相似性最大的節點然后進行雙向認證，假設vselect∈VX，因此第一次在賬號匹配過程中最多需要計算vselect與N個節點的跨網絡相似性，對應雙向認證需要計算M-1次，第一次時間開銷為M+N-1，第二次為(M-1)+(N-1)-1。每一項的通項公式為M+N-2n-1。同樣到N-1次后算法結束，所以總時間為(M+N)(N-1)-N(N-1)-N，化簡后為M(N-2)。所以賬號在跨網絡匹配部分的復雜度為O(MN)。

綜合超圖構建與跨網絡賬號匹配，得到總的時間復雜度為O(MN)。

4 實驗及結果分析

4.1 實驗數據

4.1.1 DBLP網絡

為了驗證算法的有效性，本文使用文獻[15]中的英文文獻數據庫DBLP來建立一個模擬的社交網絡：DBLP中包含很多文章，每篇文章由多個作者合作完成。將每一個作者作為社交網絡中的用戶，將作者之間的合作關系認為是社交網絡中的好友關系。然后將DBLP數據集中的所有文章隨機分為兩個部分，按照上述方法在這兩個部分上分別構建模擬的社交網絡，從而得到兩個DBLP網絡。這樣，對于屬于兩個部分的兩篇文章，如果這兩個文章中都包含同一作者，那么這個作者在兩個網絡中的兩個賬號就可以組成種子節點。兩個網絡中的用戶數量分別為2 317和2 327。DBLP網絡具體信息如表1所示。

表1 DBLP網絡數據統計Tab. 1 DBLP network data statistics

圖5是兩個網絡度的分布，近似服從冪律分布。

4.1.2 真實社交網絡數據

為了驗證算法的實用性，本文使用文獻[10]提出的標準數據集，該數據集在Twitter和Facebook這兩個社交網絡上，以16位在兩個網絡上都注冊賬號的用戶為起點，通過好友關系逐步擴展網絡，最終得到了1 475個賬號，如表2所示，其中：Facebook賬號有422個，Twitter賬號有1 053個。其中有152個對應關系已知的種子節點。

圖5 DBLP網絡的度分布Fig. 5 Degree distribution of DBLP networks表2 Facebook和Twitter社交網絡數據統計Tab. 2 Social network data statistics of Facebook and Twitter

網絡節點數種子節點數網絡連邊數Facebook422152895Twitter10531525439

圖6是兩個網絡度的分布，近似服從冪律分布。

圖6 Twitter網絡和Facebook網絡的度分布Fig. 6 Degree distribution of Twitter network and Facebook network

4.2 評價指標

本文評價指標采用信息檢索中的準確率P、召回率R、綜合指標F，其計算公式為：

R=Nc/Ne

(6)

P=Nc/Ns

(7)

F=2RP/(R+P)

(8)

其中：Nc是算法識別出的正確匹配的用戶節點的對數；Ne是實驗數據中實際存在的匹配節點對個數；Ns是算法識別出的匹配的節點對(包括正確匹配的和正確匹配的)。

4.3 實驗分析

本文選取度數排名靠前的一部分種子節點作為初始時已知的種子節點，其余的種子節點在初始時作為未匹配節點，在算法結束后用來驗證算法的準確性。

4.3.1 超圖權值的影響

為了驗證超圖權值對實驗結果的影響，令權重p=1，權重q從1遞減到0。在DBLP網絡和真實社交網絡(Facebook和Twitter)上實驗結果如圖7所示。

在DBLP網絡上，當p比q約等于4.5時，F達到最大值62.4%。在真實社交網絡上，當權重p一定(p=1)，q從1開始逐漸減小時，共同好友關系在計算節點相似性時所占比重減小，當q減小到約為p值的十分之一時(p/q≈10)，F值達到最大值72.4%，說明共同好友關系比于直接相連關系相對較弱，過多地依靠共同好友關系來得到節點相似性時，F值將會大幅降低；當q值從0.1繼續減小時，F值降低，說明了共同好友關系在計算用戶相似性時也應該占一定比重，忽略了共同好友關系會導致F值下降。

圖7 綜合指標F隨權重的變化Fig. 7 Change of comprehensive index F with weight

4.3.2 剪枝率的影響

此外，本文還驗證了在不同的剪枝率下算法的評價指標。剪枝率為算法在迭代得到的種子節點集合上所減去的種子節點的比例，結果如圖8所示。

圖8 評價指標隨剪枝率的變化Fig. 8 Change of evaluation indexes with pruning rate

在DBLP網絡上，隨著剪枝率的增加，算法的召回率減小，準確率增大；剪枝率為45%時，F達到最大值62.4%。由于數據集合中種子節點所占比例非常小僅為18%，算法前期可能就挖掘出大部分種子節點，之后便會產生大量錯誤匹配，因此需要減去大部分迭代產生的結果，來保證最優的F值。在真實社交網絡上，當剪枝率為35%的時候，F值達到最大值72.4%。此時雖然召回率不高，但是保證了一定的準確率。

4.3.3 算法性能對比

為了驗證算法的有效性，本文將提出的WHUI與傳統的FRUI算法進行對比，實驗中的參數均選用最佳情況下的取值(p=1，q=0.3，剪枝率在DBLP網絡上設置為90%，在真實社交網絡上設置為35%)。表3匯總了在DBLP網絡和真實社交網絡的測試結果。圖9是兩種算法的評價指標對比。

通過在DBLP網絡上的實驗測試，發現當種子節點數量較少時，對于FRUI算法，由于可以利用的種子節點不多，因此通過節點跨網絡相似度來區分不同的用戶準確率和召回率都相對較低；對于WHUI算法，由于充分利用當前所有種子節點來計算跨網絡相似性，在種子節點數較少時，其準確率、召回率高于FRUI。當種子節點數量增多時，FRUI在召回率和F值上擁有微小的優勢。總的來說，在DBLP網絡上，WHUI相對于FRUI算法，平均F值提高了1.2個百分點。

在真實社交網絡上的測試結果表明，WHUI算法在準確率、召回率和F值上全面優于FRUI，這是因為WHUI算法中使用的超圖模型不僅保留了好友關系網絡中的拓撲信息，還加入了網絡中的異質關系信息，從而更加準確地度量出節點間跨網絡相似性，實現了相對準確的匹配。在真實網絡上，WHUI算法相對于FRUI算法，平均準確率提高了5.5個百分點，平均召回率提高了3.4個百分點，平均F值提高了4.6個百分點。

表3 WHUI和FRUI節點匹配效果對比Tab. 3 Comparison of node matching results by WHUI and FRUI

圖9 WHUI與FRUI的評價指標對比Fig. 9 Comparison of evaluation indexes of WHUI and FRUI

4.3.4 算法時間復雜度對比

在DBLP網絡和真實社交網絡上對比了WHUI與FRUI的算法效率，參數設置與4.3.3節中的實驗參數相同，實驗結果如圖10所示。

從圖10中看出，WHUI算法運行時間普遍高于FRUI算法。這是因為WHUI算法相比FRUI算法具有超圖構建以及雙向認證的過程，這兩個步驟在一定程度上增加了時間開銷，但是同時也提高了算法的準確率，在實際應用中，多出的時間開銷在可接受的范圍之內。

圖10 WHUI與FRUI的效率比較Fig. 10 Time complexity comparison of WHUI and FRUI

5 結語

針對現有匹配算法對于社交網絡中異質關系利用率不高的缺點，本文提出了使用帶權超圖來描述節點間的社會關系，帶權超圖不僅保留了好友關系網絡中原始的拓撲信息，而且還可以體現網絡中的異質關系。在帶權超圖的基礎上定義節點間的跨網絡相似性，并結合迭代匹配算法實現更加準確的跨網絡用戶身份識別。實驗結果表明，本文算法在準確率和綜合評價指標上均有明顯的優勢，驗證了帶權超圖模型在跨網絡節點相似性計算上的有效性。下一步將進一步細化網絡中的異質關系，對不同類型的異質關系賦予不同的超圖權重，以此實現在異質關系信息已知的條件下，更加準確地跨網絡身份識別。

References)

[1] 孟波.多社交網絡用戶身份識別算法研究[D].大連:大連理工大學,2015:1-10. (MENG B. Research on algorithms for identifying users across multiple online social networks [D]. Dalian: Dalian University of Technology, 2015:1-10.)

[2] 劉東,吳泉源,韓偉紅,等.基于用戶名特征的用戶身份統一性判定方法[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.)

[3] PERITO D, CASTELLUCCIA C, KAAFAR M A, et al. How unique and traceable are usernames? [C]// PETS’11: Proceedings of the 2011 11th International Conference on Privacy Enhancing Technologies. Berlin: Springer, 2011: 1-17.

[4] LIU J, ZHANG F, SONG X, et al. What’s in a name?: an unsupervised approach to link users across communities [C]// Proceedings of the 2013 ACM International Conference on Web Search and Data Mining. New York: ACM, 2013: 495-504.

[5] ZHENG R, LI J, CHEN H, et al. A framework for authorship identification of online messages: writing-style features and classification techniques[J]. Journal of the American Society for Information Science and Technology, 2006, 57(3): 378-393.

[6] ALMISHARI M, TSUDIK G. Exploring linkability of user reviews [C]// Proceedings of the 2012 European Symposium on Research in Computer Security, LNCS 7459. Berlin: Springer, 2012: 307-324.

[7] ZHOU X, LIANG X, ZHANG H, et al. Cross-platform identification of anonymous identical users in multiple social media networks [J]. IEEE Transactions on Knowledge & Data Engineering, 2016, 28(2): 411-424.

[8] 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.

[9] NARAYANAN A, SHMATIKOV V. De-anonymizing social networks [C]// Proceedings of the 30th IEEE Symposium on Security and Privacy. Piscataway, NJ: IEEE, 2009: 173-187.

[10] BARTUNOV S, KORSHUNOV A, PARK S T, et al. Joint link-attribute user identity resolution in online social networks [C]// SNAKDD’12: Proceedings of the 2012 6th International Conference on Knowledge Discovery and Data Mining, Workshop on Social Network Mining and Analysis. New York, ACM, 2012: 1-9.

[11] MAN T, SHEN H, LIU S, et al. Predict anchor links across social networks via an embedding approach [C]// IJCAI’16: Proceedings of the 2016 International Joint Conference on Artificial Intelligence. New York, ACM, 2016: 1823-1829.

[12] BERGE C. Graphs and Hypergraphs [M]. Amsterdam: Elsevier, 1973: 389-390.

[13] BERGE C. Hypergraphs: Combinatorics of Finite Sets [M]. Amsterdam: Elsevier, 1984: 3-4.

[15] 桑基韜,路冬媛,徐常勝.基于共同用戶的跨網絡分析:社交媒體大數據中的多源問題[J].科學通報,2014,59(36):3554-3560.(SANG J T, LU D Y, XU C S. Overlapped user-based cross-network analysis: exploring variety in big social media data [J]. Chinese Science Bulletin, 2014, 59(36): 3554-3560.)[15] DENG H, HAN J, ZHAO B, et al. Probabilistic topic models with biased propagation on heterogeneous information networks [C]// Proceedings of the 2011 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2011: 1271-1279.

This work is partially supported by the National Natural Science Foundation of China (61521003).

XUQian, born in 1993, M. S. candidate. His research interests include social network mining, machine learning.

CHENHongchang, born in 1964, Ph. D., professor. His research interests include information security of telecommunication network, information communication security.

WUZheng, born in 1992, M. S. candidate. His research interests include complex network, network large data analyzing and processing.

HUANGRuiyang, born in 1986, Ph. D., associate research fellow. His research interests include network large data analyzing and processing, big data distributed processing.

Useridentificationmethodacrosssocialnetworksbasedonweightedhypergraph

XU Qian*, CHEN Hongchang, WU Zheng, HUANG Ruiyang

(NationalDigitalSwitchingSystemEngineering&TechnologicalResearchCenter,ZhengzhouHenan450002,China)

With the emergence of various social networks, the social media network data is analyzed from the perspective of variety by more and more researchers. The data fusion of multiple social networks relies on user identification across social networks. Concerning the low utilization problem of heterogeneous relation between social networks of the traditional Friend Relationship-based User Identification (FRUI) algorithm, a new Weighted Hypergraph based User Identification (WHUI) algorithm across social networks was proposed. Firstly, the weighted hypergraph was accurately constructed on the friend relation networks to describe the friend relation and the heterogeneous relation in the same network, which improved the accuracy of presenting topological environment of nodes. Then, on the basis of the constructed weighted hypergraph, the cross network similarity between nodes was defined according to the consistency of nodes’ topological environment in different networks. Finally, the user pair with the highest cross network similarity was chosen to match each time by combining with the iterative matching algorithm, while two-way authentication and result pruning were added to ensure the recognition accuracy. The experiments were carried out in the DBLP cooperation networks and real social networks. The experimental results show that, compared with the existing FRUI algorithm, the average precision, recall,Fof the proposed algorithm is respectively improved by 5.5 percentage points, 3.4 percentage points, 4.6 percentage points in the real social networks. The WHUI algorithm can effectively improve the precision and recall of user identification in practical applications by utilizing only network topology information.

user identification across social network; weighted hypergraph; heterogeneous relation; node similarity; iterative matching

2017- 05- 23;

2017- 08- 10。

國家自然科學基金資助項目(61521003)。

徐乾(1993—)，男，遼寧大連人，碩士研究生，主要研究方向：社交網絡挖掘、機器學習； 陳鴻昶(1964—)，男，河南鄭州人，教授，博士，主要研究方向：電信網信息關防、信息通信安全； 吳錚(1992—)，男，江蘇徐州人，碩士研究生，主要研究方向：復雜網絡、網絡大數據分析與處理； 黃瑞陽(1986—)，男，福建漳州人，副研究員，博士，主要研究方向：網絡大數據分析與處理、大數據分布式處理。

1001- 9081(2017)12- 3435- 07

10.11772/j.issn.1001- 9081.2017.12.3435

(*通信作者電子郵箱549529376@qq.com)

TP391.4

A