采用用戶名相似度傳播模型的線上用戶身份屬性關(guān)聯(lián)方法

劉兆麗,秦濤,管曉宏,2,趙丹,楊濤

(1.西安交通大學(xué)智能網(wǎng)絡(luò)與網(wǎng)絡(luò)安全教育部重點(diǎn)實(shí)驗(yàn)室, 710049, 西安;2.清華大學(xué)智能與網(wǎng)絡(luò)化系統(tǒng)研究中心, 100084, 北京;3.西北工業(yè)大學(xué)自動(dòng)化學(xué)院, 710072, 西安)

S(S1,S2)=[(|{}|+

|{}%

?

采用用戶名相似度傳播模型的線上用戶身份屬性關(guān)聯(lián)方法

劉兆麗1,秦濤1,管曉宏1,2,趙丹1,楊濤3

(1.西安交通大學(xué)智能網(wǎng)絡(luò)與網(wǎng)絡(luò)安全教育部重點(diǎn)實(shí)驗(yàn)室, 710049, 西安;2.清華大學(xué)智能與網(wǎng)絡(luò)化系統(tǒng)研究中心, 100084, 北京;3.西北工業(yè)大學(xué)自動(dòng)化學(xué)院, 710072, 西安)

針對(duì)用戶跨線上行為復(fù)雜多樣難以融合監(jiān)控的問(wèn)題,提出了基于用戶名相似度傳播模型的線上用戶身份屬性關(guān)聯(lián)方法。結(jié)合中文社交網(wǎng)絡(luò)中用戶名的特征,將用戶名中的中英文字符進(jìn)行分離,并采用貪婪算法分別求取不同用戶名之間的中英文字符串的最大公共子串,以此實(shí)現(xiàn)含中英文字符的用戶名相似度的計(jì)算;結(jié)合用戶線上的好友結(jié)構(gòu)網(wǎng)絡(luò),僅利用一階鄰居的用戶名相似度求解用戶對(duì)的匹配度,由此不但實(shí)現(xiàn)了用戶名相似度沿網(wǎng)絡(luò)結(jié)構(gòu)的快速傳播,也大幅度地降低了匹配算法的計(jì)算復(fù)雜度。結(jié)合所收集的新浪微博和人人網(wǎng)中用戶身份屬性數(shù)據(jù)的實(shí)驗(yàn)結(jié)果表明:新提出的字符串匹配算法將用戶名匹配準(zhǔn)確率提升了近30%,傳播模型也大幅度地減少了用戶名匹配的計(jì)算量,分析結(jié)果不但可以實(shí)現(xiàn)用戶跨線上應(yīng)用行為的關(guān)聯(lián)融合,也對(duì)網(wǎng)絡(luò)輿論控制和行為監(jiān)管具有重要的參考價(jià)值。

線上應(yīng)用;屬性關(guān)聯(lián)分析;用戶名相似;特征傳播

多種多樣的線上應(yīng)用極大地豐富了人們的生活,人們通過(guò)這些線上應(yīng)用獲取所需的信息、分享個(gè)人觀點(diǎn)、發(fā)表個(gè)人言論、共享生活心得。大量的線上應(yīng)用在豐富了人們?nèi)粘Ｉ畹耐瑫r(shí),也給謠言、暴恐等信息的快速傳播提供了溫床。越來(lái)越多的恐怖和極端組織利用網(wǎng)絡(luò)來(lái)傳播他們的信仰言論,給社會(huì)安全帶來(lái)了嚴(yán)重的威脅。用戶在線上應(yīng)用中發(fā)表各種言論所使用的ID是虛擬的身份屬性,對(duì)這些虛擬的身份屬性進(jìn)行關(guān)聯(lián)融合分析,并實(shí)現(xiàn)虛擬身份到物理人的映射,可為線上應(yīng)用中輿論的安全監(jiān)管提供豐富的信息。

自網(wǎng)絡(luò)被廣泛使用以來(lái),針對(duì)網(wǎng)絡(luò)用戶行為分析的研究得到大量的關(guān)注。文獻(xiàn)[1]研究了論壇中的線上用戶多賬號(hào)的關(guān)聯(lián),提出了4種匹配方法:基于字符串的匹配、基于書寫習(xí)慣的匹配、基于發(fā)帖時(shí)間的匹配和基于社交網(wǎng)絡(luò)結(jié)構(gòu)的匹配。文獻(xiàn)[2]提出采用語(yǔ)義分析的身份屬性關(guān)聯(lián)方法,不利用字符串的相似性實(shí)現(xiàn)身份屬性的關(guān)聯(lián)。文獻(xiàn)[3]提出了從Web頁(yè)面中提取用戶的身份屬性并將之應(yīng)用于罪犯的追蹤。在前期的研究工作中,作者提出了基于用戶行為特征的身份屬性關(guān)聯(lián)方法,利用身份屬性和IP地址的組合信息實(shí)現(xiàn)身份屬性的關(guān)聯(lián)[4]。可見(jiàn),目前大多數(shù)分析方法通常僅選擇用戶節(jié)點(diǎn)信息或者網(wǎng)絡(luò)結(jié)構(gòu)信息其中之一進(jìn)行身份屬性關(guān)聯(lián),由于當(dāng)前的網(wǎng)絡(luò)應(yīng)用中用戶的身份屬性信息有數(shù)千萬(wàn)條,如果僅僅通過(guò)分析節(jié)點(diǎn)信息的相似度,計(jì)算復(fù)雜度將大幅度提高,而如果僅僅采用網(wǎng)絡(luò)結(jié)構(gòu)信息而不使用節(jié)點(diǎn)信息,那么身份屬性匹配的準(zhǔn)確度將大幅度降低。

針對(duì)上述問(wèn)題,本文提出了基于用戶名相似度傳播模型的用戶身份屬性關(guān)聯(lián)方法,首先結(jié)合中文社交網(wǎng)絡(luò)中用戶名的特征,將用戶名中的中英文字符進(jìn)行分離,分別求取不同用戶名之間的中英文字符串的最大公有子串,借以實(shí)現(xiàn)用戶名相似度的計(jì)算。隨后結(jié)合用戶線上的好友結(jié)構(gòu)網(wǎng)絡(luò),僅利用一階鄰居的用戶名相似度求解用戶對(duì)的匹配度,由此不但實(shí)現(xiàn)了用戶名相似度沿網(wǎng)絡(luò)結(jié)構(gòu)的快速傳播,也大幅度地降低了匹配算法的計(jì)算復(fù)雜度。結(jié)合所收集的新浪微博和人人網(wǎng)中用戶身份屬性數(shù)據(jù)的實(shí)驗(yàn)結(jié)果表明,本文所提出的方法因綜合利用用戶節(jié)點(diǎn)和網(wǎng)絡(luò)結(jié)構(gòu)信息,在降低計(jì)算復(fù)雜度的同時(shí)大大提升了身份屬性關(guān)聯(lián)的效率。

1 用戶名相似度傳播模型

1.1 用戶身份屬性關(guān)聯(lián)建模

在線社交網(wǎng)絡(luò)中用戶之間的關(guān)系可以采用圖G(V,E)來(lái)描述,其中V為用戶的集合,E為用戶之間關(guān)系的集合。邊的構(gòu)建原則為用戶之間存在好友關(guān)系,例如在微博網(wǎng)絡(luò)中用戶u,v∈V,且用戶u關(guān)注了用戶v,則存在一條從u指向v的有向邊,即euv∈E。目前線上應(yīng)用類型很多,一個(gè)物理用戶可能同時(shí)在多個(gè)不同的線上應(yīng)用中擁有賬戶,也即是同一個(gè)物理人擁有多個(gè)線上身份屬性。線上用戶身份屬性的關(guān)聯(lián)可以定義為如何在兩個(gè)線上社交網(wǎng)絡(luò)G1(V1,E1)和G2(V2,E2)中,挖掘?qū)儆谝粋€(gè)物理人的賬號(hào),既挖掘關(guān)聯(lián)對(duì)(v1,v2),它們屬于同一個(gè)物理人并且v1∈V1,v2∈V2。

