基于標簽的微博人脈網絡挖掘算法和結構分析

王 莎，張連明

(湖南師范大學物理與信息科學學院，長沙 410 081)

基于標簽的微博人脈網絡挖掘算法和結構分析

王 莎，張連明

(湖南師范大學物理與信息科學學院，長沙 410 081)

針對互聯網微博業務的廣泛應用及其對大數據挖掘和分析的影響，提出一種基于標簽的微博人脈網絡挖掘算法。分析該網絡的結構特征，利用微博用戶標簽，在模糊匹配過程中計算詞語之間的匹配度時，主要考慮詞語語素、次序和詞長3個因素。為弱化以不同用戶為起點對算法準確率的影響，分別以普通用戶和名人用戶為起點用戶，挖掘微博人脈網絡數據。同時，研究微博人脈網絡的結構特性，通過分析發現微博人脈網絡同時具有小世界和無標度特性。實驗結果表明，運用該算法對名人用戶和普通用戶朋友中對IT感興趣的人進行挖掘的誤差率是可接受的。其中，挖掘10個名人用戶朋友時算法的平均誤差率為14.08%，挖掘10個普通用戶朋友時算法的平均誤差率為10.63%。

標簽；微博；人脈網絡；模糊匹配；數據挖掘；結構特征

1 概述

隨著Web2.0技術的不斷發展，社交網絡發展勢頭強勁，微博人脈網絡更是成為一個強大的新媒體社交平臺[1]。微博人脈網絡極大地改變了人們的社會生活方式，人們享受其帶來的自由和便利。微博人脈網絡結構的測量與建模、微博用戶行為的分析對重構通信網絡結構、個性化推薦、社會管理等方面具有一定的指導意義和實用價值。

微博人脈網絡是以用戶ID為節點、以用戶之間的關系為邊的有向網絡[2]。新浪微博是中國第一家推出微博業務的門戶網站，經過2年的發展，它已經和Twitter[3]一起成為全球使用最多的微博類服務網站。隨著微博業務的廣泛應用，微博用戶劇增，微博信息更新頻繁，信息傳播速度越來越快[4]。微博數據的挖掘及其內在聯系的理解顯得非常重要[5]。

面向微博的數據挖掘技術面臨2個挑戰：(1)得到微博相關的所有數據；(2)所有得到的微博數據不是絕對精確的，只要在保證速度的前提下近似地反映宏觀和整體情況。在以用戶為中心的Web2.0環境中，用戶按自己的理解為資源添加標簽來對其進行標注，以更好地為用戶組織資源。傳統的資源推薦考慮用戶和資源2個方面，即使用的是資源-用戶2個維度。后來發展的網絡資源在前一個的基礎上增加了標簽因素，也就是說推薦是基于資源-用戶-標簽3個維度，所以在系統向用戶進行推薦的時候，與傳統的推薦相比要多考慮標簽這一因素。例如在新浪微博中[6]，用戶可以給自己設定特定的標簽來表示自己的興趣愛好，系統可以根據用戶設定的標簽為用戶推薦其有相同愛好的人，這樣就只需考慮用戶-標簽2個維度，在為用戶進行推薦時節省了時間和資源[7]。也可根據用戶設定的標簽在微博領域的競爭中挖掘同類人，即有著同一興趣愛好的用戶，這不僅有利于微博企業了解特定領域用戶的行為，而且能夠為特定領域的用戶提供個性化服務，分析信息在此類人群中的傳播速度等。

本文利用微博提供的API接口獲取數據，提出基于標簽的模糊匹配微博人脈網絡挖掘算法，分析網絡的結構特性。由于標簽為詞語或短語，在標簽的匹配過程中主要考慮詞語語素、次序和詞長這3個方面，計算標簽之間的匹配度。此外，基于上述算法所得的微博人脈網絡數據，分析其結構特性。

2 挖掘算法

2.1 算法原理

微博中使用的標簽用來表示用戶的興趣，由此可以根據標簽系統挖一些興趣相投的人，即人脈聚合。用戶可以給自己設定標簽，標簽一般為一個詞語或者短語，在進行模糊匹配時首先建立一個標準標簽庫。

