王李冬 胡克用 周微微 張 赟

1(杭州師范大學(xué) 浙江 杭州 310018) 2(浙江傳媒學(xué)院 浙江 杭州 310018)

0 引 言

社交網(wǎng)絡(luò)可以讓人們通過Internet進行聯(lián)系和互動，類似現(xiàn)實社會當中的社交行為，典型的如美國的Facebook、Twitter、Instagram，以及我國的人人網(wǎng)和微博。社交網(wǎng)絡(luò)提供的服務(wù)越來越豐富，從最早期的文本發(fā)布到后期的圖像與視頻共享、用戶間關(guān)注、評論等，使得越來越多的用戶會在不同的社交網(wǎng)絡(luò)上進行注冊以獲得不同的服務(wù)。

然而不同的社交網(wǎng)絡(luò)之間信息完全孤立，網(wǎng)民的不同社交網(wǎng)絡(luò)上的活動行為在不同網(wǎng)站上有不同的表現(xiàn)和側(cè)重性。例如新浪微博以媒體屬性為主，人人網(wǎng)以社交屬性為主。如果要獲得一個用戶的完整圖像，最大的困難就在于虛擬用戶賬號及其相應(yīng)的用戶行為分散在不同的社交網(wǎng)絡(luò)中[3]。對網(wǎng)民在不同社交網(wǎng)絡(luò)當中的虛擬用戶賬號進行匹配(如圖1所示)，是實現(xiàn)用戶完整圖像構(gòu)建的前提基礎(chǔ)。此外，跨社交網(wǎng)絡(luò)的用戶身份匹配對商業(yè)應(yīng)用，好友推薦，網(wǎng)絡(luò)安全，通信錄合并等有重要的意義。

圖1 身份匹配示例

目前的跨社交平臺用戶匹配技術(shù)可以大致分為基于用戶圖像的方法[4-5]，基于內(nèi)容的方法[6-7]和基于網(wǎng)絡(luò)結(jié)構(gòu)的方法[8-9]。在基于用戶圖像的方法中，Perito等[4]計算用戶名的相似度并通過二分類器進行識別。Motoyama等[5]通過計算用戶的屬性(教育、職業(yè)等)相似度進行匹配。屬性信息雖然很容易獲得，但在大型社交網(wǎng)絡(luò)中存在較大的重復(fù)性，單純依靠用戶屬性方法并無法解決大社交網(wǎng)絡(luò)的用戶匹配問題，而且多數(shù)社交網(wǎng)絡(luò)將用戶的屬性信息設(shè)定為隱私數(shù)據(jù)。在基于內(nèi)容的方法中，Kong等[6]將用戶的時間信息、空間信息和文本信息綜合起來計算相似度。Goga等[7]利用用戶的地理位置、時間戳和書寫風格進行識別。雖然基于內(nèi)容的方法具備一定的有效性，但上述的地理和空間信息在社交網(wǎng)絡(luò)中存在稀疏特性，方法難以適用大范圍社交網(wǎng)絡(luò)。在基于網(wǎng)絡(luò)結(jié)構(gòu)的方法中，Bartunov等[8]提出基于JLA(Joint Link-Attribute)的識別方法，該方法共同考慮了用戶屬性和鏈接信息。Narayanan[9]等提出完全基于鏈接屬性的識別方法。現(xiàn)有研究表明，融合用戶圖像信息、內(nèi)容信息和網(wǎng)絡(luò)信息的方法往往比單個方法的效果要好[10,12]。

本文主要研究跨社交網(wǎng)絡(luò)的局部身份匹配問題，在給定先驗種子節(jié)點集的基礎(chǔ)上，在兩個社交網(wǎng)絡(luò)中推斷出所有潛在的匹配用戶對集合?；谏鲜鏊枷?，本文提出融合鏈接信息和屬性信息的CLA(Combined Link and Attribute)算法。該算法首先通過特定的屬性信息和人工選取得到先驗種子用戶，然后利用好友親密度獲得候選用戶進行匹配。針對候選匹配用戶，通過融合鏈接信息和屬性相似度匹配準則計算得到匹配值最高的用戶作為匹配用戶，然后將匹配用戶作為種子用戶迭代運行，直到?jīng)]有新的匹配用戶產(chǎn)生。

