融合多特征的跨社交網(wǎng)絡用戶在線識別方法研究

盧 菁，王菊鈿，劉 叢

(上海理工大學 光電信息與計算機工程學院，上海 200093)

1 引 言

隨著社交網(wǎng)絡的廣泛普及和興起，人們?yōu)闈M足不同的服務需求會加入多個社交網(wǎng)絡.在不同的社交網(wǎng)絡中找到屬于同一自然人的用戶即為跨社交網(wǎng)絡用戶識別問題(通常也稱為社交網(wǎng)絡用戶對齊問題、跨社交網(wǎng)絡實體匹配問題以及錨鏈接預測問題等).跨社交網(wǎng)絡用戶識別可實現(xiàn)刻畫用戶畫像、提高社交效率、投放精準廣告等.

當前的跨社交網(wǎng)絡用戶識別研究，按照使用特征的信息不同，大致分為基于屬性特征的識別方法、基于結(jié)構(gòu)特征的識別方法和結(jié)合兩種特征的識別方法，近年來還出現(xiàn)了針對結(jié)構(gòu)信息獲取限制問題的用戶識別方法.

1)基于屬性特征.屬性指用戶簡檔中的屬性信息，如用戶名、個人簡介、教育經(jīng)歷等.表1顯示了社交網(wǎng)絡中用戶簡檔中的屬性信息.文獻[1]結(jié)合簡檔屬性的匹配分數(shù)和人為設置的權重判斷來自兩個網(wǎng)絡的實體對是否指向同一個現(xiàn)實實體.文獻[2]利用屬性信息構(gòu)建分類特征，并通過第3個社交網(wǎng)絡為無法直接匹配的跨社交網(wǎng)絡用戶對建立關聯(lián).文獻[3]分析了用戶名的n-gram概率以估計用戶名稀有性或通用性，利用無監(jiān)督方法識別具有通用用戶名的用戶，并將具有同一稀有用戶名的用戶識別為相同用戶.以上基于屬性特征的用戶識別方法取得一定的成果，但該類方法往往面臨屬性數(shù)據(jù)缺失、不一致、異構(gòu)等問題，且容易受到惡意偽裝用戶的干擾.

表1 用戶及候選用戶簡檔中的屬性信息

2)基于結(jié)構(gòu)特征.用戶與社交網(wǎng)絡中其他用戶的鏈接關系即為用戶的結(jié)構(gòu)信息.不同社交網(wǎng)絡中屬于同一自然人的用戶的網(wǎng)絡結(jié)構(gòu)往往是相似且難以模擬的.現(xiàn)存許多研究通過網(wǎng)絡嵌入、隨機游走技術提取用戶的結(jié)構(gòu)特征對跨社交網(wǎng)絡的用戶進行識別.文獻[4]提出了網(wǎng)絡嵌入模型IONE將用戶關系表征為向量以鏈接跨社交網(wǎng)絡的用戶.文獻[5]提出了FRUI-P算法通過隨機游走技術構(gòu)建FFVM模型提取朋友特征向量以評估跨社交網(wǎng)絡中兩個用戶的相似性.文獻[6]提出將社交網(wǎng)絡表征為低維的向量空間，通過神經(jīng)網(wǎng)絡等方法得到錨鏈候選集合，最后通過G-S算法進行穩(wěn)定匹配的IAUE模型以提高用戶識別的準確度.然而，僅利用結(jié)構(gòu)信息容易將用戶抽象成網(wǎng)絡中一個沒有身份信息的用戶，導致識別準確率不高.另外，如今社交網(wǎng)絡更新變化快，用戶可能隨著時間變化中斷或者形成新的關系，以上基于離線全局網(wǎng)絡結(jié)構(gòu)的跨社交網(wǎng)絡用戶識別方法將面臨社交網(wǎng)絡結(jié)構(gòu)更新消耗大的問題.