本文以獲取對IT感興趣的人為例，因每個人的習慣不同，在給自己設定標簽時，表達方式不同可能表示的興趣愛好相同，比如A用戶給自己設定一個標簽為程序員，B用戶給自己設定一個標簽程序猿，這2個標簽表達方式不同，但語義相同。所以，若要對對IT感興趣的人進行聚類，可以先建立一個標準庫，這個標準庫中的標簽都與IT相關，當得到某一用戶的標簽時，拿這個用戶的標簽去和標準庫中的標簽進行匹配，如若符合要求，則將該用戶的基本信息挖掘出來。

標準庫的建立方式如下：

(1)用戶先注冊一個微博賬號，在微博名人堂的IT、通信中的IT業界里選取做IT的給自己設有標簽的20位名人，分別取到他們的標簽。

(2)將這些標簽中與IT行業無關的標簽去掉。

(3)將標簽中重復的、以及表達意思一樣或者相近的標簽去掉，得到的這些標簽作為標準庫。標準庫中有13個標簽，它們分別是IT、移動互聯網、Twitter、軟件、社交網絡、程序員、數據庫、云計算、架構設計、三網融合、編程、數據挖掘和Linux。

在漢語中，語氣、語調、語素等結構的細微變化都可能造成詞義的變化。為了提高挖掘算法的準確度，本文對語素、次序和詞長這3個方面進行綜合考慮，2個詞語A 和B的相似度WordSim(A,B)可以使用下列公式來計算[8]：

其中，α，β，γ為可調節參數，且滿足α + β + γ =1；Same(A,B) 為A和B中相同字的個數；Len(A)和Len(B)分別為A和B中字的個數；Once(A,B)表示當且僅當在A和B中出現一次的語素集合；若用Pfirst(A,B)表示Once(A,B)語素在A中位置序號構成的向量，Psecond(A,B)表示Pfirst(A,B)中分量按對應語素在B中次序排序生成的向量，則RevOrd(A,B)表示Psecond(A,B)各相鄰分量的逆序數。

根據經驗數據可知，語素占主要地位，其次是字序和詞長，故在設置參數時，一般要求α大于β，遠大于γ。本文取α=0.7，β=0.29，γ=0.01。

2.2 算法實現

標簽是基于網絡對網絡資源進行自由標注的一種方法，它具有自由性[9]。對資源進行標注之后，用戶可以根據標簽更方便地獲取自己所需的資源。在微博中，用戶給自己設定的標簽代表著用戶的喜好，根據用戶的喜好可以對其進行推薦，使其找到與之興趣相投的人[10]。微博用戶能為自己設定標簽，這樣為用戶進行推薦時只涉及用戶-標簽2個維度，節省了時間和資源。

標簽設定具有自由性，2個同時對IT感興趣的人在分別給自己設定標簽時，由于年齡、個人習慣、教育程度等差異，造成他們各自的表達方式可能不同，因此在挖掘對IT感興趣的人脈網絡時必需對標簽進行模糊匹配。

具體方法如下：

(1)調用微博API獲取用戶標簽。

(2)將獲得的標簽分別與標簽標準庫中的標簽進行相似度計算。

(3)若計算得到的結果有一個匹配度值大于閾值μ，則認為該用戶也對IT行業感興趣，該用戶滿足條件，把該用戶的信息挖掘出來(本文取μ=0.5)。

本文算法的偽代碼如下：

算法 基于標簽的模糊匹配微博人脈網絡挖掘算法

輸入 一個用戶ID，標準標簽庫，閾值μ

輸出 用戶ID的朋友中符合條件的用戶信息

假設朋友關系的層數為l，平均每個人擁有的朋友數為m，平均每個人擁有的標簽數為t，標準標簽庫含有的標簽數為s。所以MATCH()方法內層循環占用的時間為O(s)，外層循環為O(t)，則MATCH()方法的復雜度為O(st)。Crawler()方法外層循環為O(l)，內層循環占用的時間為O(ml)，所以整個算法的復雜度為O(mlst)。

2.3 匹配度計算實例