1 CLA算法

CLA算法的目的是為了準確匹配盡可能多的用戶，算法的大致流程如圖2所示。算法首先根據(jù)用戶的用戶名、email等信息選取先驗種子用戶，再從種子用戶的好友集中選擇候選用戶進行匹配，根據(jù)屬性相似度和鏈接相似度計算匹配準則，將匹配得到的用戶作為新的種子用戶，迭代運行，直到?jīng)]有新的匹配用戶產(chǎn)生。

圖2 CLA算法流程

1.1 先驗配對用戶對選取

定義1(配對用戶對) 給定兩個社交網(wǎng)絡(luò)，分別表示為GA=(UA,EA,SA)、GB=(UB,EB,SB)。UA表示網(wǎng)絡(luò)GA的用戶實體集合，EA為網(wǎng)絡(luò)GA的用戶關(guān)系(鏈接關(guān)系)，UB表示網(wǎng)絡(luò)GB的用戶實體集合，uAi代表用戶集合UA中的第i個用戶，uBj代表用戶集合UB中的第j個用戶。SA表示網(wǎng)絡(luò)GA的用戶屬性集合，sAi代表用戶uAi屬性向量。若用戶uAi和用戶uBj在現(xiàn)實生活中屬于同一個體，則uAi和uBj被認定為配對用戶對，記為UMP。

定義2(先驗種子用戶) 先驗種子用戶是指通過特定方法找出的先驗配對用戶，由此找到更多的配對用戶對，本文記為PUMP。

目前沒有通用的方法適用于獲取任意兩個社交網(wǎng)絡(luò)的先驗種子用戶，一般需要針對特定社交網(wǎng)絡(luò)選取特定的屬性信息進行識別。Balduzzi等[1]提出利用email對用戶進行判定。由于email的唯一性，利用email進行判定是較好的方法。

此外，文獻[3]指出，同個用戶往往在不同的社交網(wǎng)絡(luò)使用同一個昵稱(nickname)。因此，若兩個社交網(wǎng)絡(luò)中用戶的用戶名完全一樣，可認定為該對用戶為同一對象，匹配用戶對。然而，部分社交網(wǎng)絡(luò)允許不同的用戶以相同用戶名進行注冊，如人人網(wǎng)。單單通過用戶名無法直接判斷兩用戶是否屬于同一人，一種簡單的解決方法就是通過其他可獲取的因素，如地理位置、生日、工作單位、性別等屬性信息進行進一步確認。此外，部分網(wǎng)絡(luò)會提供額外的信息，如twitter，該網(wǎng)絡(luò)提供獨特的URL地址用于用戶自識別，因此針對twitter的先驗配對用戶獲取可直接利用該URL與Facebook進行用戶身份識別。本文擬綜合利用Email、URl等信息的相等匹配獲得先驗種子用戶，并結(jié)合生日、工作單位、性別等屬性信息通過人工挑選對用戶進行準確性的甄別。

1.2 候選配對用戶對選取

文獻[11]對129個同時在新浪網(wǎng)和人人網(wǎng)注冊的用戶進行調(diào)研，發(fā)現(xiàn)這些用戶的好友集中有67.5%同時存在于新浪網(wǎng)和人人網(wǎng)?；诖?，本文假設(shè)：若兩個用戶相配對，則他們的好友中存在匹配用戶對的概率較大。為了選取候選配對用戶，可以從種子用戶的好友集出發(fā)。本文將候選用戶選取分為初始候選用戶選取和最終用戶選取。其中，初始候選用戶選取的規(guī)則定義如下：

定義3(初始候選用戶對) 若uAi和uBj為兩個社交網(wǎng)絡(luò)中的種子用戶，uAk∈friend(uAi)，uBl∈friend(uBj)，則(uAk,uBl)屬于初始候選用戶對CMP_P，定義為：