3)結(jié)合屬性特征和局部結(jié)構(gòu)特征.基于以上提出的問題，近幾年出現(xiàn)了許多基于用戶屬性信息和局部結(jié)構(gòu)信息即用戶鄰居信息提取特征進行跨社交網(wǎng)絡用戶識別的研究.文獻[7]利用一個線性模型結(jié)合屬性相似度和好友相似度計算得用戶整體相似度以識別用戶.文獻[8]通過利用眾包識別激活用戶錨點對以計算用戶的全視角特征，并將其與屬性特征、局部結(jié)構(gòu)特征結(jié)合以迭代識別未匹配的用戶對.然而，近幾年許多社交網(wǎng)絡為保護用戶的隱私限制了獲取用戶結(jié)構(gòu)信息的API的訪問頻率.例如，Twitter設置了每小時最多允許請求150次API，且部分API限制每次調(diào)用僅返回不多于200條數(shù)據(jù);新浪微博普通權限下訪問API的總次數(shù)為每小時1000次，且不同功能的API存在不同的限制，例如，調(diào)用獲取用戶好友列表的API最多能夠獲取30%的好友信息，而對于獲取用戶跟隨者列表的API，每次調(diào)用最多能得到5個跟隨者信息.因此，在API的訪問限制下，以上結(jié)合屬性特征和局部結(jié)構(gòu)特征的跨社交網(wǎng)絡用戶識別方法將因獲取不到用戶識別所需的結(jié)構(gòu)數(shù)據(jù)而無法得到期望的用戶識別結(jié)果.

4)基于結(jié)構(gòu)信息獲取限制的用戶在線識別.文獻[9]基于API的調(diào)用限制問題設計了爬蟲策略TOP動態(tài)分配API以迭代獲取結(jié)構(gòu)信息，并結(jié)合了屬性信息和有限的結(jié)構(gòu)信息進行跨社交網(wǎng)絡的用戶識別.該研究在一定范圍內(nèi)解決了結(jié)構(gòu)信息獲取限制下的跨社交網(wǎng)絡的用戶識別問題.然而，TOP爬蟲策略在動態(tài)獲取結(jié)構(gòu)信息過程中始終將API分配給評分最高的候選用戶，容易導致其他與最高評分相近的候選用戶分配不到API，從而得不到更高的識別精度.因此，需要設計一個動態(tài)爬蟲策略實現(xiàn)有限API的優(yōu)質(zhì)調(diào)配以獲取更多隱含有效信息的結(jié)構(gòu)數(shù)據(jù).

綜上所述，跨社交網(wǎng)絡的用戶識別主要面臨屬性信息存在干擾信息、單特征識別準確度低、離線全局結(jié)構(gòu)更新消耗大、在線獲取結(jié)構(gòu)信息的API存在訪問限制等問題.因此，本文將跨社交網(wǎng)絡用戶識別視為一種在線任務，設計了爬蟲策略DYN動態(tài)獲取結(jié)構(gòu)信息，并改進了屬性特征和局部結(jié)構(gòu)特征的提取方法，最后利用邏輯回歸模型融合多特征構(gòu)建用戶識別模型實現(xiàn)了跨社交網(wǎng)絡的用戶在線識別.本文的貢獻如下：

1)針對獲取結(jié)構(gòu)信息API的訪問限制，設計了動態(tài)爬蟲策略DYN，對有限的API進行優(yōu)質(zhì)的調(diào)配以獲取得更多有效結(jié)構(gòu)數(shù)據(jù).

2)改進了屬性特征和局部結(jié)構(gòu)特征的提取方法，提高了跨社交網(wǎng)絡用戶在線識別的精確度和召回率.

3)結(jié)合邏輯回歸模型構(gòu)建了融合屬性特征和局部結(jié)構(gòu)特征的多特征跨社交網(wǎng)絡用戶識別模型，提高了跨社交網(wǎng)絡用戶識別的精確度和召回率.

4)在新浪微博和知乎中獲取了大規(guī)模用戶數(shù)據(jù)，對本文設計的方法進行訓練和驗證.與已有的方法相比，本文的方法具有更高的精確度和召回率.

2 問題定義

2.1 相關定義及符號

定義1.社交網(wǎng)絡.將社交網(wǎng)絡表示為G={V，E}，其中，V表示用戶集合，E?{(vi，vj)|vi，vj∈V}(i，j，…，N)表示用戶間的關系集合.本文為了方便模型建立和計算，選取兩個網(wǎng)絡進行建模，一個網(wǎng)絡為源網(wǎng)絡，另一個網(wǎng)絡為目標網(wǎng)絡，分別記為Gs={Vs，Es}和Gt={Vt，Et}.v∈V代表用戶集V中的用戶v.

定義2.候選用戶集合C.候選用戶表示在目標網(wǎng)絡中潛在的與源網(wǎng)絡中的待匹配用戶屬于同一自然人可能性較大的用戶，候選用戶集合為候選用戶組成的集合.

如表1所示，源網(wǎng)絡中的用戶u在目標網(wǎng)絡中的候選用戶為v1，v2，v3，因此用戶u的候選用戶集為C={v1，v2，v3}.

