王李冬，張 引，胡克用，張 赟

(1.杭州師范大學(xué) 錢江學(xué)院，杭州 311121；2.浙江大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州 310012 3.浙江傳媒學(xué)院，杭州 310018)

自媒體時(shí)代越來(lái)越多的用戶開始習(xí)慣在社交網(wǎng)絡(luò)(social media network，SMN)上實(shí)現(xiàn)日常的互動(dòng)和信息的獲取?，F(xiàn)今，社交網(wǎng)絡(luò)個(gè)數(shù)已達(dá)上百個(gè)，且種類繁多，典型的如校園類的人人網(wǎng)、開心網(wǎng)，學(xué)習(xí)類的知乎網(wǎng)等，綜合類的如MySpace、Twi-tter和Facebook等。人們?yōu)榱讼硎懿煌W(wǎng)站提供的服務(wù)往往需要注冊(cè)為該網(wǎng)站的用戶。普通用戶擁有多個(gè)不同社交網(wǎng)站的帳號(hào)是較普遍的情況。用戶可以在Foursquare上用手機(jī)與別人分享地理位置信息進(jìn)行交流，也可以在MySpace上交友、分享個(gè)人信息并進(jìn)行即時(shí)通訊。每個(gè)用戶若在不同的社交網(wǎng)絡(luò)注冊(cè)，會(huì)留下其個(gè)人信息(如年齡、工作單位、畢業(yè)院校等)，發(fā)表的文本內(nèi)容，發(fā)布的視頻、圖像等多媒體信息，以及在自己感興趣內(nèi)容下的評(píng)論、轉(zhuǎn)發(fā)等。對(duì)這些信息進(jìn)行整合、分析，將構(gòu)成用戶完整的個(gè)人畫像。

現(xiàn)有的社交網(wǎng)絡(luò)與社交網(wǎng)絡(luò)之間由于功能不同，因此往往是相互獨(dú)立的，而且針對(duì)同一用戶在不同網(wǎng)絡(luò)上的注冊(cè)信息缺乏有效的管理平臺(tái)進(jìn)行統(tǒng)一管理。為了分析某用戶甚至群體用戶在社交網(wǎng)絡(luò)上的行為，獲取用戶的完整圖像(profile)，需要整合用戶在不同社交網(wǎng)絡(luò)上的數(shù)據(jù)，其突破口在于跨社交平臺(tái)的用戶身份匹配，即識(shí)別用戶在多個(gè)社交網(wǎng)絡(luò)上的帳號(hào)?？缟缃黄脚_(tái)的身份匹配對(duì)商業(yè)上的信息服務(wù)推送、好友推薦以及網(wǎng)絡(luò)安全治理有重要意義。

同一用戶在不同社交網(wǎng)絡(luò)注冊(cè)時(shí)往往會(huì)填報(bào)相同或相似的屬性信息，如相同的用戶名，相同的性別、生日等信息。這些信息為跨社交網(wǎng)絡(luò)的身份匹配提供了一定的表面特征條件。但是，表面特征信息往往存在稀疏性、內(nèi)容缺失以及部分屬性與事實(shí)不符等特征，因此單純依靠表征特征會(huì)提升匹配的錯(cuò)誤率。本文主要研究跨社交網(wǎng)絡(luò)的身份匹配問(wèn)題，即給定部分已知種子用戶(同時(shí)存在于2個(gè)社交網(wǎng)絡(luò))節(jié)點(diǎn)集MPprior的基礎(chǔ)上，推斷出所有潛在的匹配用戶對(duì)集合MP。為了匹配跨社交網(wǎng)絡(luò)用戶，需要對(duì)2個(gè)網(wǎng)絡(luò)中的所有用戶一一比對(duì)。由于社交網(wǎng)絡(luò)的日益龐大，針對(duì)兩兩用戶節(jié)點(diǎn)進(jìn)行計(jì)算會(huì)消耗大量的時(shí)間。因此，本文擬通過(guò)候選用戶選擇和基于匹配因子的識(shí)別方法實(shí)現(xiàn)配對(duì)用戶對(duì)的判定，并提出融合用戶表面特征(屬性信息)和基于網(wǎng)絡(luò)嵌入的朋友匹配度作為身份匹配的匹配因子，本文將該方法命名為JFA(joint friend-attribute)。現(xiàn)有方法往往單獨(dú)采用基于表面特征的匹配技術(shù)或者基于網(wǎng)絡(luò)嵌入學(xué)習(xí)的方法，而本文對(duì)這2種方法進(jìn)行融合探討，屬于全新的一種嘗試。

1 相關(guān)工作

跨社交網(wǎng)絡(luò)用戶身份匹配方法主要包括基于社交網(wǎng)絡(luò)表面特征和基于表示學(xué)習(xí)2種方法。

1.1 社交網(wǎng)絡(luò)表面特征