1.2 用戶名相似度問(wèn)題建模

用戶名即用戶賬號(hào),本文中稱為用戶的網(wǎng)絡(luò)身份屬性,它是由字母、漢字、數(shù)字以及一些特殊符號(hào)組成的字符串。在同一種網(wǎng)絡(luò)應(yīng)用中用戶名作為用戶的唯一身份標(biāo)識(shí),是不允許重復(fù)的。Kumar的研究表明,50%的用戶在不同的社交網(wǎng)絡(luò)中使用相同用戶名[5]。Bekkerman的研究表明,線下物理人通常會(huì)在線上社會(huì)中使用相同或相近的用戶名[6]。據(jù)此,可以使用用戶名的相似性作為多網(wǎng)絡(luò)用戶關(guān)聯(lián)的重要依據(jù)。

(1)

1.3 用戶名相似度的傳播模型

假設(shè)在所要匹配的兩個(gè)線上應(yīng)用中存在已經(jīng)確定關(guān)聯(lián)的用戶身份屬性,稱這些屬性為種子信息。種子信息是通過(guò)人工查詢獲得的同時(shí)存在于兩個(gè)社交網(wǎng)絡(luò)的賬號(hào)對(duì),利用種子信息可以增加算法的可信度。

在線上應(yīng)用中用戶有不同的好友,這些好友有可能是該用戶在物理世界中的好友,也有可能是該用戶在網(wǎng)絡(luò)世界中的好友。根據(jù)用戶的活動(dòng)規(guī)律,我們推測(cè)用戶在物理世界中的好友在不同的應(yīng)用中很可能也應(yīng)該是用戶的好友。為此,我們得到同一物理用戶在不同的應(yīng)用中的好友會(huì)存在比較多的物理匹配對(duì),并提出了結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)的用戶身份屬性關(guān)聯(lián)傳播模型。傳播模型采用基于網(wǎng)絡(luò)結(jié)構(gòu)的迭代算法,以種子集合作為初始已匹配對(duì),從種子節(jié)點(diǎn)將其攜帶的信息擴(kuò)散到其鄰居節(jié)點(diǎn),根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)依次傳播下去,最終得到兩網(wǎng)絡(luò)中相關(guān)聯(lián)的用戶。傳播模型的計(jì)算步驟可簡(jiǎn)單描述為:

