劉璟　劉挺

摘要：隨著各種在線社區(qū)呈現(xiàn)出爆炸性的發(fā)展，網(wǎng)絡(luò)中已經(jīng)積累了大量的用戶信息，這些用戶信息已經(jīng)成為了社會計算相關(guān)研究和應(yīng)用的寶貴的數(shù)據(jù)資源。由于各種社區(qū)在功能和主題上的不同，用戶的信息碎片化地散布在不同的社區(qū)中，這為獲取用戶完整信息以及跨社區(qū)的研究等都帶來了挑戰(zhàn)。用戶鏈指技術(shù)是解決用戶信息跨社區(qū)問題的關(guān)鍵。本文分析和總結(jié)了近些年用戶鏈指技術(shù)相關(guān)的研究與工作，剖析了各個工作的優(yōu)勢和局限，并對其它領(lǐng)域的相關(guān)研究進(jìn)一步作了綜合的分類與比較。

關(guān)鍵詞：跨社區(qū)； 用戶鏈指； 用戶信息

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A文章編號：2095-2163（2014）04-0039-04

Abstract：With the development of various online communities， there is a huge amount of user information cumulated on the web. The user information is the basis for the research and applications of social science. Since different communities are various in terms of functions and topics， all different aspects of user information are distributed in different communities， which makes it challenging to acquire the complete user information and conduct cross-community research. The technologies of user linking are the keys to address the cross-community problem of user information. This paper introduces the state-of-the-art user linking technologies， analyzes the advantages and limitations of each method， and conducts categorization and comparison of the related work in other research areas.

Key words：Cross-community； User Linking； User Information

0引言

近些年，互聯(lián)網(wǎng)服務(wù)正日益呈現(xiàn)社交化的態(tài)勢，各種在線社區(qū)例如論壇社區(qū)、問答社區(qū)、博客社區(qū)、微博社區(qū)等也相繼涌現(xiàn)。數(shù)量龐大的用戶群體每天都會進(jìn)入這些在線社區(qū)中發(fā)表微博和日志，提出和回答問題，分享心得體會，或者做出留言點評等等。為此，這些社區(qū)已積累了大量的用戶信息數(shù)據(jù)，為社會計算的相關(guān)研究提供了生動豐富的基礎(chǔ)海量數(shù)據(jù)。例如，Zhang等[1]和Liu等[2]分別研究了論壇和問答社區(qū)中的用戶專業(yè)水平估計問題。Gruhl等[3]則研究了微博社區(qū)和博客社區(qū)中用戶的影響力估計問題。Leskovec等[4]還研究了社區(qū)結(jié)構(gòu)的動態(tài)變化的問題。但是這些研究工作卻僅僅關(guān)注了面向單個社區(qū)的社區(qū)結(jié)構(gòu)分析和用戶計算，具體原因即在于不同社區(qū)的用戶之間往往沒有顯式的鏈接，因而使得一個社區(qū)的用戶圖與其它社區(qū)的用戶圖之間并不連通。同時，盡管每個用戶在不同的社區(qū)擁有不同的用戶信息，并且這些用戶信息在不同社區(qū)之間依然是非共享的，這也在無形中又導(dǎo)致了不同社區(qū)之間的用戶圖是相互分割、以及互不連通。

可以觀察到，由于各類在線社區(qū)在主題以及功能上的不同，用戶的各種信息都碎片化地散布在各個社區(qū)中。如圖 1所示，一個用戶在Facebook社區(qū)中的信息包含著其詳細(xì)的基本資料，包括性別、年齡、家庭住址以及朋友關(guān)系等；而該用戶在圖片社區(qū)Flickr中的信息則包含著有關(guān)的旅游經(jīng)歷；同時，該用戶在購物社區(qū)中的信息即包含了相應(yīng)的購買記錄；另外，該用戶在論壇社區(qū)中還分享著個人的興趣愛好；以及該用戶在問答社區(qū)將會求助其在家庭生活中遇到的各類問題。為保護(hù)用戶隱私，本文已對該例中的用戶進(jìn)行了匿名化處理。