該類方法主要利用用戶屬性信息或者融合用戶屬性信息和拓?fù)浣Y(jié)構(gòu)的方法實(shí)現(xiàn)跨社交平臺(tái)的身份匹配。針對(duì)前者，大部分方法計(jì)算某個(gè)特定屬性值的字符串相似度或者組合多個(gè)屬性值相似度，并通過(guò)不同的權(quán)重系數(shù)加權(quán)平均得到最終的結(jié)果，或?qū)⑵渥鳛檩斎胍杂?xùn)練二類分類器。例如，Vosecky等[1]將姓名、出生年月等屬性信息構(gòu)成用戶的特征向量，并計(jì)算用戶與用戶間的特征相似度，之后對(duì)每個(gè)相似度賦予權(quán)重計(jì)算綜合相似度。孟波等[2-3]利用監(jiān)督學(xué)習(xí)方法和提取的屬性特征構(gòu)建多個(gè)二類分類器實(shí)現(xiàn)身份識(shí)別，屬性特征包括名字特征、用戶信息特征以及拓?fù)涮卣鳌ong等[4]利用用戶的上網(wǎng)時(shí)間、地理位置、文本信息等提出MNA方法(multi-network anchoring)，構(gòu)建SVM分類器，在其基礎(chǔ)上通過(guò)交叉匹配方法提升匹配效率。針對(duì)后者，Liang等[5]通過(guò)提取用戶名、姓名等特征，并利用交叉匹配和剪枝原則實(shí)現(xiàn)用戶匹配。Bartunov等[6]利用條件隨機(jī)場(chǎng)(conditional random fields)提出聯(lián)合屬性和鏈接關(guān)系的JLA方法，通過(guò)構(gòu)建能量函數(shù)并最小化能量函數(shù)的方式得到用戶匹配，并利用監(jiān)督分類器對(duì)結(jié)果實(shí)行剪枝操作，取得良好的匹配效果。該方法適用于由于隱私保護(hù)而導(dǎo)致個(gè)人信息缺乏的狀況。Wang等[7]提出融合二元朋友、三元朋友關(guān)系以及屬性特征的概率因子圖模型PIFGM (pairwise identical factor graph model)，在部分訓(xùn)練數(shù)據(jù)集的基礎(chǔ)上預(yù)測(cè)配對(duì)用戶對(duì)。大部分的研究表明，融入鏈接關(guān)系的身份匹配效果優(yōu)越于單單依靠屬性信息的匹配效果[8]。

除上述2種方法外，也有部分研究機(jī)構(gòu)利用其他表面特征，如社交網(wǎng)絡(luò)上的頭像、朋友關(guān)系、用戶發(fā)布的文本內(nèi)容、用戶行為等進(jìn)行身份識(shí)別。例如，Goga等[9]提出了一種適用于海量用戶的身份識(shí)別方法。該方法首先利用Jaro距離方法計(jì)算用戶名字之間的相似度，利用感知哈希計(jì)算頭像相似度，利用人臉識(shí)別技術(shù)得到臉部相似度，然后根據(jù)上述特征相似度，訓(xùn)練樸素貝葉斯分類器得到匹配結(jié)果。Zhou等[10]提出基于朋友關(guān)系的用戶識(shí)別方法，為每個(gè)候選匹配用戶對(duì)計(jì)算匹配度，并通過(guò)排序的手段得到最佳匹配用戶對(duì)。Nie等[11]通過(guò)融合網(wǎng)絡(luò)結(jié)構(gòu)和用戶發(fā)布的文本內(nèi)容實(shí)現(xiàn)用戶核心興趣(core interest)建模，在其基礎(chǔ)上實(shí)現(xiàn)身份識(shí)別。Zafarani等[12]提出利用用戶行為建模的形式對(duì)不同網(wǎng)絡(luò)的用戶身份進(jìn)行匹配。此外也有研究者開始針對(duì)MOOC網(wǎng)站的用戶行為進(jìn)行分析[13]，將用戶在不同MOOC網(wǎng)站上的學(xué)習(xí)資源進(jìn)行整合。上述多數(shù)研究主要面向2個(gè)社交網(wǎng)絡(luò)的跨身份識(shí)別，Zhang等[14]為了滿足3個(gè)以上社交網(wǎng)絡(luò)用戶身份識(shí)別的局部一致性和全局一致性，提出一種全新的基于能量目標(biāo)函數(shù)的方法。

1.2 表示學(xué)習(xí)

近幾年，基于網(wǎng)絡(luò)表示學(xué)習(xí)的方法開始引起學(xué)者們的關(guān)注[15-19]。該類方法的核心思想來(lái)自于網(wǎng)絡(luò)嵌入(network embedding)，即將網(wǎng)絡(luò)嵌入到低維的特征空間，使得每個(gè)節(jié)點(diǎn)都由一個(gè)低維的特征向量表示，最后對(duì)不同網(wǎng)絡(luò)的節(jié)點(diǎn)表示學(xué)習(xí)結(jié)果進(jìn)行分析以預(yù)測(cè)是否為同一用戶節(jié)點(diǎn)[20]。例如，Wang等[15]提出LHNE(linked heterogeneous network embedding model)模型將結(jié)構(gòu)信息(朋友關(guān)系)和內(nèi)容信息(主題)融合嵌入到統(tǒng)一的特征空間。Zhang等[16]假設(shè)若2個(gè)網(wǎng)絡(luò)的用戶在各自的ego network中具備更多的相似鄰居，則他們?yōu)橥挥脩舻母怕示驮酱蟆；诖耍岢龌趫D神經(jīng)網(wǎng)絡(luò)的MEgo2Vec模型，在構(gòu)建匹配ego network的基礎(chǔ)上，通過(guò)多角度節(jié)點(diǎn)嵌入方法獲取用戶名的字面和語(yǔ)義特征，并利用注意力機(jī)制對(duì)不同鄰居用戶間的影響力建模，最后結(jié)合結(jié)構(gòu)嵌入對(duì)用戶身份進(jìn)行預(yù)測(cè)。Liu等[17-18]提出的IONE模型和PALE模型都利用結(jié)構(gòu)信息進(jìn)行用戶節(jié)點(diǎn)的表示學(xué)習(xí)并獲得嵌入向量，但沒(méi)有利用用戶的屬性特征。Shang等[19]針對(duì)表征學(xué)習(xí)模型的魯棒性提出基于對(duì)抗學(xué)習(xí)的方法，首先通過(guò)自編碼器得到網(wǎng)絡(luò)的低維嵌入空間，再引入節(jié)點(diǎn)的嵌入向量的先驗(yàn)分布，利用對(duì)抗正則化方法提升嵌入向量的魯棒性。上述基于表示學(xué)習(xí)的方法雖然取得不錯(cuò)的效果，但是網(wǎng)絡(luò)的表征學(xué)習(xí)和用戶身份的對(duì)齊尚無(wú)法結(jié)合到一個(gè)模型中。

