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

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

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

|{}%

?

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

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

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

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

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

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

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

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

1 用戶名相似度傳播模型

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

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

1.2 用戶名相似度問題建模

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

(1)

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

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

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

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

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

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

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

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

步驟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é)點清除

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

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

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

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

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

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

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

3 用戶名相似度度量方法

3.1 用戶名相似度計算方法

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

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

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

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

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

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

步驟4 分別計算兩字符串的中文字符串最長公共字串集合與英文字符串最長公共字串集合,計算中文字符串時,MinMatchLength取值為1;計算英文字符串時,MinMatchLength取值為3。

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

4 實驗結(jié)果分析

4.1 相似度方法比較

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

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

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

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

4.2 CGST算法性能分析

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

圖3 GST與CGST算法比較

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

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

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

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

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

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

5 結(jié) 論

線上應(yīng)用在豐富了用戶生活的同時,也給網(wǎng)絡(luò)輿論安全管理帶來一定的困難,本文圍繞用戶跨線上應(yīng)用身份屬性關(guān)聯(lián)問題開展了研究。首先,本文對所收集到的新浪微博信息和人人網(wǎng)信息進(jìn)行了預(yù)處理,清除了新浪微博中的僵尸粉等賬號。再者,根據(jù)中文社交網(wǎng)絡(luò)中用戶名的特點,提出了基于CGST算法的用戶名相似度計算方法。最后,為了充分利用用戶節(jié)點的信息和網(wǎng)絡(luò)結(jié)構(gòu)方面的特征信息,本文提出了基于用戶名相似度傳播模型的身份屬性關(guān)聯(lián)方法,在大幅度降低計算復(fù)雜度的同時,也有效地提升了身份屬性信息關(guān)聯(lián)的準(zhǔn)確性。結(jié)合所收集到的用戶身份屬性信息的實驗結(jié)果表明,本文所提出的方法在計算復(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。 作者簡介:劉兆麗(1985—),女,博士生;秦濤(通信作者),男,副教授。 基金項目:國家自然科學(xué)基金資助項目(61221063,61403301,61402373);中國博士后科學(xué)基金資助項目(2014M562417)。

10.7652/xjtuxb201604001

TP393

A

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