Zafarani等[5]第一次提出了用戶鏈指這個問題：即將一個自然人在不同社區(qū)的用戶身份鏈接起來。用戶鏈指技術(shù)具有非常廣泛的應(yīng)用。首要地，用戶鏈指技術(shù)有助于理解不同社區(qū)之間用戶的遷移模式[6]，例如可以觀察到MySpace的哪些用戶是遷移到了Facebook的，進(jìn)而幫助社區(qū)的運(yùn)營人員有針對性地調(diào)整日常策略，以保持或增加社區(qū)的流量。同時，用戶鏈指技術(shù)還可以將一個自然人在不同社區(qū)的信息都聚合起來，形成更豐富的個人信息，從而解決推薦系統(tǒng)和個性化系統(tǒng)中的冷啟動問題[7-8]。通常情況下，如果將一個自然人在不同社區(qū)的用戶信息聚合起來，可能會暴露用戶的隱私。用戶鏈指技術(shù)可通過聚合用戶信息，并進(jìn)行自動監(jiān)測，為用戶提供一定的隱私暴露提醒服務(wù)[9]。此外，用戶鏈指技術(shù)也可以幫助建立跨社區(qū)的專家推薦系統(tǒng)，以及在跨多個社區(qū)的用戶圖上進(jìn)行用戶影響力分析。綜上，用戶信息碎片化地散布在各個不同的社區(qū)，跨社區(qū)的用戶信息為社會計算相關(guān)研究的開展帶來了很大的挑戰(zhàn)。因此，跨社區(qū)的用戶鏈指研究即顯得尤為必要，并具有高度的科技實用價值。

1主要工作介紹和分析

近幾年，用戶鏈指問題已經(jīng)引起了眾多研究人員的興趣與關(guān)注。Zafarani等[5]第一次正式提出了用戶鏈指問題，即將一個自然人在不同社區(qū)的用戶身份鏈接起來。按照模型方法，用戶鏈指的相關(guān)工作可以分為基于數(shù)據(jù)抽取的、無指導(dǎo)的和有指導(dǎo)的學(xué)習(xí)三類。本節(jié)將從這三個方面，依次介紹相關(guān)工作，并具體分析其各自優(yōu)勢和相應(yīng)局限。第4期劉璟，等：跨社區(qū)的用戶鏈指技術(shù)綜述智能計算機(jī)與應(yīng)用第4卷

1.1基于數(shù)據(jù)抽取的用戶鏈指方法

Yuan等[10]發(fā)現(xiàn)某些社區(qū)的用戶可能會在自己的個人用戶頁面（User Profile Page）中顯式地標(biāo)出自己在其他社區(qū)的個人用戶頁面的鏈接。例如，某個新浪微博用戶即在該用戶的微博個人頁面中給出了自己在豆瓣中的個人頁面的鏈接。Yuan等[10]則利用用戶的這種行為，通過人工撰寫模板的方式抽取數(shù)據(jù)，鏈指了來自4個社區(qū)的100萬左右的用戶，并進(jìn)一步在具有用戶鏈指信息的數(shù)據(jù)集合上研究了不同群組用戶的不同行為。Yuan 等[10]的用戶鏈指方法主要依賴于用戶給出的標(biāo)示信息，卻未能進(jìn)行更深入的統(tǒng)計學(xué)習(xí)，因此還無法推廣到更多的社區(qū)中。

類似地，Zafarani等[5]也發(fā)現(xiàn)了有些用戶會在自己的個人頁面中顯式標(biāo)出自己在其他社區(qū)的個人頁面的鏈接，并基于這個觀察提出了一個基于網(wǎng)頁搜索的啟發(fā)式解決方法。該方法主要基于兩個假設(shè)：

（1）一個自然人在社區(qū)A的個人頁面所對應(yīng)的網(wǎng)頁鏈接中包含了其在社區(qū)A的用戶名；

（2）該自然人在社區(qū)B的用戶個人頁面中標(biāo)示出了該自然人在社區(qū)A的用戶名。

然而，在Liu等[11]的數(shù)據(jù)集上，實驗結(jié)果已經(jīng)表明，75.47%的社區(qū)并不同時符合以上兩個假設(shè)。

1.2無指導(dǎo)的用戶鏈指方法