總之，面向跨社交網(wǎng)絡(luò)的身份匹配已取得一定的研究成果，但多數(shù)方法缺乏普適性和高準(zhǔn)確率。此外，大多數(shù)基于用戶屬性的匹配手段都缺乏對(duì)屬性貢獻(xiàn)度的深入分析，而且在研究方法上很少將表面特征匹配的結(jié)果與嵌入學(xué)習(xí)模型相結(jié)合。本文擬從融合屬性特征和拓?fù)浣Y(jié)構(gòu)的角度出發(fā)，探討單個(gè)特征和多個(gè)特征對(duì)用戶匹配方法準(zhǔn)確率的影響，將表面特征匹配與網(wǎng)絡(luò)嵌入學(xué)習(xí)模型相結(jié)合提出準(zhǔn)確有效的身份匹配準(zhǔn)則。

2 JFA方法

Zhou等[10]對(duì)129個(gè)用戶(同時(shí)在新浪網(wǎng)和人人網(wǎng)注冊(cè))進(jìn)行調(diào)研，發(fā)現(xiàn)這些用戶大約有67.5%的朋友關(guān)系同時(shí)存在于新浪網(wǎng)和人人網(wǎng)?？梢?jiàn)，用戶在不同的但具備相似功能的社交網(wǎng)絡(luò)中往往具備相似的社交群。Goga等[9]發(fā)現(xiàn)很多用戶同時(shí)具備Google+、MySpace、Twitter等帳號(hào)。由此，我們可以假設(shè)：① 若給定先驗(yàn)種子用戶集，則可以根據(jù)朋友關(guān)系推斷出候選配對(duì)用戶對(duì)。② 若候選配對(duì)用戶對(duì)中具有相似的屬性信息和結(jié)構(gòu)信息(朋友關(guān)系)，則他們?yōu)橥粋€(gè)體的概率越大?；诖思僭O(shè)，我們提出融合屬性特征(如用戶名等)和拓?fù)浣Y(jié)構(gòu)(朋友匹配度)的JFA(joint friend-attribute)方法。

在講述方法前，本文先作下述定義：

定義1(配對(duì)用戶對(duì)) 給定2個(gè)社交網(wǎng)絡(luò)，分別表示為SMNA={UA，EA}，SMNB={UB，EB}。UA表示網(wǎng)絡(luò)SMNA的用戶實(shí)體集合，EA為網(wǎng)絡(luò)SMNA的用戶關(guān)系(相互關(guān)注或鏈接關(guān)系)，UB表示網(wǎng)絡(luò)SMNB的用戶實(shí)體集合，UAi代表用戶集合UA中的第i個(gè)用戶，UBj代表用戶集合UB中的第j個(gè)用戶。若用戶UAi和用戶UBj在現(xiàn)實(shí)生活中屬于同一個(gè)體，則(UAi，UBj)∈MP，MP為配對(duì)用戶集合。

定義2(先驗(yàn)種子) 社交網(wǎng)絡(luò)SMNA和社交網(wǎng)絡(luò)SMNB的先驗(yàn)種子代表已知的匹配用戶對(duì)，將先驗(yàn)種子集記為MPprior。

定義3(朋友關(guān)系) 在社交網(wǎng)絡(luò)SMNA中，若用戶UAi與用戶UAj相互關(guān)注，則用戶UAi和用戶UAj為朋友關(guān)系，記為UAj∈friend(UAi)。

提出的JFA方法框架圖如圖1所示。

圖1 JFA方法框架

該方法主要包含候選用戶對(duì)選取和匹配過(guò)程兩部分。前者主要根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)選出有較大可能成為匹配用戶對(duì)的候選用戶對(duì)。后者在候選用戶對(duì)集合中進(jìn)一步選擇，利用字符串匹配等手段計(jì)算用戶屬性匹配度，并利用網(wǎng)絡(luò)嵌入學(xué)習(xí)算法計(jì)算朋友匹配度，最后通過(guò)基于貪心優(yōu)化的判定準(zhǔn)則對(duì)匹配因子進(jìn)行比較，以得到最終匹配用戶對(duì)。上述2個(gè)過(guò)程相互迭代，直到種子用戶集為空。

2.1 候選用戶對(duì)選取

將候選用戶選取規(guī)則定義如下：

定義4(候選用戶對(duì)) 若UAi和UBj為2個(gè)社交網(wǎng)絡(luò)中的先驗(yàn)種子用戶(即代表同一用戶)，UAk∈friend(UAi)，UBl∈friend(UBj)，則(UAk，UBl)屬于候選用戶對(duì)CMP，定義為：