定義3.候選用戶對集合T.源網(wǎng)絡中的用戶分別與其在目標網(wǎng)絡中的候選用戶組成的用戶對.候選用戶對集合為用戶對應的所有候選用戶對組成的集合.

例如，表1中所示，源網(wǎng)絡用戶u及其候選用戶組成的用戶對集合為T={(u，v1)，(u，v2)，(u，v3)}.

定義4.跟隨者.在社交網(wǎng)絡中，用戶v主動跟隨用戶u，而用戶u沒有跟隨v，即稱用戶v為用戶u的跟隨者.

定義5.好友.若用戶u和用戶v互為對方的跟隨者，則u和v互為對方的好友.

定義6.鄰居.在本文中鄰居指用戶的跟隨者或好友.

定義7.特征向量X.特征向量X={a1，..，an，b1，..，bn}由屬性特征和局部結(jié)構(gòu)特征構(gòu)成，其中ai為計算用戶的屬性相似度得到的屬性特征，bi為根據(jù)用戶鄰居信息計算得到的局部結(jié)構(gòu)特征.

定義8.最佳映射.對于源網(wǎng)絡中用戶vs，vs的候選用戶集合C中與其屬于同一自然人概率最高的候選用戶即為用戶vs在目標網(wǎng)絡的最佳映射.

跨社交網(wǎng)絡用戶在線識別問題可定義為：給定源網(wǎng)絡用戶vs及其在目標網(wǎng)絡中的候選用戶集合C，在C中找到與vs屬于同一自然人的最佳映射.

2.2 用戶識別模型

本文通過訓練得到的邏輯回歸模型參數(shù)構(gòu)建用戶識別模型.邏輯回歸[10，11](Logistic Regression)模型是一種非線性0/1分類模型.假設數(shù)據(jù)集D={Xi，Yi}，i=1，…，n，Xi∈R，Yi∈{0，1}，Xi為輸入變量集合，Yi為分類結(jié)果集合.邏輯回歸模型預測函數(shù)的值表示分類結(jié)果為1的概率，該預測函數(shù)為：

(1)

其中，輸入向量X={x0，x1，x2，…，xn}是樣本特征向量，x0為1.θ={θ0，θ1，…，θn}是特征向量對應的權重向量，即邏輯回歸模型的參數(shù).通過最大似然估計求解模型的參數(shù)，即將對數(shù)似然函數(shù)取反構(gòu)造損失函數(shù)，如式(2)所示.

(2)

通過梯度下降法求解出一組θ值使得J(θ)最小，θ的迭代更新公式如式(3)所示：

(3)

其中，α為梯度下降的學習率.通過以上的步驟便可求出邏輯回歸模型的參數(shù)向量θ.

本文研究的跨社交網(wǎng)絡用戶在線識別問題可以轉(zhuǎn)換為判斷源網(wǎng)絡中用戶vs及其在目標網(wǎng)絡中的候選用戶vt是否屬于同一自然人的二分類問題.通過利用訓練數(shù)據(jù)集提取其用戶對的屬性特征和局部結(jié)構(gòu)特征訓練得到邏輯回歸模型參數(shù)向量θ，并利用參數(shù)向量θ構(gòu)建用戶識別模型，如式(4)所示.

(4)

MATCH(vs，vt)表示用戶對(vs，vt)屬于同一自然人的概率.因此，將用戶對(vs，vt)的屬性特征和結(jié)構(gòu)特征組成特征向量X計算MATCH(vs，vt)，可以得到(vs，vt)屬于同一自然人的概率估計，該概率即為(vs，vt)的匹配分數(shù).

2.3 方法流程

本文提出的跨社交網(wǎng)絡用戶在線識別方法(MCUOR)的流程如圖1所示，主要分為以下3個部分：

圖1 跨社交網(wǎng)絡用戶在線識別方法流程圖

1)提取屬性特征.通過計算候選用戶對應屬性信息的相似度提取屬性特征.

2)提取結(jié)構(gòu)特征.通過動態(tài)爬蟲策略DYN利用有限的API預算獲取候選用戶的局部結(jié)構(gòu)即鄰居信息，然后計算候選用戶對的跟隨者重疊度和好友重疊度以提取局部結(jié)構(gòu)特征.

3)跨社交網(wǎng)絡用戶在線識別.通過用戶識別模型結(jié)合屬性特征和局部結(jié)構(gòu)特征計算候選用戶對的匹配分數(shù)，并根據(jù)相應算法得到用戶識別結(jié)果.

3 屬性特征提取