Vosecky等[12]提出通過收集用戶在社交網(wǎng)絡(luò)中用戶個人頁面的信息，將用戶在每個社區(qū)的個人信息表示成一個向量。向量中每一維都是一個用戶個人信息域，例如用戶名、個人描述、頭像和地點等。當(dāng)用戶個人信息向量生成后，無指導(dǎo)的和有指導(dǎo)的方法均可行之有效地進(jìn)行用戶鏈指。Vosecky等[12]使用無指導(dǎo)的方法計算每兩個用戶之間的用戶個人信息向量的相似度，若相似度大于某個預(yù)先設(shè)定的閾值，則這兩個用戶將視作屬于同一個自然人。其缺點是預(yù)先設(shè)定的相似度閾值的選取難度將會很大。

以上方法沒有對社區(qū)的類型加以限制。Iofciu等[13]研究了社會化標(biāo)簽系統(tǒng)中的用戶鏈指問題，提出了一個將用戶名編輯距離和用戶標(biāo)簽分布相似度進(jìn)行線性組合的方法。其基本假設(shè)為：

（1）一個自然人在不同社區(qū)所使用的用戶名是相同或者相近的，因此可使用編輯距離用于度量兩個用戶名的相似性；

（2）一個自然人在兩個社會化標(biāo)簽系統(tǒng)中給出的標(biāo)簽分布也應(yīng)該是接近的，因此還可使用標(biāo)簽分布相似度進(jìn)行度量。

這個方法的局限在于會依賴特定的網(wǎng)站信息，例如標(biāo)簽。同樣地，該方法還需要預(yù)先設(shè)定的閾值才能進(jìn)行判斷。而閾值的人工選取是非常困難的，相應(yīng)地不同的社區(qū)所需要的閾值也可能是不相同的。

1.3基于有指導(dǎo)學(xué)習(xí)的用戶鏈指方法

Malhotra等[8]和Nunes等[14]首先借助用戶個人頁面的信息，構(gòu)建用戶信息向量。這與Vosecky等[12]提出的構(gòu)造用戶信息向量的思想類似，但與其相區(qū)別之處卻在于，Malhotra等[8]和Nunes等[14]提出了使用標(biāo)注數(shù)據(jù)學(xué)習(xí)分類器。這些研究所獲得的實驗結(jié)果均已表明，基于有指導(dǎo)學(xué)習(xí)的方法可以達(dá)到較高的準(zhǔn)確率。然而，Narayanan等[15]又明確指出不同類型社區(qū)的用戶個人信息類型也是互不相同的。而且由于人工為每類在線社區(qū)都標(biāo)注訓(xùn)練數(shù)據(jù)很難實現(xiàn)，就使得以上有指導(dǎo)的方法也將很難擴(kuò)展到各種不同的在線社區(qū)中。

為了解決這一問題，Liu等[11] 提出了一種無指導(dǎo)的方法自動生成訓(xùn)練數(shù)據(jù)，這就使得該方法可以很容易地擴(kuò)展到任何類型的在線社區(qū)。具體地，Liu等[11] 將用戶鏈指任務(wù)分為兩步：同名消歧（Alias-disambiguation）和不同名消解（Alias-conflation）。第一步，同名消歧是指，對于一個來自不同社區(qū)的使用相同用戶名的用戶集合，需要判定該用戶集合中的用戶是否都屬于同一個自然人。換句話說，就是要對使用相同用戶名的用戶實現(xiàn)明確區(qū)分。第二步，不同名消解是指，收集一個自然人所使用的所有不同的用戶名。Liu等[11]只是關(guān)注于解決第一步同名消歧問題。文章中首先通過用戶問卷調(diào)查和基于About.me數(shù)據(jù)集的分析，量化地說明了解決同名消歧任務(wù)的重要性。其中，用戶問卷調(diào)查結(jié)果表明89.17%的人有一個主要使用的用戶名；而基于About.me的數(shù)據(jù)分析結(jié)果則表明，平均每個人使用了2.44個用戶名，解決同名消歧即可將46.8%的用戶對鏈接起來。人們傾向于將一個用戶名作為主要使用的用戶名的原因主要包括：

（1）這樣將有助于用戶減輕記憶上的負(fù)擔(dān)，因為如果每個社區(qū)都使用不同的用戶名，記憶起來將會非常地困難；