CMP={(UAk，UBl)

|UAk∈friend(UAi)∧UBl∈friend(UBj)∧

(UAi，UBj)∈MPprior}

(1)

其中，

friend(UAi)={UAj|(UAi，UAj)∈EA}

候選用戶對(duì)選取示例見(jiàn)圖2。圖2描述2個(gè)社交網(wǎng)絡(luò)SMNA和SMNB，2個(gè)網(wǎng)絡(luò)中的虛線表示先驗(yàn)種子點(diǎn)，即存在于2個(gè)社交網(wǎng)絡(luò)中的同一用戶。根據(jù)候選用戶選取規(guī)則，從種子點(diǎn)出發(fā)，得到(Lisa，Ben)×(Lisa，Ray，Cathy，Violet)為候選用戶對(duì)，其中，×表示笛卡兒積。

圖2 候選用戶對(duì)選取示例

2.2 匹配過(guò)程

一旦獲得候選用戶對(duì)，需要通過(guò)一定的準(zhǔn)則來(lái)判定這2個(gè)用戶是否屬于同一個(gè)體。目前沒(méi)有方法適用于任意2個(gè)社交網(wǎng)絡(luò)的配對(duì)用戶判定，一般針對(duì)特定社交網(wǎng)絡(luò)對(duì)已有方法進(jìn)行適度的修改。Balduzzi等[21]提出利用email對(duì)用戶進(jìn)行判定。由于email的唯一性，利用email進(jìn)行判定可以準(zhǔn)確的對(duì)用戶身份進(jìn)行識(shí)別，但很多社交網(wǎng)絡(luò)將email作為隱私數(shù)據(jù)。同個(gè)用戶往往在不同的社交網(wǎng)絡(luò)使用同一個(gè)昵稱(nickname)[21]。若2個(gè)社交網(wǎng)絡(luò)中用戶的用戶名一樣，可認(rèn)定為該對(duì)用戶為同一對(duì)象。但是部分社交網(wǎng)絡(luò)允許不同的用戶以相同用戶名進(jìn)行注冊(cè)，如人人網(wǎng)。單單通過(guò)用戶名無(wú)法直接判斷兩用戶是否屬于同一人，因此可通過(guò)其他可獲取的因素，如地理位置、生日、工作單位、性別等屬性信息進(jìn)行進(jìn)一步確認(rèn)。此外，部分網(wǎng)絡(luò)會(huì)提供額外的信息，如twitter網(wǎng)絡(luò)提供獨(dú)特的URL地址用于用戶識(shí)別，針對(duì)twitter網(wǎng)絡(luò)的用戶配對(duì)可直接利用該URL信息。除了上述信息外，已有研究表明融入網(wǎng)絡(luò)鏈接關(guān)系的匹配方法效果優(yōu)越于單單依靠屬性信息的匹配效果[8]。

基于上述分析，本文融合屬性匹配度和依賴鏈接結(jié)構(gòu)的朋友關(guān)系匹配度作為準(zhǔn)則判定的依據(jù)，提取用戶名、姓名、URL信息(可選)、email(可選)等屬性匹配度以及朋友匹配度等匹配因子。

2.2.1屬性匹配度

用戶名信息，表示為u，部分文獻(xiàn)采用Levenshtein距離進(jìn)行度量[22]。Levenshtein距離作為計(jì)算2個(gè)字符串間的差異程度的字符串度量，曾被多次應(yīng)用于用戶名的差異度量并取得較好的效果[23]。本文將2個(gè)用戶名U1和U2之間的用戶名相似度Simu(U1，U2)按照下式進(jìn)行計(jì)算：

(2)

式中：lev(U1，U2)表示用戶U1和U2之間的Levenshtein距離；l(ui)表示ui的字符數(shù)。

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

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

2.2.2朋友匹配度

現(xiàn)今越來(lái)越多的社交網(wǎng)絡(luò)中用戶的屬性信息存在缺失、不真實(shí)等問(wèn)題，而社交網(wǎng)絡(luò)的結(jié)構(gòu)信息顯得更加穩(wěn)定可靠。朋友匹配度主要依賴于網(wǎng)絡(luò)的鏈接結(jié)構(gòu)。在社交網(wǎng)絡(luò)中，若2個(gè)用戶之間存在鏈接關(guān)系，往往代表2個(gè)用戶之間相互關(guān)注，又或稱之為朋友關(guān)系。若2個(gè)網(wǎng)絡(luò)中的用戶具備越多的共同朋友，則他們屬于同一個(gè)體的概率越大[10]。假設(shè)F_Matchij代表朋友匹配度，文獻(xiàn)[10]將其定義為：

F_matchij=|FAi∩FBj|

(3)

式中：FAi表示用戶UAi已經(jīng)被識(shí)別的朋友集；FBj表示用戶UBj已經(jīng)被識(shí)別的朋友集；F_Matchij表示用戶UAi和用戶UBj的共同朋友個(gè)數(shù)。F_Matchij值越高，代表兩用戶越匹配，為同一個(gè)體的概率越大。然而，上式計(jì)算模型在僅僅具備部分種子點(diǎn)的情況下，無(wú)法提前獲得用戶對(duì)的共同鄰居個(gè)數(shù)。考慮到社交網(wǎng)絡(luò)的朋友關(guān)系體現(xiàn)為網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息，因此，為了獲得朋友匹配度，使用網(wǎng)絡(luò)嵌入的方法學(xué)習(xí)得到每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)嵌入向量，訓(xùn)練多層感知機(jī)(MLP)模型作為網(wǎng)絡(luò)間節(jié)點(diǎn)結(jié)構(gòu)特征向量的映射函數(shù)，再根據(jù)歐氏距離計(jì)算結(jié)構(gòu)特征向量之間的距離作為兩節(jié)點(diǎn)的朋友匹配度。具體步驟如下：