CMP_P= {(uAk,uBl)|uAk∈friend(uAi)∧uBl∈

friend(uBj)}

(1)

式中：uAk和uBl分別代表兩個社交網(wǎng)絡(luò)的種子用戶；friend(uAi)代表用戶uAi的好友集。

在大規(guī)模的社交網(wǎng)絡(luò)環(huán)境下，部分種子用戶的好友集數(shù)量較多。若對兩個網(wǎng)絡(luò)的種子用戶的好友集用戶進行兩兩比對，則需要耗費較長的運行時間，尤其在海量社交網(wǎng)絡(luò)的大數(shù)據(jù)環(huán)境下無法保證運行效率。為了提高匹配效果，本文通過特定的機制預(yù)先獲得在另一個網(wǎng)絡(luò)中更有可能存在匹配節(jié)點的用戶，然后將此類用戶與另一個網(wǎng)絡(luò)中的種子點用戶的好友集逐一進行匹配度計算。為了對初始候選用戶對進一步縮小范圍以提高匹配效率，我們擬利用用戶聚簇特性對某一個網(wǎng)絡(luò)中的用戶是否可能在另外一個網(wǎng)絡(luò)中存在匹配用戶進行評估。文獻[3]提出，如果一個用戶與已經(jīng)識別的用戶為好友關(guān)系且具備較高的親密度，則該用戶可以被優(yōu)先選擇。本文將好友親密度定義如下：

定義4(好友親密度(Friend Intensity，F(xiàn)I)) 若uAi和uAj代表社交網(wǎng)絡(luò)GA中的兩用戶，uAm屬于用戶uAi和uAj的共同好友。FAi、FAj和FAm分別表示用戶uAi、uAj和uAm的好友集合。好友親密度函數(shù)定義如下：

FI(uAi,uAj)=

(2)

式中，deg()代表用戶的度。

基于某用戶的所有好友親密度，我們通過用戶的好友評分對該用戶是否有可能在另外一網(wǎng)絡(luò)中存在匹配用戶進行評估。假設(shè)已經(jīng)識別的用戶集表示為umatch，本文將某用戶uAi的好友評分FC(uAi)定義如下：

(3)

若用戶uAi的FC值越大，則該用戶在另一個網(wǎng)絡(luò)中存在匹配用戶的可能性也越大?；谏鲜龆x，先將先驗種子集的朋友集設(shè)定為初始候選用戶，再根據(jù)好友親密度從初始候選用戶集中選擇特定用戶作為最終候選用戶賬號集uselect。該類用戶具備較大概率在另外一個網(wǎng)絡(luò)中存在匹配用戶，從而大大提升匹配效率。具體算法如下：

算法1候選用戶選取

輸入 社交網(wǎng)絡(luò)GA，GB，先驗種子用戶集PUMP。

輸出 候選用戶賬號集合uselect。

1 根據(jù)式(1)得到初始候選用戶對集合CMP_p={uA,uB}；

2 for eachuAi∈uA，uBj∈uB

3 根據(jù)式(3)計算FC(uAi)，F(xiàn)C(uBj)

4 end for

5 根據(jù)FC(uAi)和FC(uBj)對uA，uB的元素進行排序；

6uselect={uA[0],uA[1],uB[0],uB[1]}

1.3 用戶鏈接匹配度計算

為了實現(xiàn)兩個用戶之間的匹配，需要計算鏈接匹配度CR，現(xiàn)有的NS算法[2]通過度數(shù)計算實現(xiàn)：

(4)

式中，sin和sout分別代表用戶uAi和用戶uBj的共享入度鄰居好友和共享出度鄰居好友的數(shù)目。入度好友指社交網(wǎng)絡(luò)中好友的單向關(guān)注關(guān)系。din-Bj和dout-Bj分別代表用戶uBj的入度和出度。然而，該算法需要假設(shè)不同社交網(wǎng)絡(luò)中的同一用戶具備相同的入度和出度，該假設(shè)與現(xiàn)實世界的社交網(wǎng)絡(luò)不符。在本文方法中，我們擬引入朋友關(guān)系實現(xiàn)用戶鏈接匹配度計算。