（2）同時，使用一個主要的用戶名，可以幫助用戶維護(hù)在線的聲譽(yù)，因為其他人能夠通過用戶名很輕松地對該人做出判別。

Zafarani等[16]也有與其接近的發(fā)現(xiàn)。Liu等[11] 提出的無指導(dǎo)的自動生成訓(xùn)練數(shù)據(jù)的方法，主要基于以下假設(shè)：由非常獨(dú)特的字符串構(gòu)成的用戶名通常都只為一個自然人所使用，例如：bennystar99 和travelbug61。Liu等[11]又提出使用概率語言模型來度量用戶名的獨(dú)特性。進(jìn)而，Liu等[11]將同名消歧問題看做了一個成對分類問題（pairwise classification），因此來自兩個社區(qū)、使用相同用戶名的兩個用戶將作為一個實例?；谝陨霞僭O(shè)，如果一個實例對應(yīng)的用戶名語言模型概率偏低，該實例則可以視作訓(xùn)練數(shù)據(jù)中的正例；反之，一個實例對應(yīng)的用戶名語言模型概率較高，該實例即可視作訓(xùn)練數(shù)據(jù)中的反例。Liu等[11]還利用Yahoo！ Answers的數(shù)據(jù)集驗證了該假設(shè)。實驗結(jié)果表明，在自動標(biāo)注的訓(xùn)練集上學(xué)習(xí)得到的分類器是實用有效的。Liu等[11]提出的方法雖然較好地解決了同名消歧，但卻沒能解決不同名消解的問題。

Malhotra等[8]、Vosecky等[12]和Nunes等[14]等方法的一個主要局限是依賴于用戶個人信息頁面的公開性。然而很多社區(qū)的用戶個人信息頁面都是非公開可訪問的。而Liu等[11]提出的方法僅需借助用戶生成內(nèi)容頁面（User-Generated Content）的信息，而這在大部分社區(qū)卻都是公開可訪問的。

2其它領(lǐng)域相關(guān)工作介紹和比較

2.1實體消解

用戶鏈指和其他研究領(lǐng)域的一些問題均彼此相關(guān)。而與其相關(guān)的這些問題中的一類重要研究即是實體消解，具體可分為：

（1）自然語言處理領(lǐng)域中的指代消解任務(wù)[17-18]（coreference resolution）。該任務(wù)是指將文本文檔中代表同一個實體的多個表述（mention）識別出來；

（2）數(shù)據(jù)庫領(lǐng)域中的數(shù)據(jù)記錄鏈指任務(wù)[19-20]（data record linkage）。該任務(wù)是指將來自不同數(shù)據(jù)庫的、描述同一個對象的兩條數(shù)據(jù)記錄識別出來，例如將兩個產(chǎn)品數(shù)據(jù)庫中共同描述iPhone5s的數(shù)據(jù)記錄識別出來；

（3）信息檢索領(lǐng)域中搜索結(jié)果頁面的人名消歧任務(wù)[21-22]（people name disambiguation）。該任務(wù)是指對于人名的搜索結(jié)果網(wǎng)頁，按照每個網(wǎng)頁所描述的自然人進(jìn)行聚類。以上問題均統(tǒng)稱為實體消解[20]（entity resolution）。

目前，面向這些任務(wù)的性能最優(yōu)系統(tǒng)主要采用了兩類有指導(dǎo)的方法：

（1）成對分類[17，23]；

（2）有指導(dǎo)或半指導(dǎo)的聚類[18，20，22]。在本文所關(guān)注的跨社區(qū)的用戶鏈指的任務(wù)上，基于聚類的方法并不適用。因為一個自然人通常只參與了少量的社區(qū)，例如2-3個，其所對應(yīng)圖中的簇（cluster）也就只是包含了2-3個節(jié)點，此時聚類的方法在這種圖中并不適用。因此用戶鏈指的相關(guān)工作即都選擇了基于成對分類的方法[8，11，14，16]。

2.2社交網(wǎng)絡(luò)中的反匿名化