步驟1針對(duì)社交網(wǎng)絡(luò)SMNA，首先采用網(wǎng)絡(luò)嵌入的方法將每個(gè)節(jié)點(diǎn)嵌入到低維向量空間。類似文獻(xiàn)[24]的表示學(xué)習(xí)方法，本文定義2個(gè)節(jié)點(diǎn)間存在邊的概率為：

(4)

式中：zAj和zAi分別代表節(jié)點(diǎn)UAj和節(jié)點(diǎn)UAi的嵌入向量；σ(x)代表 sigmoid函數(shù)。為了學(xué)習(xí)得到嵌入向量，通過(guò)最小化以下目標(biāo)函數(shù)：

O′=-∑(UAi，UAj)∈EAlogp(UAj，UAi)

(5)

步驟2按照同樣的方法對(duì)社交網(wǎng)絡(luò)SMNB進(jìn)行嵌入學(xué)習(xí)，再綜合2個(gè)網(wǎng)絡(luò)的目標(biāo)函數(shù)得到網(wǎng)絡(luò)嵌入的最終目標(biāo)函數(shù)：

O1=-(∑(UAi，UAj)∈EAlogp(UAj，UAi)+

∑(UBi，UBj)∈EBlogp(UBj，UBi))

(6)

為了最小化目標(biāo)函數(shù)，采用隨機(jī)梯度下降法進(jìn)行求解。同時(shí)，采用負(fù)采樣方法(Negative Sampling)解決目標(biāo)函數(shù)求解過(guò)程中的耗時(shí)較大問(wèn)題。對(duì)于每條邊(UAi，UAj)，重新根據(jù)下式計(jì)算logp(UAj，UAi)：

(7)

步驟3根據(jù)種子配對(duì)用戶對(duì)的嵌入向量，學(xué)習(xí)SMNA和SMNB中節(jié)點(diǎn)的結(jié)構(gòu)特征向量之間的映射函數(shù)φ。給定zAi∈ZA，映射函數(shù)φ(zAi，θ)將向量zAi映射到空間ZB。其中，θ代表映射函數(shù)的參數(shù)集合。利用多層感知器模型構(gòu)建映射函數(shù)φ(zAi，θ)，獲得向量空間ZA到向量空間ZB的映射關(guān)系。設(shè)計(jì)的MLP模型包括輸入層、隱藏層和輸出層，隱藏層單元個(gè)數(shù)設(shè)定為2*d(d為輸入層個(gè)數(shù))。將種子配對(duì)用戶的結(jié)構(gòu)嵌入向量作為訓(xùn)練數(shù)據(jù)，對(duì)MLP模型進(jìn)行訓(xùn)練。

步驟4通過(guò)下式計(jì)算得到用戶UAi和用戶UBj的用戶匹配度：

f(F_Matchij)=||φ(zAi;θ)-zBj||2

(8)

2.2.3匹配準(zhǔn)則

將SMNA和SMNB中UA→UB的配對(duì)結(jié)果記為矩陣Y。為了簡(jiǎn)化計(jì)算，假設(shè)SMNB中僅存在1個(gè)用戶與UAi配對(duì)。若UAi和UBj配對(duì)，記為yij=1，否則yij=0。則2個(gè)社交網(wǎng)絡(luò)的局部身份配對(duì)矩陣Y滿足∑lyil≤1?UAi∈UA，∑kykj≤1?UBj∈UB。

基于此，定義以下目標(biāo)函數(shù)融合用戶的屬性和基于嵌入學(xué)習(xí)的朋友匹配度：

αf(F_Matchij))

(9)

其中，

(10)

Matcha(UAi，UBj)表示為用戶UAi和用戶UBj在匹配因子a上的匹配度。1≤k≤|K|，k表示規(guī)則使用的匹配因子個(gè)數(shù)，K表示所有的屬性匹配因子集合，|Κ|代表匹配因子總個(gè)數(shù)。式(9)中的參數(shù)α用于平衡屬性匹配值和朋友匹配度。式(10)中的wa代表匹配因子a的權(quán)重。2個(gè)網(wǎng)絡(luò)間用戶的匹配問(wèn)題就可以轉(zhuǎn)化為式(9)的目標(biāo)最大化問(wèn)題：

(11)

為了對(duì)式(9)的組合優(yōu)化問(wèn)題進(jìn)行求解，利用貪心優(yōu)化的原理，每次從候選用戶集選取配對(duì)用戶對(duì)(UAi，UBj)的過(guò)程中，使得在yij=1的條件下，obj(y)得到最大化?；诖?，定義匹配分值Mat_score，針對(duì)每一個(gè)候選用戶對(duì)中的用戶UAi，從UB中選取匹配分值最大的用戶為匹配用戶。

Mat_score(UAi,UBj)=(1-α)Rk(UAi,UBj)+

αf(F_Matchij)

(12)

2.3 JFA算法描述