定義5(朋友匹配度(Friend Match Degree，F(xiàn)MD))FAi和FBj分別代表用戶uAi和用戶uBj的好友集，F(xiàn)Ai∩FBj代表兩用戶的共同好友，則兩用戶的朋友匹配度定義如下：

(5)

式中：

(6)

若FAi=FBj，則FMD(uAi,uBj)=1。然而，該方法存在一個弊端，若FAi的數(shù)目較少，則會出現(xiàn)錯誤匹配的情況。如圖3所示，F(xiàn)A1=FB7={u3}，則FMD(uA1,uB7)=1，使得uA1和uB7被錯誤配對。

圖3 網(wǎng)絡(luò)對示例

為了解決式(5)帶來的錯誤匹配問題，我們加入共同好友因子進行調(diào)整，將式(5)調(diào)整如下：

(7)

|FAi∩FBj|代表已經(jīng)識別的共同好友個數(shù)，包括初始種子點。FMD(uAi,uBj)值越高，代表兩用戶為匹配用戶的概率就越大。

1.4 屬性相似度計算

用戶之間的屬性相似度擬采用用戶名、姓名、URL和Email信息。

用戶名和姓名都可表示為字符串。部分文獻采用Levenshtein距離進行度量[14]。Levenshtein距離作為計算兩個字符串間的差異程度的字符串度量，曾被多次應(yīng)用于用戶名的差異度量并取得較好的效果[11]。兩個用戶名之間的用戶名相似度計算如下：

(8)

式中：lev(n1,n2)表示用戶名n1和用戶名n2之間的Levenshtein距離；l(ni)表示ni的字符數(shù)。該方法可針對用戶名信息進行相似度度量，但針對姓名信息無法實現(xiàn)有效衡量。

姓名信息(可選)，在多數(shù)的網(wǎng)絡(luò)中都會出現(xiàn)，例如Facebook和Twitter。該信息可作為與用戶名同等重要的屬性字段進行身份匹配，但無法作為身份識別的唯一判定信息[13]。Levenshtein距離對順序較敏感，完全相同的名字，若“姓”和“名”的順序倒置，將產(chǎn)生完全不一樣的計算結(jié)果。鑒于國外社交網(wǎng)絡(luò)的姓名中，“姓”和“名”的順序并無統(tǒng)一規(guī)則，本文利用VMN算法[6]對姓名進行度量。VMN是一種非常有效的名字匹配技術(shù)，可以對姓名等信息實現(xiàn)模糊匹配，得到0或1的匹配結(jié)果值。在VMN算法中，名字“Tony Xie”和“Xie Tony”的相似度為1。

URL信息(可選)，若某社交網(wǎng)絡(luò)提供URL信息助于身份識別，則根據(jù)URL信息與相應(yīng)社交網(wǎng)絡(luò)的鏈接地址進行比對，若完全相同，則返回1，否則為0。

Email信息(可選)，若兩個用戶的Email完全相同，則該屬性相似度為1，否則為0。不同社交網(wǎng)絡(luò)上的兩用戶若具備相同的Email，則他們?yōu)橥粋€體的概率非常大。Email信息是進行身份識別的有效屬性字段。

上述信息中，姓名信息、URL信息以及Email信息需要根據(jù)特定的社交網(wǎng)絡(luò)做相應(yīng)的選擇。通過上述的屬性相似度計算可以得到用戶u1和用戶u2之間的相似度向量H(s1,s2)，s1和s2為其各自的屬相向量。將已知的匹配用戶對的屬性相似度向量作為訓(xùn)練向量，不同屬性信息的相似度作為不同的向量維度值?；诖?，用戶身份是否匹配轉(zhuǎn)化為一個二分類問題，即C(H(s1,s2))∈[0,1]，C代表分類器，1代表u1和u2為同個用戶，否則為不同用戶。本文利用SVM分類器將向量集合進行監(jiān)督學(xué)習(xí)訓(xùn)練，根據(jù)得到的SVM分類器來對新的向量進行分類。