假設一個用戶的標簽為旅行、汽車、互聯網觀察、云計算中心、攝影、美食，對這6個標簽與標準庫中的13個標簽分別進行匹配度計算，結果如表1所示。其中，該用戶的標簽“互聯網觀察”與標準庫中的“移動互聯網”標簽相似度最大，達到0.720 0，其次是該用戶標簽“云計算中心”，它與標準庫中“云計算”的相似度為0.527 5。該用戶的“互聯網觀察”和“云計算中心”這2個標簽與標準庫中13個標簽的平均相似度分別為0.085 6和0.048 0。其余4個標簽與標準庫中13個標簽的相似度都非常低，且平均相似度均為0.005 0。顯然，該用戶的2個標簽“互聯網觀察”和“云計算中心”與IT標準庫中標簽的相似度均大于閾值μ=0.5，可以判斷該用戶是一個IT人。

表1 標簽的匹配

3 算法檢驗與評價

取2組數據集來分析和檢驗對IT感興趣的人脈網絡挖掘算法的準確率。為了削弱以不同類型的用戶為起點對分析結果可能造成的影響，分別選取2類用戶，即名人用戶和普通用戶，其中，名人用戶為新浪微博中針對IT、通信行業中擁有真實社會身份并提供證明材料且通過認證的人群，普通用戶為新浪微博中沒進行認證的用戶。第一組數據是在新浪微博名人堂中取10個與IT相關的名人，挖掘出他們所關注的朋友信息，從這些信息中的標簽中人為地判斷這些人哪些是對IT感興趣的，統計出這個用戶中對IT感興趣的朋友的個數。因為本文算法是動態地進行人脈網絡挖掘，即滿足條件的用戶就獲取他的信息，這樣就可以分別把這10個名人的朋友中同樣對IT感興趣的人挖掘出來，得到相關數據如表2所示。

表2 名人用戶朋友的相關數據

在表2中，U1,U2,…,U10分別表示10個名人用戶；P表示對應名人用戶的朋友個數；N表示沒有給自己設定標簽的朋友個數；M1表示人為地判斷用戶朋友中對IT感興趣的朋友個數，其判斷方法為通過新浪微博提供的API接口分別挖掘所選名人用戶的朋友信息，其中包括標簽信息，再根據朋友給自己設定的標簽來判斷該朋友是否對IT感興趣；M2為計算機模糊匹配后挖到的朋友中對IT感興趣的朋友個數；F表示對IT感興趣的朋友中女性人數。

從表2可以看出，在名人的朋友中只有很少一部分用戶不會給自己設定標簽，同時，名人朋友中的女性朋友對IT感興趣的人數比較少，這符合女性用戶的興趣愛好和職業選擇特點。

第2組數據是選10個普通人，按同樣的方法獲取數據，得到相關數據如表3所示。

表3 普通用戶朋友的相關數據

從表3中還可以看出，普通用戶的朋友中也只有很少一部分人未給自己設定標簽，且普通用戶朋友中女性朋友對IT感興趣的人數非常少。

為了分析本文算法的效率，采取人工判斷方法得到的相關結果與其進行比較。圖1給出了運用本文算法就用戶中對IT感興趣的朋友個數與基于人工判斷得出用戶朋友中對IT感興趣的人數關系圖。總體看來，本文算法挖掘出名人用戶的朋友數目略小于人工判斷得到的名人用戶朋友數目，普通用戶朋友數目略小于或等于人工判斷得到的數目。普通用戶的朋友中對IT感興趣的人數相對IT名人的朋友中對IT感興趣的人數來說少了很多，這是因為在現實生活中存在物以類聚的現象，從事IT行業的人的朋友中對IT感興趣的人相對從事其他行業的人的朋友中對IT感興趣的人要多些。

圖1 挖掘名人用戶朋友的準確率

圖2給出了運用本文算法對名人用戶和普通用戶朋友中對IT感興趣的人進行挖掘得到結果的誤差率。挖掘10個名人用戶朋友時，算法的平均誤差率為14.08%，而挖掘10個普通用戶朋友時，算法的平均誤差率為10.63%，其中，普通用戶6、7和9的所有朋友全部被挖掘出來。作為現階段大數據挖掘面臨的2個挑戰之一，利用本文算法得到的微博數據允許有一定的不精確性，只要在保證速度的前提下近似地反映宏觀和整體情況，這將在本文第4節中予以討論。