根據(jù)上述流程，首先根據(jù)種子配對(duì)用戶對(duì)進(jìn)行候選用戶對(duì)選取，將該過(guò)程記為CandidateSelection(SMNA，SMNB，MPprior)，其中，MPprior代表先驗(yàn)種子用戶集。針對(duì)候選用戶對(duì)集合中的每一對(duì)用戶計(jì)算Mat_score(UAi，UBj)(見(jiàn)式(12))，以得到新的配對(duì)用戶對(duì)，以此作為新的種子用戶重新選取候選用戶對(duì)。上述過(guò)程迭代計(jì)算，具體過(guò)程如下：

Input：SMNA，SMNB，種子用戶集MPprior

Output：配對(duì)用戶集MP

1MP←?；

2Repeat

3 Randomly select a userUAm∈MPprior;

//遍歷種子用戶集中的每個(gè)種子點(diǎn)

4CMP←CandidateSelection(SMNA，SMNB，UAm)；

//CMP代表候選配對(duì)用戶對(duì)集合

5foreach(UAi，UBj)inCMPdo

6k←|K|; //初始化匹配因子個(gè)數(shù)

7 Calculate Mat_score(UAi，UBj) according to Eq.(14)；

8endfor

9 (UAi，UBj)=arg max(UAk，UBl)∈CMPMat_score(UAk，UBl)；

10MP←MP∪(UAi，UBj)；

11 ifUAiis not included inMPpriorthen

12MPprior←MPprior∪UAi；

//將匹配好的用戶作為種子用戶

13 end if

14MPprior=MPprior-UAm；

15untilMPprior=?

由上述方法可得，一旦獲得配對(duì)用戶對(duì)，則將該用戶對(duì)視作新的種子點(diǎn)(見(jiàn)算法第12行)，以重新計(jì)算得到候選配對(duì)用戶對(duì)。該方法迭代運(yùn)行，若種子集為空，則方法終止。

3 實(shí)驗(yàn)

3.1 數(shù)據(jù)集

使用3種數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證，分別為Facebook和Twitter數(shù)據(jù)集、SNS數(shù)據(jù)庫(kù)以及隨機(jī)網(wǎng)絡(luò)數(shù)據(jù)集。

1) Facebook和Twitter數(shù)據(jù)集

該數(shù)據(jù)集共包含16個(gè)來(lái)自Facebook和Twitter的網(wǎng)絡(luò)對(duì)。本數(shù)據(jù)集忽略網(wǎng)絡(luò)中的單向關(guān)注關(guān)系，保留互相關(guān)注鏈接關(guān)系。數(shù)據(jù)集已經(jīng)標(biāo)注2個(gè)網(wǎng)絡(luò)中的匹配用戶對(duì)，并同時(shí)標(biāo)注了種子用戶，具體相關(guān)信息如表1所示。圖3描述了數(shù)據(jù)集中的一個(gè)網(wǎng)絡(luò)對(duì)，該網(wǎng)絡(luò)對(duì)的種子用戶為0號(hào)用戶，且存在3對(duì)配對(duì)用戶對(duì)(紅色虛線表示)。

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

圖3 Facebook和Twitter網(wǎng)絡(luò)對(duì)示例

2) SNS數(shù)據(jù)集

SNS數(shù)據(jù)集包括當(dāng)下5種流行的社交網(wǎng)絡(luò)：Twitter、Live-Journlal、Flickr、Last.fm和Myspace，每種數(shù)據(jù)集包括了用戶的基本屬性信息，同時(shí)包含了兩兩網(wǎng)絡(luò)間用戶對(duì)應(yīng)的基準(zhǔn)數(shù)據(jù)。具體數(shù)據(jù)集信息參考https://www.aminer.cn/cosnet。

3) 隨機(jī)網(wǎng)絡(luò)數(shù)據(jù)集

隨機(jī)網(wǎng)絡(luò)數(shù)據(jù)集利用Erdos-Renyi (ER)網(wǎng)絡(luò)[25]、Watts-Strogatz(WS)網(wǎng)絡(luò)[26]和Barabasi-Albert(BA)[27]網(wǎng)絡(luò)3種網(wǎng)絡(luò)類型。圖4表示3種隨機(jī)網(wǎng)絡(luò)圖(1 000個(gè)節(jié)點(diǎn))的度分布。ER和WS網(wǎng)絡(luò)都是通過(guò)邊的隨機(jī)化重連生成，而且度概率符合正態(tài)分布，BA網(wǎng)絡(luò)的度概率符合冪律分布。

圖4 隨機(jī)網(wǎng)絡(luò)的度分布曲線圖

由于隨機(jī)網(wǎng)絡(luò)生成的節(jié)點(diǎn)無(wú)法體現(xiàn)用戶屬性等信息，因此，通過(guò)細(xì)粒化種子集在全部節(jié)點(diǎn)中的比例，分析JFA方法中的朋友匹配度因子在隨機(jī)網(wǎng)絡(luò)上的用戶匹配效果。為了在隨機(jī)網(wǎng)絡(luò)對(duì)中獲得配對(duì)用戶，首先生成較大規(guī)模的隨機(jī)網(wǎng)絡(luò)，然后按照文獻(xiàn)[28]的方法通過(guò)抽樣進(jìn)行子網(wǎng)絡(luò)提取(抽樣過(guò)程如圖5所示)，抽樣好后的網(wǎng)絡(luò)對(duì)(SMNA和SMNB)中序號(hào)相同的即為同一用戶。同時(shí)引入Jaccard系數(shù)測(cè)量生成的網(wǎng)絡(luò)對(duì)的節(jié)點(diǎn)/邊的覆蓋度。在實(shí)驗(yàn)部分，先生成1 000節(jié)點(diǎn)數(shù)的ER、WS網(wǎng)絡(luò)(每種5個(gè)網(wǎng)絡(luò))，再生成10 000節(jié)點(diǎn)的BA網(wǎng)絡(luò)，然后分別針對(duì)ER、WS和BA網(wǎng)絡(luò)生成5對(duì)網(wǎng)絡(luò)對(duì)(共15對(duì)網(wǎng)絡(luò)對(duì))，WS網(wǎng)絡(luò)和ER網(wǎng)絡(luò)中的邊隨機(jī)化重連概率p設(shè)定為0.05。在BA網(wǎng)絡(luò)中，將每次引入新節(jié)點(diǎn)時(shí)新生成的邊數(shù)m設(shè)定為20。