步驟1 從種子集合中取出兩個(gè)已匹配的節(jié)點(diǎn),例如,如圖1所示的A點(diǎn)和B點(diǎn);

(a)網(wǎng)絡(luò)A (b)網(wǎng)絡(luò)B圖1 結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)的傳播模型

步驟2 獲取該對(duì)用戶在各自網(wǎng)絡(luò)中的鄰居節(jié)點(diǎn),例如圖1中的A1、A2、A3和B1、B2、B3,若種子集合中所有的匹配節(jié)點(diǎn)對(duì)都已經(jīng)被計(jì)算,則計(jì)算結(jié)束;

步驟3 針對(duì)步驟2獲取的兩個(gè)鄰居節(jié)點(diǎn)集合,計(jì)算所有可能匹配對(duì)的相似度,在本例中需要計(jì)算相似性的節(jié)點(diǎn)對(duì)包括(A1,B1)、(A1,B2)、(A1,B3)、(A2,B1)、(A2,B2)、(A2,B3)、(A3,B1)、(A3,B2)以及(A3,B3);

步驟4 在步驟3所計(jì)算的結(jié)果中選取滿足一定條件的匹配對(duì),同時(shí)將匹配對(duì)添至種子集合;

步驟5 返回步驟1。

2 線上行為信息收集與預(yù)處理

從2013年8月15日至2013年9月14日,我們先后采集了新浪微博中1 808 600名用戶的相關(guān)信息以及他們的好友關(guān)系網(wǎng)絡(luò),從2014年4月22日至2014年5月15日共采集了人人網(wǎng)中40 330名用戶的相關(guān)信息以及他們的好友關(guān)系網(wǎng)絡(luò)信息。

2.1 用戶噪音節(jié)點(diǎn)清除

為了提高后續(xù)關(guān)聯(lián)分析的準(zhǔn)確率,需要對(duì)現(xiàn)有數(shù)據(jù)進(jìn)行去除領(lǐng)袖節(jié)點(diǎn)以及劣質(zhì)用戶。本文將新浪微博的用戶分為5大類:名人、人氣博主、官方微博、普通用戶與劣質(zhì)用戶。名人是通過(guò)新浪實(shí)名認(rèn)證、在各行各業(yè)里面具有一定知名度的人,包括明星(例如姚晨)、在較大型的公司企業(yè)里面擔(dān)任一定職務(wù)的人(例如馬云、雷軍)等。此類人通常有較多的粉絲。人氣博主是指發(fā)表微博主題明確、內(nèi)容新鮮獨(dú)到,吸引大量用戶關(guān)注,大部分未提供個(gè)人真實(shí)信息的用戶,通常包括兩類用戶,以個(gè)人為單位的網(wǎng)絡(luò)寫手(網(wǎng)絡(luò)用語(yǔ)稱為段子手,例如回憶專用小馬甲、王思聰,行文幽默新穎)和以主題為單位而非個(gè)人的微博寫手(例如全球熱門收集、IT程序猿)。官方微博是指各行各業(yè)由相關(guān)負(fù)責(zé)人進(jìn)行主題與本單位相關(guān)微博的更新,發(fā)微博目的通常為品牌傳播、產(chǎn)品營(yíng)銷、用戶互動(dòng)、危機(jī)預(yù)防與處理等。其中包括政府機(jī)關(guān)官方微博(例如江寧公安在線)、媒體官方微博(例如華商報(bào))、企業(yè)官方微博(例如果殼網(wǎng))等。普通用戶是指使用網(wǎng)絡(luò)進(jìn)行信息發(fā)布以及信息獲取的普通網(wǎng)絡(luò)用戶。劣質(zhì)用戶是指對(duì)微博文化有著不良傳播和影響的用戶,主要指廣告用戶和僵尸粉用戶。