本文利用簡檔中的多個屬性提取用戶的屬性特征，綜合考慮各屬性項的數(shù)據(jù)類型以及現(xiàn)實特性選擇合適的相似度計算方法以提取每個屬性對應的特征.

3.1 用戶主觀描述類

在用戶簡檔中，存在一類需用戶編寫文本的主觀描述類型屬性，其中往往隱含了用戶獨特的書面語言組織習慣.本文利用word2vec[12]模型將文本信息重構(gòu)到向量空間得到詞向量模型以計算用戶主觀描述類型屬性的相似度.本文基于微博語料庫采用word2vec中的CBOW[13]模型進行訓練得到詞向量庫，CBOW模型通過給定上下文contextt預測出詞wt，其損失函數(shù)為：

JCBOW=-∑wt∈Clogp(wt|contextt)

(5)

C為微博預料庫中的所有詞語，k為wt上下文窗口大小.利用反向傳播更新模型參數(shù)使得公式(5)的值最小從而訓練得到word2vec詞向量模型.

對于用戶vs和vt，將其主觀描述類屬性中的文本經(jīng)過分詞和停用詞過濾等操作得到的詞語依次輸入到訓練好的n維word2vec模型中得到相應的n維詞向量，并通過累加法將文本中所有詞對應的詞向量相加得到對應的句向量Ds、Dt.最后，結(jié)合句向量和余弦相似度度量計算vs和vt主觀描述屬性的相似度Fsd(vs，vt)，如式(6)所示.

(6)

個人簡介、職業(yè)經(jīng)歷和教育經(jīng)歷這3個簡檔屬性均屬于主觀描述類型，因此可通過以上方法計算相似度以提取這些屬性對應.

3.2 用戶名

在社交網(wǎng)絡中，許多用戶傾向于采用相似的文本搭配特殊符號組合成獨特的用戶名，文本往往包含了用戶名的基本信息，而特殊字符反映了用戶特殊的命名喜好.因此本文將用戶名拆分為文本和特殊符號并分別計算相似度以提取用戶名特征.

文本相似度：本文采用Jaro距離[14]計算用戶名文本相似度.設用戶vs和vt對應的用戶名文本分別為qs和qt，|qs|和|qt|為文本長度，m是公共字符的個數(shù)，t是換位的個數(shù).因此用戶名文本相似度公式如式(7)所示.

(7)

特殊符號相似度：設用戶vs和vt的用戶名特殊符號組成的字符串分別為rs、rt，本文采用 Jaccard 相似系數(shù)[15，16]計算用戶名特殊字符串的相似度，其計算公式如式(8)所示.

(8)

因此，用戶名的特征計算公式如式(9)所示.

Fn(vs，vt)=Fbn(vs，vt)+Fsn(vs，vt)

(9)

3.3 用戶跟隨者數(shù)

社交網(wǎng)絡中節(jié)點的度為與目標節(jié)點連接的節(jié)點總數(shù).文獻[17]提出度中心性的定義，即一個節(jié)點的度越大，其在社交網(wǎng)絡中的影響越大.屬于同一自然人的用戶在社交網(wǎng)絡中的影響力往往是相近的.用戶的跟隨者數(shù)量為該用戶在社交網(wǎng)絡中的入度，因此本文采用度中心性計算用戶跟隨者數(shù)相似度以表示兩個用戶在社交網(wǎng)絡中的影響差異，設社交網(wǎng)絡Gs用戶vs和社交網(wǎng)絡Gt用戶vt的入度分別為ks和kt，則用戶的跟隨者數(shù)相似度為：

(10)

其中，ns、nt分別為社交網(wǎng)絡Gs和Gt的節(jié)點度數(shù).

4 局部結(jié)構(gòu)特征提取

跨社交網(wǎng)絡用戶在線識別的局部結(jié)構(gòu)特征提取過程如圖2所示.對于待識別用戶對應的候選用戶對集合，在未用完API預算時，利用已知結(jié)構(gòu)信息提取結(jié)構(gòu)特征并結(jié)合屬性特征計算候選用戶對的動態(tài)評分，然后根據(jù)動態(tài)評分和爬蟲策略DYN將API分配給候選用戶以迭代獲取其結(jié)構(gòu)信息;在用完API預算后，利用已獲得結(jié)構(gòu)信息提取局部結(jié)構(gòu)特征.

圖2 局部結(jié)構(gòu)特征提取流程

4.1 局部結(jié)構(gòu)特征提取方法