近些年，隨著社交網(wǎng)絡(luò)的發(fā)展，越來越多的企業(yè)將其數(shù)據(jù)庫匿名化后提供給學(xué)術(shù)界與其共享，并展開相關(guān)的學(xué)術(shù)研究。但是涉及數(shù)據(jù)安全和隱私方向的研究人員卻發(fā)現(xiàn)一個匿名數(shù)據(jù)庫的用戶極有可能與一個公開數(shù)據(jù)庫中的用戶被鏈指起來，這樣用戶的個人隱私信息的安全防護(hù)就會降低[15]。研究人員將這一問題稱作社交網(wǎng)絡(luò)中的反匿名化。迄今為止，這一方向的研究成果主要可以分為兩類：

（1）統(tǒng)計意義上的稀有屬性值可以幫助在高維稀疏數(shù)據(jù)集上反匿名化[24-25]，例如一個冷門電影的觀看記錄很有可能將兩個數(shù)據(jù)庫中的用戶鏈指起來，因為一個冷門電影只可能獲得少數(shù)人的關(guān)注和觀看；

（2）Labitzkeg 等[26]和Narayanan 等[27]均發(fā)現(xiàn)僅利用社交網(wǎng)絡(luò)的結(jié)構(gòu)信息即可以成功地破解匿名網(wǎng)絡(luò)，原因在于一個自然人在兩個在線社區(qū)的朋友集合也是相似的。由此可知，社交網(wǎng)絡(luò)的結(jié)構(gòu)信息也可以有助于進(jìn)行用戶鏈指。Liu等[11]利用的也是社交網(wǎng)絡(luò)的結(jié)構(gòu)信息進(jìn)行用戶鏈指。

2.3作者識別

作者識別（Authorship Attribution）是統(tǒng)計自然語言處理領(lǐng)域的一個基礎(chǔ)課題。該課題是指通過分析文章的內(nèi)容，識別作者的寫作風(fēng)格，從而判斷一篇文章的作者。作者識別任務(wù)的一些研究成果同樣可以幫助用戶鏈指的獲取。Novak等[28]提出了使用語言模型識別論壇帖子的作者。Sanderson等[29]又研究發(fā)現(xiàn)文本的語言模型也可以助力作者識別任務(wù)的完成。同時，Gamon等[30]則發(fā)現(xiàn)詞性的語言模型也是作者識別任務(wù)的有效特征。而且，Graham 等[31]又相繼提出標(biāo)點符號的使用習(xí)慣也可以有助于作者辨別?；诖?，Rao等[32]又進(jìn)一步發(fā)現(xiàn)一些功能詞匯（例如，of、for、the 等）的使用習(xí)慣是作者識別的另外一個重要特征。作者識別任務(wù)的這些重要特征也將同樣有助于跨社區(qū)的用戶鏈指。Liu等[11]即通過分析用戶的文本內(nèi)容，相應(yīng)抽取了文本語言模型、詞性語言模型、標(biāo)點符號使用頻率分布、功能詞匯使用頻率分布等作為特征而獲得了具有較高性能的研究成果。

3結(jié)束語

用戶鏈指技術(shù)是聚合跨社區(qū)的用戶信息的基礎(chǔ)。然而，用戶鏈指技術(shù)是一個極具挑戰(zhàn)的研究問題，因為不同社區(qū)的用戶信息類型是多樣化和異構(gòu)化的，這就為無指導(dǎo)和有指導(dǎo)的方法都帶來了一定的挑戰(zhàn)。本文介紹和分析了當(dāng)前主流的用戶鏈指技術(shù)，比較了每種方法各自的優(yōu)勢和局限，并對其它領(lǐng)域的相關(guān)研究更深入地開展了綜合性的分類與比較?？梢钥吹?，結(jié)合用戶行為數(shù)據(jù)（例如用戶名等）和有指導(dǎo)學(xué)習(xí)的方法是用戶鏈指技術(shù)發(fā)展的重要方向。同時，基于用戶鏈指信息的應(yīng)用研究也存在著很大的機(jī)遇。

參考文獻(xiàn)：

[1]ZHANG J， ACKERMAN M S， ADAMIC L. Expertise networks in online communities： structure and algorithms[C]//WWW， 2007.

[2]LIU J， SONG Y I， LIN C Y. Competition-based user expertise score estimation[C]// SIGIR， 2011.

