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

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

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

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

|{}%

?

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

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

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

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

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

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

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

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

1 用戶名相似度傳播模型

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

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

1.2 用戶名相似度問題建模

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

(1)

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

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

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

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

(a)網絡A (b)網絡B圖1 結合網絡結構的傳播模型

步驟2 獲取該對用戶在各自網絡中的鄰居節(jié)點,例如圖1中的A1、A2、A3和B1、B2、B3,若種子集合中所有的匹配節(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所計算的結果中選取滿足一定條件的匹配對,同時將匹配對添至種子集合;

步驟5 返回步驟1。

2 線上行為信息收集與預處理

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

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

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

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

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

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

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

2.2 用戶好友網絡構建

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

3 用戶名相似度度量方法

3.1 用戶名相似度計算方法

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

3.2 針對中文社交網絡用戶名特征的相似度算法

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

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

步驟2 轉換字符串中繁體字為簡體字。

步驟3 如果當一個字符串包含另一個字符串,則相似度可設置為一個較高的固定值,如1.0;若不包含,則轉入步驟4。

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

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

4 實驗結果分析

4.1 相似度方法比較

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

表2 部分種子用戶跨應用用戶名

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

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

4.2 CGST算法性能分析

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

圖3 GST與CGST算法比較

4.3 傳播算法計算復雜度分析

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

4.4 算法匹配準確度分析

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

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

表3 關聯(lián)方法關聯(lián)結果信息

5 結 論

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

10.7652/xjtuxb201604001

TP393

A

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