給定源網(wǎng)絡用戶vs及目標網(wǎng)絡用戶vt，本文首先通過用戶識別模型得到vs鄰居的最佳映射以構(gòu)建用戶對(vs，vt)的鄰居重疊集合，然后根據(jù)鄰居重疊集合分別計算(vs，vt)的跟隨者重疊度和好友重疊度以提取(vs，vt)局部結(jié)構(gòu)特征.

4.1.1 鄰居重疊集合

跟隨者重疊集合和好友重疊集合的計算方法是一樣的，因此使用“鄰居重疊集合”泛指跟隨者重疊集合和好友重疊集合以描述該計算方法.

已知vs的鄰居集合為Γ(vs)，對于任意f∈Γ(vs)，為節(jié)省API資源，僅通過屬性信息計算得到f的最佳映射.因此，將屬性特征與值為0的結(jié)構(gòu)特征組成的特征向量輸入到用戶識別模型中計算f與其候選用戶的匹配分數(shù)，匹配分數(shù)最大的候選用戶為f在目標網(wǎng)絡中的最佳映射f′，S(f′)為(f，f′)對應的匹配分數(shù).將用戶vs所有鄰居的最佳映射存儲到vs鄰居最佳映射集合M(vs)中，則vs與vt的鄰居重疊集合為vs鄰居最佳映射集合和vt鄰居集合的交集，如公式(11)所示.

L(vs，vt)=M(vs)∩Γ(vt)

(11)

如圖3中的例子所示，源網(wǎng)絡中用戶v與目標網(wǎng)絡中用戶v′的鄰居重疊集合為{a′，c′}，a′對應的匹配分數(shù)為S(a′)=0.8，c′對應的匹配分數(shù)為S(c′)=0.6.

圖3 跨社交網(wǎng)絡用戶鄰居重疊示意圖

4.1.2 用戶跟隨者重疊度

對于用戶vs和vt，通過計算得到用戶vs鄰居最佳映射集合M(vs)以及用戶對(vs，vt)的跟隨者重疊集合L(vs，vt).本文通過使用加權Jaccard相似度(WJ)[9]結(jié)合跟隨者重疊集合中跟隨者的匹配分數(shù)計算用戶跟隨者的重疊度，WJ將重疊度的計算分為WJ(a)和WJ(b)兩部分.WJ(a)表示重疊跟隨者在vs鄰居最佳映射集合中所占比重，即L(vs，vt)中用戶對應的匹配分數(shù)總和與M(vs)中用戶匹配分數(shù)總和的比值，計算公式如式(12)所示.

(12)

WJ(b)表示重疊跟隨者在vt的跟隨者中所占比重，即L(vs，vt)中用戶匹配分數(shù)總和與vt的跟隨者總數(shù)的比值，其計算公式如式(13)所示.

(13)

因此，用戶對(vs，vt)的跟隨者重疊度Fg(vs，vt)如式(14)所示.

Fg(vs，vt)=WJ(a)+WJ(b)

(14)

4.1.3 用戶好友重疊度

不同社交網(wǎng)絡中，擁有相似的好友圈，且與好友圈中好友關聯(lián)程度相近的用戶屬于同一自然人的可能性較大[18，19].因此本文通過計算用戶與好友關聯(lián)程度為每個好友賦予權重，并結(jié)合好友權重和好友最佳映射對應的匹配分數(shù)計算好友重疊度.

對于用戶vs的好友i，通過計算用戶v的好友集合Γ(vs)與i的好友集合Γ(i)的重疊度好友i賦予權重，其權重計算如公式(15)所示：

(15)

圖4 源網(wǎng)絡用戶好友權重示意圖

本文結(jié)合好友重疊集合中好友的權重和好友最佳映射的匹配分數(shù)改進了加權Jaccard相似度(IWJ)以計算好友重疊度.與WJ的計算類似，IWJ將重疊度的計算分為IWJ(a)和IWJ(b)兩部分，IWJ(a)計算好友重疊集合L(vs，vt)在vs好友映射集合M(vs)中所占比重其計算公式如式(16)所示.

(16)

IWJ(b)計算重疊好友在vt好友中所占比重，其計算公式如式(17)所示.

(17)

綜上所述，用戶對(vs，vt)好友相似度的計算如式(18)所示.

Fh(vs，vt)=IWJ(a)+IWJ(b)

(18)

根據(jù)用戶及其不同好友之間的不同的關聯(lián)程度為用戶的好友賦予權重，可以更加有效地利用好友信息，從而實現(xiàn)更加精準地對跨社交網(wǎng)絡用戶進行識別.

4.2 動態(tài)評分函數(shù)