為了區(qū)分上述不同類型的用戶,本文提出用戶類型參數(shù)αfolk對(duì)用戶進(jìn)行分類,實(shí)現(xiàn)領(lǐng)袖節(jié)點(diǎn)、非個(gè)人用戶以及廣告或者僵尸粉用戶的排除。αfolk定義為用戶的粉絲數(shù)與關(guān)注數(shù)的比值。在數(shù)據(jù)集中選取了名人、人氣博主、廣告與僵尸節(jié)點(diǎn)各15個(gè),同時(shí)選取了普通用戶節(jié)點(diǎn)30個(gè),這些用戶的粉絲數(shù)、關(guān)注數(shù)和αfolk的平均值的統(tǒng)計(jì)結(jié)果如表1所示。其中普通用戶的粉絲數(shù)是1 785.5,雖然這個(gè)數(shù)據(jù)不具有代表性,但是它可以有效地區(qū)分名人和普通用戶。在前期的研究工作中,我們對(duì)大量普通用戶的測(cè)量分析發(fā)現(xiàn),只有10%左右的普通用戶的粉絲數(shù)大于1 000[8],但是在本文中,為了綜合考慮并實(shí)現(xiàn)普通用戶和名人的差別,我們也選擇了一些粉絲數(shù)比較多的普通用戶作為樣本數(shù)據(jù),使得普通用戶的粉絲數(shù)較多。

由表1的結(jié)果可以看出,名人節(jié)點(diǎn)等的用戶類型參數(shù)值較大,而僵尸節(jié)點(diǎn)與廣告節(jié)點(diǎn)的該值均小于0.1,而普通用戶的用戶類型參數(shù)往往大于0.3。因此,本文可使用用戶參數(shù)類型來(lái)解釋不同類型的用戶:當(dāng)αfolk在[0.3,50]區(qū)間時(shí),用戶為普通用戶節(jié)點(diǎn);當(dāng)afolk在(0,0.3)時(shí),用戶為僵尸節(jié)點(diǎn)或者廣告節(jié)點(diǎn);當(dāng)αfolk在(50,n)時(shí),用戶為名人、人氣博主等節(jié)點(diǎn),其中n為微博粉絲上限數(shù)。通過(guò)上述方法選取普通用戶節(jié)點(diǎn),在絕大多數(shù)情況下排除了名人、人氣博主與廣告、僵尸粉用戶,同時(shí)保留了活躍度高的用戶以及小有名氣的用戶。

與此同時(shí),我們利用人工標(biāo)定的方法在新浪微博和人人網(wǎng)中標(biāo)記了27對(duì)匹配節(jié)點(diǎn),它們組成了種子節(jié)點(diǎn)集合。

表1 不同類型用戶的類型參數(shù)值

2.2 用戶好友網(wǎng)絡(luò)構(gòu)建

本文定義的用戶關(guān)系網(wǎng)為用戶的好友關(guān)系,即在線下生活中相互認(rèn)識(shí)的朋友關(guān)系或者在網(wǎng)絡(luò)上成為朋友關(guān)系。在新浪微博中,用戶A關(guān)注用戶B,即A是B的粉絲,并不意味用戶A與B就是好友關(guān)系。當(dāng)兩個(gè)人同時(shí)關(guān)注了對(duì)方,即A關(guān)注B同時(shí)B也關(guān)注A,則在大部分情況下互為朋友關(guān)系,因此用戶是否相互關(guān)注可以用來(lái)判斷用戶是否存在好友關(guān)系。此外,社交關(guān)系模型的建立可以將新浪微博原有的有向用戶關(guān)系轉(zhuǎn)化為無(wú)向關(guān)系。對(duì)于人人網(wǎng),只有當(dāng)兩用戶均為對(duì)方的好友時(shí),才會(huì)在網(wǎng)頁(yè)上顯示其互為好友關(guān)系,因此人人網(wǎng)中以用戶為節(jié)點(diǎn),以好友關(guān)系為邊,所構(gòu)成的網(wǎng)絡(luò)圖為無(wú)向圖,無(wú)需對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行預(yù)處理。此外,人人網(wǎng)單個(gè)節(jié)點(diǎn)均為一個(gè)線下物理人,人人網(wǎng)中所存在的非個(gè)人賬號(hào),即公共主頁(yè),并不在好友列表中,因此無(wú)需進(jìn)行排除。

3 用戶名相似度度量方法

3.1 用戶名相似度計(jì)算方法

