王 莎,張連明
(湖南師范大學(xué)物理與信息科學(xué)學(xué)院,長沙 410 081)
基于標(biāo)簽的微博人脈網(wǎng)絡(luò)挖掘算法和結(jié)構(gòu)分析
王 莎,張連明
(湖南師范大學(xué)物理與信息科學(xué)學(xué)院,長沙 410 081)
針對互聯(lián)網(wǎng)微博業(yè)務(wù)的廣泛應(yīng)用及其對大數(shù)據(jù)挖掘和分析的影響,提出一種基于標(biāo)簽的微博人脈網(wǎng)絡(luò)挖掘算法。分析該網(wǎng)絡(luò)的結(jié)構(gòu)特征,利用微博用戶標(biāo)簽,在模糊匹配過程中計算詞語之間的匹配度時,主要考慮詞語語素、次序和詞長3個因素。為弱化以不同用戶為起點(diǎn)對算法準(zhǔn)確率的影響,分別以普通用戶和名人用戶為起點(diǎn)用戶,挖掘微博人脈網(wǎng)絡(luò)數(shù)據(jù)。同時,研究微博人脈網(wǎng)絡(luò)的結(jié)構(gòu)特性,通過分析發(fā)現(xiàn)微博人脈網(wǎng)絡(luò)同時具有小世界和無標(biāo)度特性。實(shí)驗(yàn)結(jié)果表明,運(yùn)用該算法對名人用戶和普通用戶朋友中對IT感興趣的人進(jìn)行挖掘的誤差率是可接受的。其中,挖掘10個名人用戶朋友時算法的平均誤差率為14.08%,挖掘10個普通用戶朋友時算法的平均誤差率為10.63%。
標(biāo)簽;微博;人脈網(wǎng)絡(luò);模糊匹配;數(shù)據(jù)挖掘;結(jié)構(gòu)特征
隨著Web2.0技術(shù)的不斷發(fā)展,社交網(wǎng)絡(luò)發(fā)展勢頭強(qiáng)勁,微博人脈網(wǎng)絡(luò)更是成為一個強(qiáng)大的新媒體社交平臺[1]。微博人脈網(wǎng)絡(luò)極大地改變了人們的社會生活方式,人們享受其帶來的自由和便利。微博人脈網(wǎng)絡(luò)結(jié)構(gòu)的測量與建模、微博用戶行為的分析對重構(gòu)通信網(wǎng)絡(luò)結(jié)構(gòu)、個性化推薦、社會管理等方面具有一定的指導(dǎo)意義和實(shí)用價值。
微博人脈網(wǎng)絡(luò)是以用戶ID為節(jié)點(diǎn)、以用戶之間的關(guān)系為邊的有向網(wǎng)絡(luò)[2]。新浪微博是中國第一家推出微博業(yè)務(wù)的門戶網(wǎng)站,經(jīng)過2年的發(fā)展,它已經(jīng)和Twitter[3]一起成為全球使用最多的微博類服務(wù)網(wǎng)站。隨著微博業(yè)務(wù)的廣泛應(yīng)用,微博用戶劇增,微博信息更新頻繁,信息傳播速度越來越快[4]。微博數(shù)據(jù)的挖掘及其內(nèi)在聯(lián)系的理解顯得非常重要[5]。
面向微博的數(shù)據(jù)挖掘技術(shù)面臨2個挑戰(zhàn):(1)得到微博相關(guān)的所有數(shù)據(jù);(2)所有得到的微博數(shù)據(jù)不是絕對精確的,只要在保證速度的前提下近似地反映宏觀和整體情況。在以用戶為中心的Web2.0環(huán)境中,用戶按自己的理解為資源添加標(biāo)簽來對其進(jìn)行標(biāo)注,以更好地為用戶組織資源。傳統(tǒng)的資源推薦考慮用戶和資源2個方面,即使用的是資源-用戶2個維度。后來發(fā)展的網(wǎng)絡(luò)資源在前一個的基礎(chǔ)上增加了標(biāo)簽因素,也就是說推薦是基于資源-用戶-標(biāo)簽3個維度,所以在系統(tǒng)向用戶進(jìn)行推薦的時候,與傳統(tǒng)的推薦相比要多考慮標(biāo)簽這一因素。例如在新浪微博中[6],用戶可以給自己設(shè)定特定的標(biāo)簽來表示自己的興趣愛好,系統(tǒng)可以根據(jù)用戶設(shè)定的標(biāo)簽為用戶推薦其有相同愛好的人,這樣就只需考慮用戶-標(biāo)簽2個維度,在為用戶進(jìn)行推薦時節(jié)省了時間和資源[7]。也可根據(jù)用戶設(shè)定的標(biāo)簽在微博領(lǐng)域的競爭中挖掘同類人,即有著同一興趣愛好的用戶,這不僅有利于微博企業(yè)了解特定領(lǐng)域用戶的行為,而且能夠?yàn)樘囟I(lǐng)域的用戶提供個性化服務(wù),分析信息在此類人群中的傳播速度等。
本文利用微博提供的API接口獲取數(shù)據(jù),提出基于標(biāo)簽的模糊匹配微博人脈網(wǎng)絡(luò)挖掘算法,分析網(wǎng)絡(luò)的結(jié)構(gòu)特性。由于標(biāo)簽為詞語或短語,在標(biāo)簽的匹配過程中主要考慮詞語語素、次序和詞長這3個方面,計算標(biāo)簽之間的匹配度。此外,基于上述算法所得的微博人脈網(wǎng)絡(luò)數(shù)據(jù),分析其結(jié)構(gòu)特性。
2.1 算法原理
微博中使用的標(biāo)簽用來表示用戶的興趣,由此可以根據(jù)標(biāo)簽系統(tǒng)挖一些興趣相投的人,即人脈聚合。用戶可以給自己設(shè)定標(biāo)簽,標(biāo)簽一般為一個詞語或者短語,在進(jìn)行模糊匹配時首先建立一個標(biāo)準(zhǔn)標(biāo)簽庫。
本文以獲取對IT感興趣的人為例,因每個人的習(xí)慣不同,在給自己設(shè)定標(biāo)簽時,表達(dá)方式不同可能表示的興趣愛好相同,比如A用戶給自己設(shè)定一個標(biāo)簽為程序員,B用戶給自己設(shè)定一個標(biāo)簽程序猿,這2個標(biāo)簽表達(dá)方式不同,但語義相同。所以,若要對對IT感興趣的人進(jìn)行聚類,可以先建立一個標(biāo)準(zhǔn)庫,這個標(biāo)準(zhǔn)庫中的標(biāo)簽都與IT相關(guān),當(dāng)?shù)玫侥骋挥脩舻臉?biāo)簽時,拿這個用戶的標(biāo)簽去和標(biāo)準(zhǔn)庫中的標(biāo)簽進(jìn)行匹配,如若符合要求,則將該用戶的基本信息挖掘出來。
標(biāo)準(zhǔn)庫的建立方式如下:
(1)用戶先注冊一個微博賬號,在微博名人堂的IT、通信中的IT業(yè)界里選取做IT的給自己設(shè)有標(biāo)簽的20位名人,分別取到他們的標(biāo)簽。
(2)將這些標(biāo)簽中與IT行業(yè)無關(guān)的標(biāo)簽去掉。
(3)將標(biāo)簽中重復(fù)的、以及表達(dá)意思一樣或者相近的標(biāo)簽去掉,得到的這些標(biāo)簽作為標(biāo)準(zhǔn)庫。標(biāo)準(zhǔn)庫中有13個標(biāo)簽,它們分別是IT、移動互聯(lián)網(wǎng)、Twitter、軟件、社交網(wǎng)絡(luò)、程序員、數(shù)據(jù)庫、云計算、架構(gòu)設(shè)計、三網(wǎng)融合、編程、數(shù)據(jù)挖掘和Linux。
在漢語中,語氣、語調(diào)、語素等結(jié)構(gòu)的細(xì)微變化都可能造成詞義的變化。為了提高挖掘算法的準(zhǔn)確度,本文對語素、次序和詞長這3個方面進(jìn)行綜合考慮,2個詞語A 和B的相似度WordSim(A,B)可以使用下列公式來計算[8]:
其中,α,β,γ為可調(diào)節(jié)參數(shù),且滿足α + β + γ =1;Same(A,B) 為A和B中相同字的個數(shù);Len(A)和Len(B)分別為A和B中字的個數(shù);Once(A,B)表示當(dāng)且僅當(dāng)在A和B中出現(xiàn)一次的語素集合;若用Pfirst(A,B)表示Once(A,B)語素在A中位置序號構(gòu)成的向量,Psecond(A,B)表示Pfirst(A,B)中分量按對應(yīng)語素在B中次序排序生成的向量,則RevOrd(A,B)表示Psecond(A,B)各相鄰分量的逆序數(shù)。
根據(jù)經(jīng)驗(yàn)數(shù)據(jù)可知,語素占主要地位,其次是字序和詞長,故在設(shè)置參數(shù)時,一般要求α大于β,遠(yuǎn)大于γ。本文取α=0.7,β=0.29,γ=0.01。
2.2 算法實(shí)現(xiàn)
標(biāo)簽是基于網(wǎng)絡(luò)對網(wǎng)絡(luò)資源進(jìn)行自由標(biāo)注的一種方法,它具有自由性[9]。對資源進(jìn)行標(biāo)注之后,用戶可以根據(jù)標(biāo)簽更方便地獲取自己所需的資源。在微博中,用戶給自己設(shè)定的標(biāo)簽代表著用戶的喜好,根據(jù)用戶的喜好可以對其進(jìn)行推薦,使其找到與之興趣相投的人[10]。微博用戶能為自己設(shè)定標(biāo)簽,這樣為用戶進(jìn)行推薦時只涉及用戶-標(biāo)簽2個維度,節(jié)省了時間和資源。
標(biāo)簽設(shè)定具有自由性,2個同時對IT感興趣的人在分別給自己設(shè)定標(biāo)簽時,由于年齡、個人習(xí)慣、教育程度等差異,造成他們各自的表達(dá)方式可能不同,因此在挖掘?qū)T感興趣的人脈網(wǎng)絡(luò)時必需對標(biāo)簽進(jìn)行模糊匹配。
具體方法如下:
(1)調(diào)用微博API獲取用戶標(biāo)簽。
(2)將獲得的標(biāo)簽分別與標(biāo)簽標(biāo)準(zhǔn)庫中的標(biāo)簽進(jìn)行相似度計算。
(3)若計算得到的結(jié)果有一個匹配度值大于閾值μ,則認(rèn)為該用戶也對IT行業(yè)感興趣,該用戶滿足條件,把該用戶的信息挖掘出來(本文取μ=0.5)。
本文算法的偽代碼如下:
算法 基于標(biāo)簽的模糊匹配微博人脈網(wǎng)絡(luò)挖掘算法
輸入 一個用戶ID,標(biāo)準(zhǔn)標(biāo)簽庫,閾值μ
輸出 用戶ID的朋友中符合條件的用戶信息
假設(shè)朋友關(guān)系的層數(shù)為l,平均每個人擁有的朋友數(shù)為m,平均每個人擁有的標(biāo)簽數(shù)為t,標(biāo)準(zhǔn)標(biāo)簽庫含有的標(biāo)簽數(shù)為s。所以MATCH()方法內(nèi)層循環(huán)占用的時間為O(s),外層循環(huán)為O(t),則MATCH()方法的復(fù)雜度為O(st)。Crawler()方法外層循環(huán)為O(l),內(nèi)層循環(huán)占用的時間為O(ml),所以整個算法的復(fù)雜度為O(mlst)。
2.3 匹配度計算實(shí)例
假設(shè)一個用戶的標(biāo)簽為旅行、汽車、互聯(lián)網(wǎng)觀察、云計算中心、攝影、美食,對這6個標(biāo)簽與標(biāo)準(zhǔn)庫中的13個標(biāo)簽分別進(jìn)行匹配度計算,結(jié)果如表1所示。其中,該用戶的標(biāo)簽“互聯(lián)網(wǎng)觀察”與標(biāo)準(zhǔn)庫中的“移動互聯(lián)網(wǎng)”標(biāo)簽相似度最大,達(dá)到0.720 0,其次是該用戶標(biāo)簽“云計算中心”,它與標(biāo)準(zhǔn)庫中“云計算”的相似度為0.527 5。該用戶的“互聯(lián)網(wǎng)觀察”和“云計算中心”這2個標(biāo)簽與標(biāo)準(zhǔn)庫中13個標(biāo)簽的平均相似度分別為0.085 6和0.048 0。其余4個標(biāo)簽與標(biāo)準(zhǔn)庫中13個標(biāo)簽的相似度都非常低,且平均相似度均為0.005 0。顯然,該用戶的2個標(biāo)簽“互聯(lián)網(wǎng)觀察”和“云計算中心”與IT標(biāo)準(zhǔn)庫中標(biāo)簽的相似度均大于閾值μ=0.5,可以判斷該用戶是一個IT人。
表1 標(biāo)簽的匹配
取2組數(shù)據(jù)集來分析和檢驗(yàn)對IT感興趣的人脈網(wǎng)絡(luò)挖掘算法的準(zhǔn)確率。為了削弱以不同類型的用戶為起點(diǎn)對分析結(jié)果可能造成的影響,分別選取2類用戶,即名人用戶和普通用戶,其中,名人用戶為新浪微博中針對IT、通信行業(yè)中擁有真實(shí)社會身份并提供證明材料且通過認(rèn)證的人群,普通用戶為新浪微博中沒進(jìn)行認(rèn)證的用戶。第一組數(shù)據(jù)是在新浪微博名人堂中取10個與IT相關(guān)的名人,挖掘出他們所關(guān)注的朋友信息,從這些信息中的標(biāo)簽中人為地判斷這些人哪些是對IT感興趣的,統(tǒng)計出這個用戶中對IT感興趣的朋友的個數(shù)。因?yàn)楸疚乃惴ㄊ莿討B(tài)地進(jìn)行人脈網(wǎng)絡(luò)挖掘,即滿足條件的用戶就獲取他的信息,這樣就可以分別把這10個名人的朋友中同樣對IT感興趣的人挖掘出來,得到相關(guān)數(shù)據(jù)如表2所示。
表2 名人用戶朋友的相關(guān)數(shù)據(jù)
在表2中,U1,U2,…,U10分別表示10個名人用戶;P表示對應(yīng)名人用戶的朋友個數(shù);N表示沒有給自己設(shè)定標(biāo)簽的朋友個數(shù);M1表示人為地判斷用戶朋友中對IT感興趣的朋友個數(shù),其判斷方法為通過新浪微博提供的API接口分別挖掘所選名人用戶的朋友信息,其中包括標(biāo)簽信息,再根據(jù)朋友給自己設(shè)定的標(biāo)簽來判斷該朋友是否對IT感興趣;M2為計算機(jī)模糊匹配后挖到的朋友中對IT感興趣的朋友個數(shù);F表示對IT感興趣的朋友中女性人數(shù)。
從表2可以看出,在名人的朋友中只有很少一部分用戶不會給自己設(shè)定標(biāo)簽,同時,名人朋友中的女性朋友對IT感興趣的人數(shù)比較少,這符合女性用戶的興趣愛好和職業(yè)選擇特點(diǎn)。
第2組數(shù)據(jù)是選10個普通人,按同樣的方法獲取數(shù)據(jù),得到相關(guān)數(shù)據(jù)如表3所示。
表3 普通用戶朋友的相關(guān)數(shù)據(jù)
從表3中還可以看出,普通用戶的朋友中也只有很少一部分人未給自己設(shè)定標(biāo)簽,且普通用戶朋友中女性朋友對IT感興趣的人數(shù)非常少。
為了分析本文算法的效率,采取人工判斷方法得到的相關(guān)結(jié)果與其進(jìn)行比較。圖1給出了運(yùn)用本文算法就用戶中對IT感興趣的朋友個數(shù)與基于人工判斷得出用戶朋友中對IT感興趣的人數(shù)關(guān)系圖。總體看來,本文算法挖掘出名人用戶的朋友數(shù)目略小于人工判斷得到的名人用戶朋友數(shù)目,普通用戶朋友數(shù)目略小于或等于人工判斷得到的數(shù)目。普通用戶的朋友中對IT感興趣的人數(shù)相對IT名人的朋友中對IT感興趣的人數(shù)來說少了很多,這是因?yàn)樵诂F(xiàn)實(shí)生活中存在物以類聚的現(xiàn)象,從事IT行業(yè)的人的朋友中對IT感興趣的人相對從事其他行業(yè)的人的朋友中對IT感興趣的人要多些。
圖1 挖掘名人用戶朋友的準(zhǔn)確率
圖2給出了運(yùn)用本文算法對名人用戶和普通用戶朋友中對IT感興趣的人進(jìn)行挖掘得到結(jié)果的誤差率。挖掘10個名人用戶朋友時,算法的平均誤差率為14.08%,而挖掘10個普通用戶朋友時,算法的平均誤差率為10.63%,其中,普通用戶6、7和9的所有朋友全部被挖掘出來。作為現(xiàn)階段大數(shù)據(jù)挖掘面臨的2個挑戰(zhàn)之一,利用本文算法得到的微博數(shù)據(jù)允許有一定的不精確性,只要在保證速度的前提下近似地反映宏觀和整體情況,這將在本文第4節(jié)中予以討論。
圖2 算法誤差率
綜上所述,在新浪微博中不管是普通用戶還是名人用戶,他們都會給自己設(shè)定標(biāo)簽。利用用戶給自己設(shè)定的標(biāo)簽,構(gòu)造基于標(biāo)簽的模糊匹配微博脈挖掘算法的準(zhǔn)確率較高,從而本文可以根據(jù)需要挖取特定領(lǐng)域的用戶,分析不同領(lǐng)域用戶之間的各種關(guān)系,這樣微博就能為用戶提供個性服務(wù),更好地滿足用戶的需求。同時還可以看出,從事IT行業(yè)的人的朋友中對IT感興趣的人數(shù)相對較多,且對IT感興趣的女性人數(shù)非常少,這符合IT工作性質(zhì)和人們的職業(yè)選擇。
基于本文算法研究了對IT感興趣的不同數(shù)量的名人微博人脈網(wǎng)絡(luò),以及教育、體育等其他領(lǐng)域中大量名人微博人脈網(wǎng)絡(luò),發(fā)現(xiàn)算法均具有較好的性能。
在本節(jié)利用新浪微博提供的API獲得的數(shù)據(jù)來研究微博人脈網(wǎng)絡(luò)的結(jié)構(gòu)特性,同時以顯示其宏觀性和整體性。采用廣度優(yōu)先策略,以筆者本人的新浪微博賬號為起始用戶,獲取作者用戶ID以及朋友ID,再以朋友ID的起始點(diǎn),獲取朋友的朋友ID,獲取數(shù)據(jù)154 0 33條,其中包含101 496個節(jié)點(diǎn),154 021條邊。
聚集系數(shù)是反映一個用戶的朋友之間關(guān)系的一個特征量,求出該微博人脈網(wǎng)絡(luò)絡(luò)的聚類系數(shù)為0.127。顯然遠(yuǎn)大于同等規(guī)模的隨機(jī)網(wǎng)絡(luò)的聚類系數(shù),較大的聚類系數(shù)說明所關(guān)注的對象之間很可能也互相關(guān)注,即微博人脈網(wǎng)絡(luò)絡(luò)具有高聚類特性。該微博人脈網(wǎng)絡(luò)絡(luò)的平均路徑長度為4.57,這對于微博這樣一種有向社會網(wǎng)絡(luò)來說是很小的,也就是微博具有較短的平均最短路徑,這也說明微博用戶之間平均通過4~5個用戶就能與任意一個用戶建立聯(lián)系。較大的聚集系數(shù)和較短的平均路徑長度說明微博人脈網(wǎng)絡(luò)絡(luò)具有小世界特性。微博人脈網(wǎng)絡(luò)的小世界特性使得信息傳播的平均路徑長度很小,因此信息能在微博網(wǎng)絡(luò)中迅速地傳播開來。
圖3給出了微博人脈網(wǎng)絡(luò)絡(luò)節(jié)點(diǎn)度分布情況(節(jié)點(diǎn)度小于等于500的情形),顯然,該網(wǎng)絡(luò)節(jié)點(diǎn)度滿足冪律分布,通過計算得到冪指數(shù)為1.906,這說明微博人脈網(wǎng)絡(luò)絡(luò)屬于無標(biāo)度網(wǎng)絡(luò)。名人用戶受到更多用戶的關(guān)注,容易成為微博人脈網(wǎng)絡(luò)中的中心節(jié)點(diǎn)。
圖3 微博人脈網(wǎng)絡(luò)節(jié)點(diǎn)度分布
本文提出一種基于模糊匹配的人脈挖掘算法,在標(biāo)簽匹配過程中綜合考慮詞語語素、字序、字長,通過模糊匹配可以挖掘特定領(lǐng)域的人,實(shí)驗(yàn)結(jié)果表明該算法準(zhǔn)確率較高,同時通過分析微博網(wǎng)絡(luò)數(shù)據(jù)表明微博網(wǎng)絡(luò)具有小世界特性。但本文算法只能挖掘大領(lǐng)域的人群,無法挖掘更小領(lǐng)域的人,這是今后研究的方向。
[1] Kang Shulong, Zhang Chuang, Lin Zhiqing, et al. Complexity Research of Massively Microblogging Based o n Human Behaviors[C]//Proc. of the 2nd International W orkshop on Database Technology and Applications. Wuhan, China: [s. n.], 2010: 1-4
[2] Wang Rui, Jin Yongsheng. An Empirical Study on the Relationship Betwe en the Followers’ Number and In fluence of Microblogging[C]//Proc. of International Conference on E-business and E-government. Guangzhou, China: [s. n.], 2010: 2014-2017.
[3] Cha M Y, Haddadi H, Ben evenuto F, et al. Measuring User Influence in T witter: The Million Follower Fallacy[C]//Proc. of the 4th International Conference on Weblogs a nd Social Media. Washington D. C., USA: AAAI Press, 2010: 10-17.
[4] 孫曉瑩, 李大展, 王 水. 國內(nèi)微博研究的發(fā)展與機(jī)遇[J].情報雜志, 2012, 31(7): 25-33.
[5] 廉 捷, 周 欣, 曹 偉, 等. 新浪微博數(shù)據(jù)挖掘方案[J].清華大學(xué)學(xué)報, 2011, 51(10): 1300-1305.
[6] 張嵐嵐. 新浪微博的網(wǎng)絡(luò)輿情分析研究——模型、設(shè)計與實(shí)驗(yàn)[D]. 上海: 華東師范大學(xué), 2011.
[7] Golder S A, Huberman B A. The Structure of Collaborative Tagging Systems[J]. Journal of Information Seienees, 200 6, 32(2): 198-208.
[8] 朱毅華, 侯漢清, 沙印亭. 計算機(jī)識別漢語同義詞的兩種算法比較和測評[J]. 中國圖書館學(xué)報, 2002, 28(4): 82-85.
[9] 劉向紅, 宋 文, 姚 朋. 基于標(biāo)簽的Folksonomy機(jī)制研究——以CiteUlike為例[J]. 圖書館理論與實(shí)踐, 2010, (5): 29-33.
[10] 易 明. 基于Web挖掘的個性化信息推薦[M]. 北京: 北京科學(xué)出版社, 2010.
編輯 任吉慧
Mining Algorithm and Structural Analysis of Microblog Interpersonal Relationship Network Based on Tag
WANG Sha, ZHANG Lian-ming
(College of Physics and Information Science, Hunan Normal University, Changsha 410081, China)
For the widespread use of microblog business and the impact on data mining techniques, a mining algorithm of microblog interpersonal relationship network is proposed based on the fuzzy matching of tag, and the characteristics of the network are analyzed. Use the tag of the us ers, the algorithm mainly considers w ord morpheme, order, and word length to calculate the match degree of the words when matching the tag. For weakening the influence that using different users as a starting point may have different result, ordinary users and celebrities as a starting point separately are used. At the same time, the structural characteristics o f the netw ork are st udied, and the analysis results show that the network has small-world and scale-free properties. The results show that the mining error rate o f celebrities and common users friends who are interested in IT. When mining 10 celebrity users’ friends, the average error rate of the algorithm is 14.08%, and 10.63% for common users.
tag; microblog; interpersonal relationship network; fuzzy matching; data mining; structural characteristics
10.3969/j.issn.1000-3428.2014.05.002
1000-3428(2014)05-0007-05
A
TP393
國家自然科學(xué)基金資助項(xiàng)目(60973129);廣東省自然科學(xué)基金資助項(xiàng)目(S2011010000812)。
王 莎(1988-),女,碩士研究生,主研方向:社會網(wǎng)絡(luò);張連明(通訊作者),教授、博士。
2013-08-15
2013-10-31E-mail:zlm@hunnu.edu.cn