圖5 隨機(jī)網(wǎng)絡(luò)抽樣示例

3.2 實(shí)驗(yàn)結(jié)果

采用傳統(tǒng)的準(zhǔn)確率(precision)、召回率(recall)以及F1-measure進(jìn)行效果度量，具體如下：

recall=tp/(tp+fn)

(13)

precision=tp/(tp+fp)

(14)

(15)

式中：tp代表真陽(yáng)性，即被正確匹配的賬號(hào)對(duì)；fp代表假陽(yáng)性，即被錯(cuò)誤匹配的賬號(hào)對(duì)；fn代表假陰性，即無(wú)法被匹配出來(lái)的賬號(hào)對(duì)。

3.2.1隨機(jī)網(wǎng)絡(luò)數(shù)據(jù)集

針對(duì)隨機(jī)網(wǎng)絡(luò)數(shù)據(jù)集，匹配準(zhǔn)則中的匹配因子僅考慮朋友匹配度，并通過(guò)設(shè)定不同的種子個(gè)數(shù)，判定JFA方法的種子個(gè)數(shù)對(duì)用戶身份匹配效果的影響。需要注意的是，僅計(jì)算朋友匹配度作為匹配因子使得JFA方法演變?yōu)閱渭円蕾囃負(fù)浣Y(jié)構(gòu)的一種方法，因此本文將該方法和NS方法進(jìn)行對(duì)比實(shí)驗(yàn)，并將結(jié)果記錄于圖6和圖7中。由Narayanan等[29]提出的NS方法僅依賴于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。

圖6 JFA和NS在3個(gè)隨機(jī)網(wǎng)絡(luò)上的召回率折線圖

圖7 JFA和NS在3個(gè)隨機(jī)網(wǎng)絡(luò)上的準(zhǔn)確率折線圖

圖6表示JFA方法和NS方法在3個(gè)合成網(wǎng)絡(luò)上的召回率結(jié)果。橫坐標(biāo)表示先驗(yàn)種子集占的比例，縱坐標(biāo)代表召回率。由結(jié)果可得，當(dāng)種子集的比例升高，召回率也會(huì)相應(yīng)提升。在所有情況下，僅利用朋友匹配度的JFA方法比NS方法能夠識(shí)別出更多的配對(duì)用戶。圖7給出2種方法在3個(gè)合成網(wǎng)絡(luò)上的查準(zhǔn)率結(jié)果。橫坐標(biāo)表示種子集占的比例，縱坐標(biāo)代表召回率。在大部分情況下，隨著種子集個(gè)數(shù)的增多，查準(zhǔn)率也會(huì)相應(yīng)得到提高。針對(duì)ER和WS網(wǎng)絡(luò)，本文方法的識(shí)別準(zhǔn)確率明顯高于NS方法。針對(duì)BA網(wǎng)絡(luò)，即便在種子集比例較小的情況下，本文方法依然能體現(xiàn)較強(qiáng)的優(yōu)越性(在先驗(yàn)種子集比例為0.02的情況下，召回率達(dá)到0.735)。

3.2.2真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集

針對(duì)Facebook-Twitter數(shù)據(jù)集和SNS數(shù)據(jù)集，采用不同的基準(zhǔn)算法與本文方法進(jìn)行比較，分別為SVM、JLA(Joint Link-Attribute)[6]、NS[29]、SiGMa[30]、COSNET[14]和JFA。在SVM算法中，通過(guò)屬性相似度得到用戶UAi和用戶UBj之間的相似度向量H(SAi，SBj)，SAi和SBj為其各自的屬性向量；然后將已知匹配的用戶對(duì)的屬性相似度向量作為訓(xùn)練向量，不同屬性信息的相似度作為不同的向量維度值；基于此，用戶身份是否匹配轉(zhuǎn)化為一個(gè)二分類問(wèn)題，即C(H(SAi，SBj))∈[0，1]，C代表分類器，分類結(jié)果1代表UAi和UBj為同個(gè)用戶，否則為不同用戶。JLA方法為現(xiàn)今效果較好地實(shí)現(xiàn)局部身份匹配的常用方法，利用賬號(hào)屬性信息和網(wǎng)絡(luò)結(jié)構(gòu)，將2種信息融合到一個(gè)框架中。SiGMa方法是一種融合結(jié)構(gòu)信息和實(shí)體的屬性相似度測(cè)量的貪婪迭代算法。在具體實(shí)現(xiàn)上，將用戶名完全匹配的用戶作為種子點(diǎn)進(jìn)行擴(kuò)展，評(píng)分函數(shù)(score function)采用各個(gè)屬性相似度的加權(quán)和。JFA方法中，式(13)的平衡因子α通過(guò)實(shí)驗(yàn)經(jīng)驗(yàn)設(shè)定為0.5。COSNET方法是近幾年效果較好的一種融合屬性信息和結(jié)構(gòu)信息的匹配方法，將其應(yīng)用于SNS數(shù)據(jù)集的兩兩社交網(wǎng)絡(luò)的匹配(去除全局匹配部分)，局部屬性特征按照原文中的方法進(jìn)行提取。表2記錄了不同匹配因子的測(cè)試結(jié)果。表3給出不同方法在Facebook-Twitter數(shù)據(jù)集的16對(duì)網(wǎng)絡(luò)上的匹配效果的均值。表4記錄了不同方法在SNS數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。