用戶名相似性計(jì)算可以轉(zhuǎn)化為字符串相似性計(jì)算,而字符串相似性計(jì)算方法中最為常見(jiàn)的包括編輯距離算法(Levenshtein)、最長(zhǎng)公共子序列(longest common subsequence, LCS)算法和貪心算法(greedy string tiling, GST)算法。其中編輯距離算法是由俄國(guó)科學(xué)家Levenshtein首先提出,故又稱作Levenshtein距離,編輯距離是指兩個(gè)字符串之間,由一個(gè)字符串轉(zhuǎn)換成另一個(gè)字符串所需要的最少編輯次數(shù)。一次編輯的合法操作包括:將某字符替換為另一字符,插入某字符以及刪除某字符[9]。LCS算法也是計(jì)算字符串相似度的常用算法。該算法將兩個(gè)給定的字符串分別刪除零個(gè)或者多個(gè)字符,但不改變剩余字符串的順序而得到的長(zhǎng)度最長(zhǎng)的相同子字符序列[10]。其中子序列是原字符串的子串且保持每個(gè)元素在原字符串中相對(duì)位置不變[11]。GST算法是一種貪婪算法,最早由澳大利亞悉尼大學(xué)的Michael Wise設(shè)計(jì)。該算法對(duì)兩個(gè)字符串進(jìn)行貪婪式搜索以找出最大公有子串,需要對(duì)字符串進(jìn)行多次搜索,每次找出當(dāng)前字符串中未標(biāo)記部分的最長(zhǎng)公共子串,同時(shí)將已找出的最長(zhǎng)公共子串標(biāo)記為已使用,避免最大匹配重復(fù)使用[12]。

3.2 針對(duì)中文社交網(wǎng)絡(luò)用戶名特征的相似度算法

GST算法會(huì)在以下情況中出現(xiàn)較大誤差:當(dāng)用戶名中包含較多無(wú)關(guān)信息時(shí),如特殊符號(hào)或無(wú)意義字符,算法計(jì)算的值較低;當(dāng)用戶名為繁體字時(shí),難以使用原算法進(jìn)行匹配,致使失配率增高;當(dāng)設(shè)置最短匹配長(zhǎng)度(MinMatchLength)取值較低時(shí),會(huì)造成英文字符串的匹配較多,尤其當(dāng)英文元字母較多,如“Ainne”與“Irene”,當(dāng)MinMatchLength取值為1時(shí)相似度為0.8,而當(dāng)MinMatchLength取值為3時(shí),相似度為0。然而,用戶名往往不會(huì)僅僅包含英文,多為中文或者中英文結(jié)合。為了進(jìn)一步提高算法準(zhǔn)確率,分析發(fā)現(xiàn)用戶在社交網(wǎng)絡(luò)中的用戶名存在以下特征:①社交網(wǎng)絡(luò)用戶由于其存在部分的真實(shí)線下社交特點(diǎn),有部分用戶會(huì)將自己的線下真實(shí)姓名用于用戶名之中,并多傾向于使用真實(shí)姓名作為用戶名的子序列;②用戶的用戶名中,同時(shí)包含部分與真實(shí)姓名無(wú)關(guān)的字符;③用戶中文名為姓氏與名字所構(gòu)成,姓氏最少是一個(gè)字,用戶名如果包含真實(shí)姓名,則其中最小可信單位長(zhǎng)度為1,英文作為人名時(shí),最小長(zhǎng)度為3,則可信最小單位長(zhǎng)度為3。基于以上分析,本文對(duì)字符串相似度算法GST進(jìn)行改進(jìn)。改進(jìn)后算法命名為Chinese greedy string tiling,簡(jiǎn)寫為CGST,具體步驟如下。

步驟1 排除對(duì)用戶名匹配時(shí)貢獻(xiàn)小的字符,即對(duì)兩個(gè)字符串去除數(shù)字及特殊符號(hào)字符。

步驟2 轉(zhuǎn)換字符串中繁體字為簡(jiǎn)體字。

步驟3 如果當(dāng)一個(gè)字符串包含另一個(gè)字符串,則相似度可設(shè)置為一個(gè)較高的固定值,如1.0;若不包含,則轉(zhuǎn)入步驟4。

步驟4 分別計(jì)算兩字符串的中文字符串最長(zhǎng)公共字串集合與英文字符串最長(zhǎng)公共字串集合,計(jì)算中文字符串時(shí),MinMatchLength取值為1;計(jì)算英文字符串時(shí),MinMatchLength取值為3。

步驟5 計(jì)算相似度。在獲取最長(zhǎng)公共字串集合的算法中,每次在向當(dāng)前循環(huán)中添加新的字符時(shí),需要判斷該字符是否已經(jīng)匹配過(guò),以排除重復(fù)匹配情況。

4 實(shí)驗(yàn)結(jié)果分析

4.1 相似度方法比較

將字符串相似度應(yīng)用于用戶名比較時(shí),評(píng)判算法是否合適的衡量依據(jù)主要為計(jì)算結(jié)果是否準(zhǔn)確,即能否使同一個(gè)物理用戶在兩個(gè)應(yīng)用中的用戶名計(jì)算得出的相似度值高。因此,下文中主要通過(guò)應(yīng)用算法到具體場(chǎng)景來(lái)比較3個(gè)算法的性能。在數(shù)據(jù)集中,作者標(biāo)定了27位同時(shí)使用新浪微博與人人網(wǎng)的物理用戶,作為種子。在此選取其中3位用戶將其用戶名列出,見(jiàn)表2。該表中的用戶將用于分析不同算法的準(zhǔn)確性。