對用戶進行動態(tài)評分時，除了鄰居重疊集合中的節(jié)點外，也應考慮候選用戶鄰居集合中不重疊節(jié)點以及未知節(jié)點對動態(tài)爬蟲的影響，因此本文在構(gòu)建動態(tài)評分時加入了Cu和Cn，Cu為未知鄰居分數(shù)，Cn為已知不重疊鄰居分數(shù).Cu代表了用戶的未知鄰居節(jié)點在動態(tài)評分過程中的影響，Cu計算公式如式(19)所示.

(19)

其中，Uk(vs，vt)表示用戶vs的候選用戶vt未知鄰居總數(shù)，即Uk(vs，vt)=|vt.out|-|Γ(vt)|，|vt.out|表示候選用戶鄰居總數(shù).在動態(tài)爬蟲過程中，擁有越多未知鄰居，其Uk越大，Cu越大.

Cn表明了候選用戶鄰居中被判斷為不重疊的鄰居對動態(tài)爬蟲的影響，Cn的計算公式如式(20)所示.

(20)

其中，Nl(vs，vt)表示候選用戶已知跟隨者中不重疊用戶的總數(shù)Nl(vs，vt)=|Γ(vt)-M(vs)|.當候選用戶中不重疊的鄰居數(shù)量增多時，Nl相應增大，Cn相應減小并且Nl越大，Cn減少速度越快.

因此，本文通過訓練得到的邏輯回歸模型參數(shù)θ結(jié)合屬性特征、局部結(jié)構(gòu)特征以及Cu和Cn構(gòu)造動態(tài)評分函數(shù)，因此動態(tài)評分函數(shù)如式(21)所示.

(21)

給定源網(wǎng)絡用戶vs和其在目標網(wǎng)絡候選用戶vt，在動態(tài)匹配過程中通過利用屬性信息提取屬性特征和已獲取鄰居信息提取局部結(jié)構(gòu)特征，將屬性特征和局部結(jié)構(gòu)特征組成(vs，vt)的特征向量X，并根據(jù)鄰居信息的獲取情況計算Cu和Cn，最后利用動態(tài)評分函數(shù)MATCH_DYN(vs，vt)計算用戶對(vs，vt)的動態(tài)匹配分數(shù).

4.3 動態(tài)爬蟲策略

本文設計了一種根據(jù)動態(tài)評分占比分配API的迭代式爬蟲策略DYN(v，C，E)，給定API預算E、待識別用戶v及其在目標網(wǎng)絡中的候選用戶集合C，通過爬蟲策略DYN迭代分配預算以獲取C中候選用戶c的鄰居信息.在每次迭代開始前，根據(jù)動態(tài)匹配分數(shù)對候選用戶c進行降序排序.第一次迭代時僅利用屬性特征計算動態(tài)匹配分數(shù).在迭代過程中，根據(jù)候選用戶動態(tài)匹配分數(shù)與C中所有候選人動態(tài)匹配分數(shù)總和的比值將s個預算按候選用戶排序分配給候選用戶以獲取其鄰居信息，直到用完s個預算.利用動態(tài)評分函數(shù)根據(jù)所獲取鄰居信息更新候選用戶c和v的動態(tài)匹配分數(shù)，實現(xiàn)迭代爬蟲.動態(tài)爬蟲策略流程如算法1所示.

算法1.動態(tài)爬蟲策略DYN(v，C，E)

輸入：待識別用戶v，候選用戶集合C，API預算E，每輪迭代分配API總數(shù)s，e=0

輸出：更新后的候選用戶集合C中用戶c的鄰居信息

1.whilee

2. ife=0 do //開始第一次爬蟲迭代之前

3. 僅通過屬性特征計算動態(tài)匹配分數(shù)c.score

4. 根據(jù)c.score對C中候選用戶c進行降序排序

5. whiles≠0 do

6. 按照評分排序依次讀取C中候選用戶c的信息

7. 計算所有候選用戶動態(tài)評分總和sum

9. 對候選用戶c調(diào)用n個API獲取鄰居信息

10.e=e+n

11.c.score=MATCH_DYN(v，c)

12.end while

13.end while

5 跨社交網(wǎng)絡在線用戶識別