1.5 用戶匹配準則

定義6(用戶匹配度) 給定不同社交網(wǎng)絡(luò)的兩個用戶uAi和uBj，兩者的賬號屬性向量分別為sAi和sBj。他們之間的用戶匹配度計算如下：

Mat(uAi,uBj)=C(H(sAi,sBj))×α+FMD(uAi,uBj)

(9)

式中：C(H(sAi,sBj))∈[0,1]代表用戶uAi和uBj的屬性相似度分類結(jié)果，F(xiàn)MD(uAi,uBj)代表用戶uAi和uBj的鏈接匹配度結(jié)果(見式(7))，參數(shù)α用于平衡屬性相似度和基于鏈接的用戶鏈接匹配度，本文將其定義為已經(jīng)識別出的用戶個數(shù)。

具體的匹配算法如算法2。該算法將式(1)得到的初始候選用戶對和算法1得到的候選用戶賬號集合uselect作為輸入，然后針對候選用戶賬號集合中的每一個用戶，在另一個網(wǎng)絡(luò)中的初始候選用戶對范圍內(nèi)搜索匹配用戶。若兩者之間的用戶匹配度最高，則視為配對。

算法2匹配準則計算

輸入：初始候選用戶對集合uA,uB；

候選用戶賬號集合uselect。

輸出：匹配用戶賬號umatch。

1umatch=?

2 for eachuselect(i)∈uselect

3 ifuselect(i)∈uAthen

4 for eachuBi∈uBdo

5 根據(jù)式(9)計算Mat(uselect(i),uBi)

6 end for

7umatch=umatch∪argmaxuBi∈uB(Mat(uselect(i),uBi))

8 else

9 若uselect(i)∈uB用同樣方法執(zhí)行

10 end for

2 實驗與討論

本文使用文獻[8]的Facebook和Twitter基準數(shù)據(jù)集。Facebook和Twitter基準數(shù)據(jù)集共包含16個來自Facebook和Twitter的網(wǎng)絡(luò)對。帳號的屬性信息包含用戶名、姓名和URL信息。由于在ego-network上研究，因此在樣例網(wǎng)絡(luò)中，任意兩個用戶之間的距離不會超過兩個人。數(shù)據(jù)集已經(jīng)標注兩個網(wǎng)絡(luò)中的匹配用戶對，并同時標注了種子用戶，具體相關(guān)信息如表1所示。圖4顯示了Facebook-Twitter的一個數(shù)據(jù)集示例，該數(shù)據(jù)集共10對匹配用戶，圖中標示出了5對。

表1 Facebook-Twitter數(shù)據(jù)集信息

圖4 Facebook-Twitter數(shù)據(jù)集示例

此外我們從人人網(wǎng)和新浪網(wǎng)上搜集了相應(yīng)的數(shù)據(jù)組成數(shù)據(jù)集。新浪微博數(shù)據(jù)庫是從新浪微博的搜索界面上抓取，而人人網(wǎng)的數(shù)據(jù)庫則是從其開放的API獲取。人人網(wǎng)和新浪網(wǎng)的數(shù)據(jù)如表2所示。其中，新浪爬取的用戶信息包括用戶ID、用戶名、微博數(shù)、粉絲數(shù)、關(guān)注數(shù)，以及關(guān)注關(guān)系等。人人網(wǎng)用戶信息包括用戶名，戶主的所有好友、戶主及好友關(guān)注的公共主頁等。

表2 新浪-人人數(shù)據(jù)集信息

在評價方案中，本文利用傳統(tǒng)的準確率、召回率以及F1-measure綜合進行衡量。具體如下：

recall=tp/(tp+fn)

(10)

precision=tp/(tp+fp)

(11)

(12)