表2 部分種子用戶跨應(yīng)用用戶名

采用第3節(jié)中的不同算法分別對(duì)這27個(gè)用戶的兩個(gè)用戶名進(jìn)行相似度計(jì)算,圖2展示了不同算法計(jì)算的相似度分布結(jié)果。圖中橫坐標(biāo)表示相似度,縱坐標(biāo)表示用戶數(shù),每一個(gè)點(diǎn)表示使用不同算法大于該相似度的用戶數(shù)。對(duì)于確定已匹配的用戶名對(duì),相似度越高的用戶越多表示算法準(zhǔn)確率越高。可以看出:編輯距離算法所得到的用戶名相似度多數(shù)小于0.4,占總用戶數(shù)的61.5%;LCS算法較編輯距離算法來(lái)說(shuō)結(jié)果略好一些,69.2%的用戶計(jì)算所得相似度小于0.5;GST算法相似度為0.4以上的用戶較多,占總用戶數(shù)的77%。通過(guò)計(jì)算得到,3個(gè)算法計(jì)算所得的平均相似度值分別為0.42、0.44和0.58,由此可看出GST算法在計(jì)算用戶名相似度時(shí)有較好的表現(xiàn)。對(duì)于表2中編號(hào)為2的用戶,新浪微博用戶名為“小雯雯-滕雯”,人人網(wǎng)用戶名為“滕雯”,通過(guò)編輯距離算法、LCS算法和GST算法計(jì)算的相似度差異較大,分別為0.17、0.36和0.89。編輯距離算法計(jì)算得到的值很低主要因?yàn)閮蓚€(gè)字符串長(zhǎng)度差異大,導(dǎo)致即使包含相同的字符串時(shí)也會(huì)使差異步數(shù)較大,從而計(jì)算結(jié)果不理想。LCS的結(jié)果主要由于當(dāng)存在特殊符號(hào)隔開了有意義的字符時(shí),會(huì)導(dǎo)致計(jì)算結(jié)果下降。GST算法反復(fù)計(jì)算了兩字符串的公共字串,致使這對(duì)字符串有很多匹配對(duì),因而計(jì)算結(jié)果較為理想。從算法所匹配的公共序列來(lái)看,編輯距離算法與LCS算法均屬于有序的相似度算法,而GST算法屬于無(wú)序的算法,即對(duì)于GST來(lái)說(shuō),“王小紅”與“小紅王”是完全匹配的,而對(duì)于前兩種算法無(wú)法完全匹配,這也是其算法準(zhǔn)確率較低的原因。

圖2 編輯距離、LCS及GST算法的計(jì)算結(jié)果比較

4.2 CGST算法性能分析

對(duì)種子集合中的27對(duì)用戶名采用CGST算法和GST算法的計(jì)算結(jié)果對(duì)比如圖3所示,有80.8%的用戶名對(duì)的相似度大于等于0.9,而GST算法在此區(qū)間僅有7.7%的用戶。GST算法用戶名平均相似度值為0.58,而CGST算法把結(jié)果提高為0.89。編號(hào)為3的用戶的新浪微博名與人人網(wǎng)用戶名分別為“田若靜-不美不開心”與“田若靜”,采用GST算法得到相似度值為0.5,而采用CGST則為1.0。例如“何鵬程”和“郝程程程”這個(gè)并非屬于同一個(gè)物理人的用戶名對(duì),相似度計(jì)算的結(jié)果由0.86降低為0.29。CGST算法大大提高了用戶名的區(qū)分度。本文提出的CGST算法與GST算法相比,改進(jìn)主要在于每一輪計(jì)算中會(huì)保存已經(jīng)添加的匹配對(duì),每次新檢測(cè)出的匹配對(duì)需要查詢是否已存在該匹配對(duì)。如果采用哈希表等數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ),每次查詢的時(shí)間復(fù)雜度降為O(1),因此改進(jìn)后的CGST算法并沒(méi)有增加時(shí)間復(fù)雜度。當(dāng)兩個(gè)字符串完全不相同時(shí),計(jì)算的時(shí)間復(fù)雜度為O(n2);當(dāng)每次循環(huán)中均只能找到一個(gè)最大匹配,將致使算法3個(gè)循環(huán)均要被執(zhí)行,則時(shí)間復(fù)雜度為O(n3)。但是,鑒于用戶名匹配僅僅在用戶的鄰居節(jié)點(diǎn)集合進(jìn)行,而90%以上的用戶其好友個(gè)數(shù)均小于1 000[8],因此本算法的計(jì)算復(fù)雜度并不高。

圖3 GST與CGST算法比較

4.3 傳播算法計(jì)算復(fù)雜度分析