圖2 算法誤差率

綜上所述，在新浪微博中不管是普通用戶還是名人用戶，他們都會給自己設定標簽。利用用戶給自己設定的標簽，構造基于標簽的模糊匹配微博脈挖掘算法的準確率較高，從而本文可以根據需要挖取特定領域的用戶，分析不同領域用戶之間的各種關系，這樣微博就能為用戶提供個性服務，更好地滿足用戶的需求。同時還可以看出，從事IT行業的人的朋友中對IT感興趣的人數相對較多，且對IT感興趣的女性人數非常少，這符合IT工作性質和人們的職業選擇。

基于本文算法研究了對IT感興趣的不同數量的名人微博人脈網絡，以及教育、體育等其他領域中大量名人微博人脈網絡，發現算法均具有較好的性能。

4 人脈網絡結構分析

在本節利用新浪微博提供的API獲得的數據來研究微博人脈網絡的結構特性，同時以顯示其宏觀性和整體性。采用廣度優先策略，以筆者本人的新浪微博賬號為起始用戶，獲取作者用戶ID以及朋友ID，再以朋友ID的起始點，獲取朋友的朋友ID，獲取數據154 0 33條，其中包含101 496個節點，154 021條邊。

聚集系數是反映一個用戶的朋友之間關系的一個特征量，求出該微博人脈網絡絡的聚類系數為0.127。顯然遠大于同等規模的隨機網絡的聚類系數，較大的聚類系數說明所關注的對象之間很可能也互相關注，即微博人脈網絡絡具有高聚類特性。該微博人脈網絡絡的平均路徑長度為4.57，這對于微博這樣一種有向社會網絡來說是很小的，也就是微博具有較短的平均最短路徑，這也說明微博用戶之間平均通過4～5個用戶就能與任意一個用戶建立聯系。較大的聚集系數和較短的平均路徑長度說明微博人脈網絡絡具有小世界特性。微博人脈網絡的小世界特性使得信息傳播的平均路徑長度很小，因此信息能在微博網絡中迅速地傳播開來。

圖3給出了微博人脈網絡絡節點度分布情況(節點度小于等于500的情形)，顯然，該網絡節點度滿足冪律分布，通過計算得到冪指數為1.906，這說明微博人脈網絡絡屬于無標度網絡。名人用戶受到更多用戶的關注，容易成為微博人脈網絡中的中心節點。

圖3 微博人脈網絡節點度分布

5 結束語

本文提出一種基于模糊匹配的人脈挖掘算法，在標簽匹配過程中綜合考慮詞語語素、字序、字長，通過模糊匹配可以挖掘特定領域的人，實驗結果表明該算法準確率較高，同時通過分析微博網絡數據表明微博網絡具有小世界特性。但本文算法只能挖掘大領域的人群，無法挖掘更小領域的人，這是今后研究的方向。

[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] 孫曉瑩, 李大展, 王 水. 國內微博研究的發展與機遇[J].情報雜志, 2012, 31(7): 25-33.

[5] 廉 捷, 周 欣, 曹 偉, 等. 新浪微博數據挖掘方案[J].清華大學學報, 2011, 51(10): 1300-1305.

[6] 張嵐嵐. 新浪微博的網絡輿情分析研究——模型、設計與實驗[D]. 上海: 華東師范大學, 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]. 中國圖書館學報, 2002, 28(4): 82-85.

[9] 劉向紅, 宋 文, 姚 朋. 基于標簽的Folksonomy機制研究——以CiteUlike為例[J]. 圖書館理論與實踐, 2010, (5): 29-33.

[10] 易 明. 基于Web挖掘的個性化信息推薦[M]. 北京: 北京科學出版社, 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

國家自然科學基金資助項目(60973129)；廣東省自然科學基金資助項目(S2011010000812)。

王 莎(1988－)，女，碩士研究生，主研方向：社會網絡；張連明(通訊作者)，教授、博士。

2013-08-15

2013-10-31E-mail：zlm@hunnu.edu.cn