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

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

基于帶權超圖的跨網(wǎng)絡用戶身份識別方法

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

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

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

跨網(wǎng)絡用戶身份識別；帶權超圖；異質關系；節(jié)點相似度；迭代匹配

0 引言

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

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

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

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

1 相關定義

1.1 用戶身份識別

1.2 種子節(jié)點

1.3 基于好友關系的跨網(wǎng)絡用戶身份識別

(1)

2 超圖模型構建

2.1 超圖

(2)

2.2 超圖模型

2.3 在好友關系網(wǎng)絡上構建超圖模型

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

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

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

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

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

2.3.1 超邊權重設定

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

2.3.2 超圖模型構建算法

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

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

輸入 好友關系網(wǎng)絡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)中含有兩個或兩個以上的節(jié)點

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的所有鄰居節(jié)點組成的集合，第3)～10)行是在直接相連的兩個節(jié)點上構建超邊，第11)～14)行是在擁有共同好友的兩個或多個節(jié)點上構建超邊。

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

3.1 節(jié)點相似性計算

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

3.1.1 同一網(wǎng)絡中的節(jié)點間相似性

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

(3)

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

3.1.2 跨網(wǎng)絡的節(jié)點間相似性

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

(4)

(5)

3.2 跨網(wǎng)絡節(jié)點匹配

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

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

3.2.1 節(jié)點選擇

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

算法2 節(jié)點選擇算法。

輸出 待匹配的用戶節(jié)點vselect。

1)

if unmapped queue非空 then

2)

return 隊列中第一個元素

3)

end if

4)

5)

計算v0的鄰居中種子節(jié)點的個數(shù)

6)

end for

7)

8)

9)

10)

11)

else

12)

13)

end if

14)

returnvselect

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

3.2.2 節(jié)點匹配

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

算法3 節(jié)點匹配算法。

輸出 候選匹配節(jié)點vmatch。

1)

ifvselect來自網(wǎng)絡Xthen

2)

3)

4)

end for

5)

6)

returnvmatch

7)

else

8)

9)

end if

3.2.3 雙向認證

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

算法4 雙向認證算法。

輸出 一個新的種子節(jié)點。

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

3.2.4 結果剪枝

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

3.3 WHUI算法

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

算法5 雙向認證算法。

輸入 好友關系網(wǎng)絡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 時間復雜度分析

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

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

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

4 實驗及結果分析

4.1 實驗數(shù)據(jù)

4.1.1 DBLP網(wǎng)絡

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

表1 DBLP網(wǎng)絡數(shù)據(jù)統(tǒng)計Tab. 1 DBLP network data statistics

圖5是兩個網(wǎng)絡度的分布，近似服從冪律分布。

4.1.2 真實社交網(wǎng)絡數(shù)據(jù)

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

圖5 DBLP網(wǎng)絡的度分布Fig. 5 Degree distribution of DBLP networks表2 Facebook和Twitter社交網(wǎng)絡數(shù)據(jù)統(tǒng)計Tab. 2 Social network data statistics of Facebook and Twitter

網(wǎng)絡節(jié)點數(shù)種子節(jié)點數(shù)網(wǎng)絡連邊數(shù)Facebook422152895Twitter10531525439

圖6是兩個網(wǎng)絡度的分布，近似服從冪律分布。

圖6 Twitter網(wǎng)絡和Facebook網(wǎng)絡的度分布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是算法識別出的正確匹配的用戶節(jié)點的對數(shù)；Ne是實驗數(shù)據(jù)中實際存在的匹配節(jié)點對個數(shù)；Ns是算法識別出的匹配的節(jié)點對(包括正確匹配的和正確匹配的)。

4.3 實驗分析

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

4.3.1 超圖權值的影響

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

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

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

4.3.2 剪枝率的影響

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

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

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

4.3.3 算法性能對比

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

通過在DBLP網(wǎng)絡上的實驗測試，發(fā)現(xiàn)當種子節(jié)點數(shù)量較少時，對于FRUI算法，由于可以利用的種子節(jié)點不多，因此通過節(jié)點跨網(wǎng)絡相似度來區(qū)分不同的用戶準確率和召回率都相對較低；對于WHUI算法，由于充分利用當前所有種子節(jié)點來計算跨網(wǎng)絡相似性，在種子節(jié)點數(shù)較少時，其準確率、召回率高于FRUI。當種子節(jié)點數(shù)量增多時，F(xiàn)RUI在召回率和F值上擁有微小的優(yōu)勢?？偟膩碚f，在DBLP網(wǎng)絡上，WHUI相對于FRUI算法，平均F值提高了1.2個百分點。

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

表3 WHUI和FRUI節(jié)點匹配效果對比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網(wǎng)絡和真實社交網(wǎng)絡上對比了WHUI與FRUI的算法效率，參數(shù)設置與4.3.3節(jié)中的實驗參數(shù)相同，實驗結果如圖10所示。

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

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

5 結語

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

References)

[1] 孟波.多社交網(wǎng)絡用戶身份識別算法研究[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] 劉東,吳泉源,韓偉紅,等.基于用戶名特征的用戶身份統(tǒng)一性判定方法[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] ?；w,路冬媛,徐常勝.基于共同用戶的跨網(wǎng)絡分析:社交媒體大數(shù)據(jù)中的多源問題[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—)，男，遼寧大連人，碩士研究生，主要研究方向：社交網(wǎng)絡挖掘、機器學習； 陳鴻昶(1964—)，男，河南鄭州人，教授，博士，主要研究方向：電信網(wǎng)信息關防、信息通信安全； 吳錚(1992—)，男，江蘇徐州人，碩士研究生，主要研究方向：復雜網(wǎng)絡、網(wǎng)絡大數(shù)據(jù)分析與處理； 黃瑞陽(1986—)，男，福建漳州人，副研究員，博士，主要研究方向：網(wǎng)絡大數(shù)據(jù)分析與處理、大數(shù)據(jù)分布式處理。

1001- 9081(2017)12- 3435- 07

10.11772/j.issn.1001- 9081.2017.12.3435

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

TP391.4

A