傳播算法每一輪選取一對(duì)已匹配對(duì),在兩個(gè)網(wǎng)絡(luò)中遍歷匹配對(duì)的所有好友,該過(guò)程需要O(n2)的時(shí)耗。基于CGST的用戶名相似度計(jì)算方法的復(fù)雜度為O(n3),其中n為用戶名長(zhǎng)度,這里的n與數(shù)量級(jí)上百的遍歷好友數(shù)目相比較小,可忽略不計(jì)。傳播算法的總輪數(shù)由新匹配數(shù)來(lái)決定,而新匹配數(shù)與網(wǎng)絡(luò)規(guī)模有關(guān),當(dāng)總輪數(shù)與好友數(shù)的數(shù)量級(jí)相近時(shí),基于用戶名的傳播關(guān)聯(lián)方法的時(shí)間復(fù)雜度為O(n3),當(dāng)總輪數(shù)遠(yuǎn)遠(yuǎn)大于用戶好友數(shù)時(shí),則可忽略遍歷好友的時(shí)間,即時(shí)間復(fù)雜度為O(n),由此可見(jiàn)本文所提出的算法計(jì)算復(fù)雜度較低。此外,本文所提出的基于用戶名的傳播關(guān)聯(lián)方法,將用戶名相似性的計(jì)算與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相結(jié)合,摒棄了以往在兩個(gè)網(wǎng)絡(luò)中直接進(jìn)行用戶名相似度計(jì)算的方法,從而避免了當(dāng)數(shù)據(jù)量多時(shí)用戶名重復(fù)率高,導(dǎo)致用戶名計(jì)算結(jié)果相似或者區(qū)分率小、準(zhǔn)確率低以及計(jì)算復(fù)雜度高的問(wèn)題。

4.4 算法匹配準(zhǔn)確度分析

本文使用新浪微博37 608名用戶和人人網(wǎng)40 330名用戶及其好友關(guān)系生成的網(wǎng)絡(luò),以27名用戶作為種子節(jié)點(diǎn)進(jìn)行節(jié)點(diǎn)匹配計(jì)算,最終得到276名物理用戶的兩網(wǎng)賬號(hào)匹配對(duì),見(jiàn)表3。經(jīng)過(guò)對(duì)其中150對(duì)關(guān)聯(lián)進(jìn)行人為查詢,發(fā)現(xiàn)當(dāng)閾值選取0.75時(shí),得到的匹配準(zhǔn)確率高達(dá)96.77%。

首先,這是因?yàn)槲覀冊(cè)诓杉瘮?shù)據(jù)時(shí),新浪微博爬蟲的起始點(diǎn)和人人網(wǎng)絡(luò)爬蟲的起始點(diǎn)不是物理匹配對(duì),造成了兩個(gè)網(wǎng)絡(luò)中總體的覆蓋率不是很大,如果以種子節(jié)點(diǎn)為起始節(jié)點(diǎn),匹配率將會(huì)大幅度提升。此外,匹配結(jié)果與節(jié)點(diǎn)和種子節(jié)點(diǎn)所處的網(wǎng)絡(luò)位置有關(guān),當(dāng)節(jié)點(diǎn)處于網(wǎng)絡(luò)邊緣,則缺失節(jié)點(diǎn)結(jié)構(gòu)信息,會(huì)導(dǎo)致計(jì)算結(jié)果不佳。最后,當(dāng)網(wǎng)絡(luò)較小時(shí),處于網(wǎng)絡(luò)邊緣的節(jié)點(diǎn)數(shù)占網(wǎng)絡(luò)規(guī)模比值大,也會(huì)造成計(jì)算結(jié)果不佳。如果增加網(wǎng)絡(luò)規(guī)模或者種子節(jié)點(diǎn)的數(shù)量,那么匹配率也會(huì)得到提升。

表3 關(guān)聯(lián)方法關(guān)聯(lián)結(jié)果信息

5 結(jié) 論

線上應(yīng)用在豐富了用戶生活的同時(shí),也給網(wǎng)絡(luò)輿論安全管理帶來(lái)一定的困難,本文圍繞用戶跨線上應(yīng)用身份屬性關(guān)聯(lián)問(wèn)題開展了研究。首先,本文對(duì)所收集到的新浪微博信息和人人網(wǎng)信息進(jìn)行了預(yù)處理,清除了新浪微博中的僵尸粉等賬號(hào)。再者,根據(jù)中文社交網(wǎng)絡(luò)中用戶名的特點(diǎn),提出了基于CGST算法的用戶名相似度計(jì)算方法。最后,為了充分利用用戶節(jié)點(diǎn)的信息和網(wǎng)絡(luò)結(jié)構(gòu)方面的特征信息,本文提出了基于用戶名相似度傳播模型的身份屬性關(guān)聯(lián)方法,在大幅度降低計(jì)算復(fù)雜度的同時(shí),也有效地提升了身份屬性信息關(guān)聯(lián)的準(zhǔn)確性。結(jié)合所收集到的用戶身份屬性信息的實(shí)驗(yàn)結(jié)果表明,本文所提出的方法在計(jì)算復(fù)雜度和匹配準(zhǔn)確度方面都具有較高的性能。在下一步工作中,將綜合考慮更多的用戶身份屬性信息,進(jìn)一步提升匹配的準(zhǔn)確度。