本文的跨社交網(wǎng)絡用戶在線識別流程如算法2所示.給定源網(wǎng)絡Gs中待識別用戶v及其在目標網(wǎng)絡Gt中的候選用戶集合C，利用預算E根據(jù)動態(tài)爬蟲策略DYN(v，C，E)獲取候選用戶鄰居信息以提取局部結(jié)構(gòu)特征.在動態(tài)爬蟲結(jié)束后，將屬性特征和局部結(jié)構(gòu)特征組成特征向量輸入用戶識別模型的函數(shù)MATCH(v，c)中得到候選用戶c與v的匹配分數(shù)，與v匹配分數(shù)最大的候選用戶即為v在目標網(wǎng)絡中的最佳映射v′.最后，將最佳映射v′對應的匹配分數(shù)與閾值λ比較，若用戶對(v，v′)的匹配分數(shù)超過閾值λ，則返回“用戶v與v′屬于同一自然人”，否則返回“(v，v′)屬于不同自然人”的結(jié)果.

算法2.跨社交網(wǎng)絡用戶在線識別

輸入：Gs中待識別用戶v及其候選用戶集合C，API預算E

輸出：v在Gt中的匹配結(jié)果

1.Fm←v.friends//v的好友信息

2.Fn←v.followers//v的跟隨者信息

3.v←{vp，F(xiàn)m，F(xiàn)n} //vp為v的屬性信息

4.C←DYN(v，C，E) //獲取候選用戶鄰居信息

5.//cp、FM和FN分別為c的簡檔、好友和跟隨者信息

6.c(c∈C)←{cp，F(xiàn)M，F(xiàn)N}

7.c.score=MATCH(v，c) //c與v的匹配分數(shù)

8.v′←argmaxc∈Cc.score//v′為匹配分數(shù)最高的c

9.ifv′.score≥λthen

10. return“(v，v′)屬于同一自然人″

11.else

12. return“(v，v′)屬于不同自然人″

6 實驗部分

6.1 數(shù)據(jù)集與實驗設計

在本文的實驗中，設置知乎為源網(wǎng)絡，新浪微博為目標網(wǎng)絡.通過網(wǎng)絡爬蟲得到40萬微博用戶和37萬知乎用戶的信息，并對爬取到的信息進行篩選和人工識別，得到31273對屬于同一自然人的知乎與微博關聯(lián)用戶，并將這些用戶對標注為正樣本，其標簽為1.同時，在剩余的數(shù)據(jù)中，設定隨機選擇的兩個非關聯(lián)用戶為負樣本，其標簽為0.本文通過簡單抽樣法將正樣本按照6∶2∶2劃分，并根據(jù)不同的方案搭配負樣本組成訓練集和測試集，如表2所示.

表2 實驗數(shù)據(jù)集

本文先通過訓練集對邏輯回歸模型進行訓練得到權重向量θ以構(gòu)造用戶識別模型和動態(tài)評分函數(shù)，然后使用測試集對爬蟲策略DYN和MCUOR方法進行評估.新浪微博的用戶可能獲取的好友信息可以通過調(diào)用一個API得到，因此本文僅對獲取用戶跟隨者列表的API設置爬蟲策略.根據(jù)實際情況分析，本文設置每單位預算包含40個獲取用戶跟隨者列表的API.實驗設計如表3所示.

表3 實驗設置

6.2 評價指標

本文采用標準的評價指標，即precision，recall，F(xiàn)1-measure進行對所提出的方法進行評估.

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

根據(jù)6.1節(jié)的實驗設計進行實驗，實驗結(jié)果如下文.

6.3.1 迭代API預算s取值分析

圖5為s的不同取值對用戶識別的召回率、精確度和F1的影響，如圖4所示，三者變化趨勢一致.隨著s的增大，召回率、精確度和F1同時增加，并在s=8時，取得最大值.當s繼續(xù)增大，數(shù)值反而下降.根據(jù)現(xiàn)實情況分析，出現(xiàn)這一情況是由于每一次迭代分配的API總數(shù)過多會出現(xiàn)將部分API分配給匹配度較低的候選用戶的情況，導致API資源的浪費.因此，當s取8時，能得到最好的用戶識別效果，即smax=8.

圖5 s取值對實驗結(jié)果的影響

6.3.2 閾值λ取值分析

圖6為根據(jù)表3的參數(shù)設置進行實驗2得到的結(jié)果.如圖6所示，隨著閾值不斷增大，precision不斷增大，recall始終保持下降的趨勢.從圖6中可以看出，在范圍[0.25，0.6]中，F(xiàn)1呈上升趨勢，在(0.6，0.7]的范圍內(nèi)閾值λ愈大F1反而更小.當λ=0.6時，取得F1的最大值，此時precision=88.75%，recall=55.04%.在跨社交網(wǎng)絡用戶識別的過程中應在保證召回率的情況下，盡量提高精確度，F(xiàn)1是兩者的綜合結(jié)果.因此，λ=0.6時實驗得到最佳效果，即λmax=0.6.