表2 面向Facebook-Twitter數(shù)據(jù)集不同匹配因子下的JFA方法效果

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

表4 SNS數(shù)據(jù)集的身份匹配效果

由表2數(shù)據(jù)可以看出，不同匹配因子取得不一樣的效果。從單個(gè)匹配因子來(lái)看，姓名和用戶名比朋友匹配度方法的準(zhǔn)確率要高，而且能獲得更高的召回率。朋友匹配度在該數(shù)據(jù)集上效果不佳，主要是由于該數(shù)據(jù)集中配對(duì)用戶對(duì)的個(gè)數(shù)較少，且部分網(wǎng)絡(luò)的結(jié)構(gòu)信息差異較大。基于用戶名的效果比基于姓名的效果好，主要源于部分用戶在網(wǎng)絡(luò)上填寫的姓名存在一定的不真實(shí)性?？偟膩?lái)說(shuō)，高級(jí)別判定準(zhǔn)則的匹配效果比較低級(jí)別的匹配效果好，尤其是查全率得到一定的提升，F(xiàn)1值也得到提升。如大部分R2判定準(zhǔn)則的匹配效果比R1判定準(zhǔn)則效果好。由此可見(jiàn)，特定的匹配因子組合可有效提升跨社交平臺(tái)用戶身份匹配的效果。

表3記錄了從Facebook到Twitter的匹配和Twitter到Facebook的匹配結(jié)果的均值。 其中，JLA方法使用監(jiān)督分類器的剪枝手段，所有方法的結(jié)果都是無(wú)種子用戶存在的情況下取16對(duì)網(wǎng)絡(luò)對(duì)的均值。由表3結(jié)果可得，雖然JLA方法能得到最高的準(zhǔn)確率，然而該方法的召回率并不十分理想。僅僅以網(wǎng)絡(luò)拓?fù)錇橛?jì)算依據(jù)的NS方法效果比綜合屬性因素和鏈接關(guān)系的JFA方法要差。JFA方法的效果不僅比JLA優(yōu)越，而且JFA方法中基于判定準(zhǔn)則的匹配方法比JLA中基于條件隨機(jī)場(chǎng)的最優(yōu)用戶映射實(shí)現(xiàn)更加簡(jiǎn)單，JLA方法需額外利用基于監(jiān)督分類器的剪枝操作才可獲得相對(duì)滿意的效果，這樣的步驟使得該方法無(wú)法直接適用于海量用戶的跨社交平臺(tái)應(yīng)用。

表4記錄SNS數(shù)據(jù)集中每對(duì)網(wǎng)絡(luò)的匹配效果。針對(duì)每對(duì)網(wǎng)絡(luò)，JFA算法的效果遠(yuǎn)比SVM、SiGma以及NS算法和JLA算法效果好，且在大部分的數(shù)據(jù)集上，效果優(yōu)越于COSNET。與JLA方法類似，SiGMa針對(duì)2種數(shù)據(jù)庫(kù)都可以獲得高于90%的準(zhǔn)確率，但是卻獲得較低的召回率。在與COSNET的比較中，COSNET對(duì)部分?jǐn)?shù)據(jù)集的查全率并不理想(如Flickr-MySpace，Last.fm-MySpace等)，但本文算法針對(duì)大部分?jǐn)?shù)據(jù)集查全率有所提升。綜合表3和表4數(shù)據(jù)可得，針對(duì)真實(shí)網(wǎng)絡(luò)，本文方法優(yōu)越于基于拓?fù)浣Y(jié)構(gòu)的NS方法和基于屬性信息的SVM傳統(tǒng)方法，同樣比融合拓?fù)浣Y(jié)構(gòu)和屬性信息的JLA和SiGMa方法效果優(yōu)越。

4 結(jié)論

提出一種基于JFA方法的跨社交平臺(tái)身份匹配，并將其應(yīng)用于隨機(jī)網(wǎng)絡(luò)和真實(shí)社交網(wǎng)絡(luò)的數(shù)據(jù)集上。首次通過(guò)表面特征與嵌入學(xué)習(xí)相結(jié)合的方式進(jìn)行匹配，并選擇不同的匹配因子進(jìn)行實(shí)驗(yàn)，結(jié)果表明：該方法在綜合多個(gè)匹配因子的條件下可取得較高的準(zhǔn)確率，效果優(yōu)于傳統(tǒng)的JLA、NS、SiGMa、COSNET等方法，而且單單基于朋友匹配度匹配因子的匹配效果依然優(yōu)于傳統(tǒng)方法。今后的工作主要針對(duì)3個(gè)或3個(gè)以上的社交網(wǎng)絡(luò)群，研究解決兩兩網(wǎng)絡(luò)之間匹配結(jié)果不一致的情況。目前針對(duì)跨社交平臺(tái)用戶匹配的研究缺乏權(quán)威有效的基準(zhǔn)數(shù)據(jù)集。