式中：tp代表被正確匹配的用戶對；fp代表被錯誤匹配的用戶對，fn代表未被匹配的用戶對。

采用不同的基準算法與本文方法進行比較，分別為JLA方法[8]、NS方法[2]。算法實驗在Windows7環(huán)境下采用Matlab編寫。由于Facebook-Twitter數(shù)據(jù)集已經(jīng)具備種子用戶，則本文算法CLA在執(zhí)行過程中省略了先驗種子用戶選取的步驟。

其中，JLA方法使用監(jiān)督分類器的剪枝手段。所有方法的結(jié)果都是取16對網(wǎng)絡(luò)對的均值。由表3可得，無論從Facebook到Twitter的匹配，還是Twitter到Facebook的匹配，JLA算法可以保持最高的準確率，但是該方法的召回率并不十分理想。其中，NS方法效果最差，可見，僅僅以網(wǎng)絡(luò)拓撲為計算依據(jù)的方法遠比綜合屬性因素和鏈接關(guān)系的方法要差。CLA方法的效率和JLA相比稍顯優(yōu)越，而且JLA中基于條件隨機場的最優(yōu)用戶映射實現(xiàn)方法比CLA方法中基于判定準則的匹配方法比更加復(fù)雜，JLA方法需額外利用基于監(jiān)督分類器的剪枝操作才可獲得相對滿意的效果。若應(yīng)用于海量用戶的跨社交平臺，JLA的繁瑣步驟無法保證效率。

表3 Facebook-Twitter數(shù)據(jù)集的身份匹配效果

針對新浪-人人數(shù)據(jù)集，我們抽取四個子網(wǎng)絡(luò)進行實驗。由于獲得的用戶數(shù)據(jù)并不包含具體屬性信息，本文的CLA方法在進行匹配度計算時僅計算用戶鏈接匹配度。抽取子網(wǎng)絡(luò)時，針對兩個網(wǎng)絡(luò)中的相同用戶對進行二層好友的深度遍歷。然后，針對每個子網(wǎng)絡(luò)人工標注20個種子用戶并分別執(zhí)行CLA算法和NS算法。由于子網(wǎng)絡(luò)中的匹配用戶對的總數(shù)目未知，我們僅計算準確率進行效果分析。由表4數(shù)據(jù)可得，Sina微博抽取的子網(wǎng)絡(luò)規(guī)模約1 000節(jié)點，人人網(wǎng)抽取的子網(wǎng)絡(luò)規(guī)模約3 000節(jié)點。CLA方法和NS方法都可以獲得一定數(shù)量的匹配用戶對，但是CLA方法在所有的實驗中都保持較高的準確率。該結(jié)果表明，在僅考慮網(wǎng)絡(luò)鏈接結(jié)構(gòu)的情況下，本文提出的方法性能依然比NS方法更加優(yōu)越。

表4 新浪-人人數(shù)據(jù)集的身份匹配效果

3 結(jié) 語

本文提出一種基于CLA方法的跨社交網(wǎng)絡(luò)的身份識別，并將其應(yīng)用于真實社交網(wǎng)絡(luò)的數(shù)據(jù)集上。通過在不同數(shù)據(jù)集上的實驗，結(jié)果表明該方法可獲得較高的準確率，效果優(yōu)于傳統(tǒng)的JLA和NS方法，而且單單基于網(wǎng)絡(luò)鏈接結(jié)構(gòu)的用戶身份識別效果依然優(yōu)于NS方法。然而，CLA方法依然存在一定的不足。該方法可應(yīng)用于海量社交網(wǎng)絡(luò)群的用戶匹配，但主要還是面向兩兩社交網(wǎng)絡(luò)。若針對三個或三個以上的社交網(wǎng)絡(luò)，可能存在兩兩社交網(wǎng)絡(luò)之間的用戶匹配結(jié)果不一致的情況。因此，在今后的工作中，本文擬針對上述問題進行改進，以適應(yīng)多社交網(wǎng)絡(luò)的用戶身份匹配，同時在算法效率上擬作進一步提升。