圖6 閾值取值對實驗結(jié)果的影響

6.3.3 爬蟲策略分析

根據(jù)表3的參數(shù)設置進行實驗4對DYN爬蟲策略與文獻[9]中提出的爬蟲策略TOP進行比較.圖7和圖8為根據(jù)本文的用戶識別方法利用DYN和TOP所爬取結(jié)構(gòu)信息得到的用戶識別結(jié)果.如圖7所示，隨著預算E的增加，通過DYN和TOP策略得到的用戶識別精確度均在不斷增加，且在預算數(shù)量為16的時候增長趨于平緩.在相同預算下，通過DYN策略得到的precision始終高于TOP.并且，在預算數(shù)為8時，DYN的精度達到88.6%，而TOP在預算數(shù)為20時才達到88.69%.可見在相同精度要求下，TOP花費的預算是DYN的兩倍多.

圖7 爬蟲策略的precision比較

如圖8所示，隨著預算E的增加，TOP和DYN對應的re-call與F1也隨之增加，且DYN對應的recall與F1始終高于TOP.綜上所述，DYN策略的爬蟲效果優(yōu)于TOP策略，通過DYN策略爬取到的結(jié)構(gòu)信息可以得到更好的用戶識別結(jié)果.

圖8 爬蟲策略的recall和F1-measure比較

6.3.4 算法整體性能分析

本文將提出的方法與文獻[6]和文獻[9]中提出的方法進行對比實驗，并且基于本文提出的方法考慮了僅利用簡檔信息、僅利用結(jié)構(gòu)信息和結(jié)合了兩者進行匹配的情況.

1)TOP：文獻[9]提出的通過計算跟隨者重疊度提取結(jié)構(gòu)特征，并結(jié)合簡檔特征進行用戶識別的方法.

2)IAUE：文獻[6]提出的利用結(jié)構(gòu)信息將社交網(wǎng)絡表征為低維的向量空間，并通過神經(jīng)網(wǎng)絡得到源網(wǎng)絡用戶在目標網(wǎng)絡的映射集合，最后通過G-S算法進行穩(wěn)定匹配的模型.

3)MCUOR-P：基于本文提出的屬性特征提取方法，僅利用屬性特征計算用戶的相似度以進行跨社交網(wǎng)絡的用戶識別.

4)MCUOR-S：通過本文提出的局部結(jié)構(gòu)特征提取方法僅利用結(jié)構(gòu)特征對跨社交網(wǎng)絡用戶進行識別.

5)MCUOR：本文提出的結(jié)合屬性特征和局部結(jié)構(gòu)特征的跨社交網(wǎng)絡用戶識別方法.

圖9為根據(jù)表4中實驗4的參數(shù)設置對以上方法進行實驗的結(jié)果.從圖9中可知，本文提出的MCUOR方法在3個評價指標下均優(yōu)于IAUE和TOP.另外，通過MCUOR-S和MCUOR-P的實驗結(jié)果可以看出，僅基于屬性特征和局部結(jié)構(gòu)特征進行用戶識別，其結(jié)果表現(xiàn)遠不如結(jié)合兩者的識別結(jié)果.實驗結(jié)果表明，本文的跨社交網(wǎng)絡用戶在線識別方法MCUOR有效地提高了用戶識別精確度和召回率.

表4 分類結(jié)果混淆矩陣

圖9 方法性能比較

7 總結(jié)和未來工作

為解決近幾年出現(xiàn)的社交網(wǎng)絡獲取結(jié)構(gòu)的API的訪問限制問題，本文設計了爬蟲策略DYN優(yōu)質(zhì)地調(diào)配API以迭代獲取結(jié)構(gòu)信息，并通過用戶識別模型結(jié)合屬性特征和局部結(jié)構(gòu)特征對跨社交網(wǎng)絡的用戶進行在線識別.通過真實數(shù)據(jù)集進行訓練和測試得到的實驗結(jié)果表明，與TOP相比，相同預算條件下，DYN策略可以獲得更多有效的結(jié)構(gòu)數(shù)據(jù).本文提出的跨社交網(wǎng)絡用戶識別方法整體表現(xiàn)優(yōu)于其他方法，能夠得到更高的用戶識別的精確度和召回率.在未來可考慮利用本文中通過微博語料庫訓練得到的詞向量模型從用戶所發(fā)內(nèi)容中提取用戶內(nèi)容特征，并結(jié)合用戶識別模型進一步提高用戶身份識別的精準度.