[1] JOHANSSON F, KAATI L, SHRESTHA A. Detecting multiple aliases in social media [C]∥Proceedings of the International Conference on Advances in Social Networks Analysis and Mining. Piscataway, NJ, USA: IEEE Communication Society, 2013: 1004-1011.

[2] AN Ning, JIANG Lili, WANG Jianyong, et al. Toward detection of aliases without string similarity [J]. Information Sciences, 2014, 261(10): 89-100.

[3] ANWAR T, ABULAISH M. Namesake alias mining on the Web and its role towards suspect tracking [J]. Information Sciences, 2014, 276(20): 123-145.

[4] LIU Zhaoli, QIN Tao, GUAN Xiaohong, et al. Alias detection across multi-online applications based on user’s behavior characteristics [C]∥Proceedings of the 2015 IEEE Trustcom. Piscataway, NJ, USA: IEEE Computer Society, 2015: 1154-1159.

[5] KUMAR S, ZAFARANI R, LIU Huan. Understanding user migration patterns in social media [C]∥Proceedings of the 25th AAAI Conference on Artificial Intelligence. New York, USA: ACM, 2011: 1-6.

[6] BEKKERMAN R, MCCALLUM A. Disambiguating Web appearances of people in a social network [C]∥Proceedings of the International Conference on World Wide Web. New York, USA: ACM, 2005: 463-470.

[7] HIRSCHBERG D S. Algorithms for the longest common subsequence problem [J]. Journal of the ACM, 1977, 24(4): 664-675.

[8] WANG Chenxu, GUAN Xiaohong, QIN Tao. Who are active? an in-depth measurement on user activity characteristics in Sina Microblog [C]∥Proceedings of the 2012 IEEE Global Communications Conference. Piscataway, NJ, USA: IEEE Communication Society, 2012: 2083-2088.

[9] LEVENSHTEIN V I. Binary codes capable of correcting deletions, insertions and reversals [J]. Soviet Physics Doklady, 1965, 163(4): 845-848.

[10]AHO A V, HIRSCHBERG D S, ULLMAN J D. Bounds on the complexity of the longest common subsequence problem [J]. Journal of the ACM, 1976, 23(1): 104-109.

[11]QIN Tao, ZHAO Dan, ZHU Min, et al. Mapping different online behaviors to physical user for comprehensive knowledge-pushing services [C]∥Proceedings of the IEEE International Conference on Communications. Piscataway, NJ, USA: IEEE Communication Society, 2014: 671-675.

[12]WISE M J. String similarity via greedy string tiling and running KarpRabin matching: 463 [R]. Sydney, Australia: University of Sydney. Department of Computer Science, 1993.

(編輯 武紅江)

A Correlation Method of Online User Identity Attributes Based on a Propagation Model of Username Similarities

LIU Zhaoli1,QIN Tao1,GUAN Xiaohong1,2,ZHAO Dan1,YANG Tao3

(1. MoE Key Laboratory for Intelligent Networks and Network Security, Xi’an Jiaotong University, Xi’an 710049, China; 2. Center for Intelligent and Networked Systems, Tsinghua University, Beijing 100084, China; 3. Department of Automation, Northwestern Polytechnical University, Xi’an 710072, China)

A user identity attribute correlation method is proposed to focus on the problem that behaviors of online users are hard for fusion and supervision among multi-online applications due to their complexity and variation. The method is based on a propagation model of username similarities. The English and Chinese characters in usernames are separated by considering the characteristics of username in the Chinese social networks. A greedy algorithm is used to extract the longest common sequence between English and Chinese characters respectively for different usernames, and then username similarities are calculated. User’s online connection structure and the username similarities of their first-order neighbors are used to decide the matching degree of the selected user pairs. Hence, not only the username similarity is propagated quickly among the connection networks, but also the complexity of matching calculation is greatly reduced. Experimental results based on the datasets collected from Sina Microblog and Renren networks show that the proposed algorithm improves the matching accuracy of usernames by about 30%, and the propagation model greatly reduces the calculation complexity of username similarities. The analysis results achieve the goal of user’s behavior fusion among different online applications, and have a reference value for online network security management and user’s online behavior supervision.

online application; attribute correlation analysis; identity similarity; characteristic propagation

2015-11-30。 作者簡(jiǎn)介:劉兆麗(1985—),女,博士生;秦濤(通信作者),男,副教授。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61221063,61403301,61402373);中國(guó)博士后科學(xué)基金資助項(xiàng)目(2014M562417)。

10.7652/xjtuxb201604001

TP393

A

0253-987X(2016)04-0001-06