[3]GRUHL D， GUHA R， LIBEN-NOWELL D. Information diffusion through Blogspace[C]//WWW， 2004.

[4]LESKOVEC J， KLEINBERG J， FALOUTSOS C. Graphs over time： densification laws， shrinking diameters and possible explanations[C]// KDD， 2005.

[5]ZAFARANI R， LIU H. Connecting corresponding identities across communities[C]// ICWSM， 2009.

[6]KUMAR S， ZAFARANI R， LIU H. Understanding user migration patterns in social media[C]//AAAI， 2011.

[7]ABEL F， HENZE N， HERDER E. Interweaving public user profiles on the Web[C]//UMAP， 2010.

[8]MALHOTRA A， TOTTI L， MEIRA W. Studying user footprints in different online social networks[C]//ASONAM， 2012.

[9]LIU K， TERZI E. A framework for computing the privacy scores of users in online social networks[C]// TKDD， 2010.

[10]YUAN NJ， ZHANG F， LIAN D. We know how you live： exploring the spectrum of urban lifestyles[C]// COSN， 2013.

[11]LIU Jing， ZHANG Fan， SONG Xinying， et al. Whats in a name？ an unsupervised approach to link users across communities[C]//WSDM， 2013.

[12]VOSECKY J， HONG D， SHEN V. User identification across multiple social networks[C]//NDT， 2009.

[13]IOFCIU T， FANKHAUSER P， ABEL F. Identifying users across social tagging systems[C]// ICWSM， 2011.

[14]NUNES A， CALADO P， MARTINS B. Resolving user identities over social networks through supervised learning and rich similarity features[C]//SAC， 2012.

[15]NARAYANAN A， SHMATIKOV V. Myths and fallacies of personally identifiable information[C]// CACM， 2010.

[16]ZAFARANI， REZA， LIU Huan. Connecting users across social media sites： a behavioral-modeling approach[C]//KDD， 2013.

[17]SOON W M， NG H T， LIM D C Y. A machine learning approach to coreference resolution of noun phrases[C]//CL， 2001.

[18]CAI J， STRUBE M. End-to-end coreference resolution via hypergraph partitioning[C]//COLING， 2010.

[19]ELMAGARMID A K， IPEIROTIS P G， VERYKIOS V S. Duplicate record detection： a survey[C]// TKDE， 2007.

[20]BHATTACHARYA I， GETOOR L. Collective entity resolution in relational data[C]//TKDD， 2007.

[21]KALASHNIKOV D V， CHEN Z， MEHROTRA S. Web People search via connection analysis[C]// TKDE， 2008.

[22]MANN G S， YAROWSKY D. Unsupervised personal name disambiguation[C]//CONLL， 2003.

[23]BENGTSON E， ROTH D. Understanding the value of features for coreference resolution[C]//EMNLP， 2008.

[24]FRANKOWSKI D， COSLEY D， SEN S. You are what you say： privacy risks of public mentions[C]// SIGIR， 2006.

[25]NARAYANAN A， SHMATIKOV V. Robust de-anonymization of large sparse datasets[C]//S&P， 2008.

[26]LABITZKE S， TARANU I， HARTENSTEIN H. What your friends tell others about you： low cost linkability of social network profiles[C]//SNA-KDD， 2011.

[27]NARAYANAN A， SHMATIKOV V. De-anonymizing social networks[C]//S&P， 2009.

[28]NOVAK J， RAGHAVAN P， TOMKINS A. Anti-aliasing on the Web[C]//WWW， 2004.

[29]SANDERSON C， GUENTER S. Short text authorship attribution via sequence kernels， Markov chains and author unmasking： an investigation[C]//EMNLP， 2006.

[30]GAMON M. Linguistic correlates of style： authorship classification with deep linguistic analysis features[C]//COLING， 2004.

[31]GRAHAM N， HIRST G， MARTHI B. Segmenting documents by stylistic character[C]//NLE， 2005.

[32]RAO J R， ROHATGI P. Can pseudonymity really guarantee privacy？ [C]//USENIX， 2000.

[33]YOSHIDA M， IKEDA M， ONO S. Person name disambiguation by Bootstrapping[C]//SIGIR， 2010.