盧體廣，劉 新，劉任任

(湘潭大學信息工程學院智能計算與信息處理教育部重點實驗室，湖南 湘潭 4 11105)

微博數(shù)據(jù)通用抓取算法

盧體廣，劉 新，劉任任

(湘潭大學信息工程學院智能計算與信息處理教育部重點實驗室，湖南 湘潭 4 11105)

目前常用的網(wǎng)絡爬蟲和基于微博API抓取數(shù)據(jù)的算法很難滿足輿情系統(tǒng)對微博數(shù)據(jù)的需求。為此，提出一種模擬瀏覽器登錄微博抓取網(wǎng)頁數(shù)據(jù)的算法，以方便地獲取任意微博用戶網(wǎng)頁上的所有數(shù)據(jù)。通過微博用戶之間的關系構建用戶網(wǎng)絡，并通過該網(wǎng)絡發(fā)現(xiàn)新用戶。為獲取微博上有質量的數(shù)據(jù)，建立一個完整的數(shù)學模型，根據(jù)用戶的發(fā)帖數(shù)、發(fā)帖頻率、粉絲數(shù)、轉發(fā)數(shù)、評論數(shù)等因素來計算用戶影響力，以影響力為主要因子構建優(yōu)先隊列，使得影響力越大的用戶數(shù)據(jù)采集頻率越高，同時計算時間間隔以兼顧非活躍用戶的數(shù)據(jù)獲取。實驗結果表明，該算法具有通用性強、完全無需人工干預、獲取信息的質量高、速度快等優(yōu)點。

微博數(shù)據(jù)；模擬登錄；用戶網(wǎng)絡；用戶影響力；網(wǎng)絡輿情；優(yōu)先隊列

1 概述

隨著互聯(lián)網(wǎng)的迅猛發(fā)展，網(wǎng)絡輿論也逐漸被人們關注。近幾年來，微博用戶呈現(xiàn)出幾何式的增長(如新浪微博的用戶已經超5億[1])，為輿論的產生和傳播提供了良好的平臺。從近期各級地方政府、事業(yè)單位、企業(yè)等紛紛開通官方微博的動作不難看出微博在當前網(wǎng)絡輿論中的重要地位。微博的崛起使得輿論陣地逐漸的從各大貼吧、論壇轉向微博。對政府而言，第一時間掌握網(wǎng)絡上的各種輿論消息，并及時疏通、引導和處理是十分重要的。

目前市場上的各種輿情監(jiān)測系統(tǒng)都是針對傳統(tǒng)社交網(wǎng)絡的，針對微博的非常少。這是因為微博出現(xiàn)的時間較短，研究較少，加上微博數(shù)據(jù)獲取存在不小的技術障礙，所以要對微博進行自動化的輿情監(jiān)測還比較困難。但近幾年的很多輿情大事件都由微博首先爆料并迅速發(fā)酵，所以對微博進行輿情監(jiān)測是必不可少的。為解決這一問題，本文對此展開了深入的研究，并較好地解決了微博輿情監(jiān)測中的一些難點問題。

傳統(tǒng)網(wǎng)絡輿情監(jiān)測系統(tǒng)的工作流程大致如下：首先從被監(jiān)測社交網(wǎng)絡平臺上不斷抓取數(shù)據(jù)；然后對數(shù)據(jù)進行統(tǒng)計分析；最后對分析結果進行評判，形成輿情報告。和傳統(tǒng)的社交平臺不同，微博(包括新浪、騰訊、搜狐、網(wǎng)易等主流微博)上的數(shù)據(jù)抓取是非常困難的。普通的網(wǎng)絡爬蟲在獲取網(wǎng)頁數(shù)據(jù)時，首先會檢查該網(wǎng)站根目錄下的Robots.txt文件，按照該文件的要求來抓取網(wǎng)頁，這些被抓取的網(wǎng)頁必須以靜態(tài)的文件形式存在[2-3]。一般的網(wǎng)站為了被搜索引擎檢索，會專門為爬蟲提供一套靜態(tài)文件。而以新浪為首的微博網(wǎng)站均未提供靜態(tài)數(shù)據(jù)(這可能是與微博數(shù)據(jù)更新太快有關，系統(tǒng)同時提供動態(tài)和靜態(tài)2套數(shù)據(jù)負擔太大，也很難同步)，所以正常的網(wǎng)絡爬蟲無法獲取微博中的數(shù)據(jù)。目前谷歌、必應、搜狗、即刻搜索等商業(yè)搜索引擎都無法提供微博數(shù)據(jù)搜索服務；唯一能提供微博數(shù)據(jù)的是百度，但它所提供的微博數(shù)據(jù)是向微博運營商購買的，時效性并不太好。

由于以上原因，微博數(shù)據(jù)的獲取成為了微博輿情監(jiān)測的一個難點。要解決這一問題，有3種思路：(1)利用系統(tǒng)提供的推送功能來獲取用戶所發(fā)表的微博。推送功能是所有的微博運營商都提供的一項功能：用戶只要注冊為微博用戶并稱為其他用戶的粉絲，當用戶登錄微博之后，那些被關注的用戶所最新發(fā)表的微博就會有選擇地被推送到該用戶的首頁上。(2)利用微博平臺提供的API接口來完成這項工作[4]。(3)如同網(wǎng)絡爬蟲的基本思路一樣，對獲取的網(wǎng)頁信息進行分析，從中發(fā)現(xiàn)新的鏈接，然后再從新的鏈接處獲取新的信息。

以上3種算法各有優(yōu)劣。第(1)種算法只適合小規(guī)模的數(shù)據(jù)抓取，其優(yōu)勢在于信息獲取的效率較高，實現(xiàn)起來也比較容易；缺點是系統(tǒng)對單一用戶關注的人數(shù)和推送的微博條數(shù)都有限制，若想全面獲取微博上的新數(shù)據(jù)，需要大量的手工勞動(即注冊多個用戶名，并為每個用戶添加大量的關注對象)，另外無法即時獲知新注冊的用戶。第(2)種算法能及時獲取有效數(shù)據(jù)，但在獲取的速度、調用次數(shù)、Oauth2.0過期時間等多方面都有諸多限制[4]；并且不同的微博平臺提供的API不一樣，如新浪微博與騰訊微博所提供的API不同，所以該算法的通用性不強。第(3)種算法最為靈活，但實現(xiàn)難度比較大，目前還沒有成熟的解決方案。為此，本文提出了模擬登錄來抓取網(wǎng)頁、并通過微博之間的關系來發(fā)現(xiàn)新用戶的算法。

2 單個微博網(wǎng)頁數(shù)據(jù)的獲取

通過對上述3種算法的分析，可見如果能解決單個微博網(wǎng)頁的抓取問題，那么就能采用同樣的算法抓取微博上其他用戶的網(wǎng)頁，再輔以一定的用戶發(fā)現(xiàn)和合適的數(shù)據(jù)抓取策略，就能完成整個微博數(shù)據(jù)的抓取，因此，第3種算法是最有前景的方案。

由于目前的微博系統(tǒng)都需要用戶登錄才能瀏覽，采用模擬瀏覽器向服務器發(fā)送數(shù)據(jù)包的方式模擬登錄，然后通過請求數(shù)據(jù)的方式來實現(xiàn)單個微博網(wǎng)頁信息的獲取。這種算法所受限制較少，可以比較自由地采集數(shù)據(jù)。該算法的基本過程如下：

(1)利用cookie來實現(xiàn)微博的身份認證(即登錄，cookie定義于RFC2109中，是為了辨別用戶身份而儲存在用戶本地終端上的數(shù)據(jù))[3]。

(2)將cookie添加到請求網(wǎng)頁的數(shù)據(jù)包的頭部。

(3)將構造的數(shù)據(jù)包通過HTTP協(xié)議發(fā)送給服務器，然后接收服務器的反饋信息。

通過上述3步就能實現(xiàn)完成單個網(wǎng)頁的抓取(其中有些具體的技術障礙需要克服，限于篇幅在此不展開論述)。使用Java編制了模擬登錄程序，順利地完成了單個網(wǎng)頁抓取任務。

在解決單個網(wǎng)頁數(shù)據(jù)獲取的問題之后，為完成整個微博數(shù)據(jù)的抓取需要制定合適的抓取策略。這里有2個最主要的問題需要解決：

(1)新用戶的發(fā)現(xiàn)。因為本文編制的爬蟲預先并不知道微博中有哪些用戶存在，需要有一種算法自動獲得這些用戶的有關信息。

(2)不同微博用戶的活躍程度不一樣，怎樣能獲取到最新的、最有價值的微博數(shù)據(jù)。

對于問題(1)，通過構建微博用戶網(wǎng)絡加以解決。對于問題(2)，采用優(yōu)先隊列來加以解決。

3 微博用戶網(wǎng)絡的構建

定義 一個圖G是一個有序三元組G=＜V,E,?＞，其中，V是非空頂點的集合；E是邊的集合，且E和V交集為空；?是E到V中某2個頂點的映射[5]。當圖中的邊具有權值時，這種帶權的圖稱為網(wǎng)，如圖1所示。

圖1 頂點和邊構成的網(wǎng)絡

和網(wǎng)絡爬蟲的工作原理一樣，可以通過某一個微博用戶頁面上的鏈接來不斷地挖掘新的微博用戶，然后訪問新的用戶，如此重復，就能形成一個微博用戶網(wǎng)絡。在這個網(wǎng)絡中，以微博用戶為頂點，用戶與用戶之間的關系作為邊，邊上的權值是用戶關系的一種量化，這樣就能構建出微博用戶網(wǎng)絡，并能通過這個網(wǎng)絡發(fā)現(xiàn)新微博用戶[6]。在微博中，活躍用戶(后文中有解釋)與其他用戶的聯(lián)系比較多，在所構造的微博用戶網(wǎng)絡中表現(xiàn)為該頂點的度相對比較大；反之，如果某個頂點的度相對較小甚至為0，那么表示該頂點對應的用戶在微博上不活躍，即僵尸粉。

假定：任何一個微博系統(tǒng)中的絕大多數(shù)正常用戶之間都存在直接或者間接聯(lián)系，也即他們在同一個連通分量g 中[5]。通過遍歷這個連通分量可以找到絕大多數(shù)的正常用戶。僵尸粉對應的是孤立節(jié)點k，無法通過g找到該孤立節(jié)點k；同樣，k節(jié)點所產生的信息也無法通過聯(lián)通分量g傳播出去。因此，類似k這樣的點是不能產生或傳播信息的。因為這類用戶在輿情系統(tǒng)中沒有多少研究價值，所以可以忽略掉那部分未處于用戶網(wǎng)絡中的用戶。

在這個用戶網(wǎng)絡中，用戶之間的關系用邊來描述。由于每種關系的重要程度不一樣，因此選擇用向量V= ＜A,D,R,C>來表示，向量V中的每個分量分別代表一種關系的權值。微博用戶之間的關系主要有4種：(1)關注：當A 對B感興趣時，可以關注B，這樣B所發(fā)表的微博就能自動地顯示在A的主頁上，用字母A來表示，其權值為固定值。(2)被關注：即表示粉絲，其意思和關注相反，A關注B，那么A稱為B的粉絲，用字母D來表示，其權值為固定值。(3)引用：即轉發(fā)某人發(fā)表的微博，用字母R來表示，引用次數(shù)即為對應的權值。(4)評論：對某人發(fā)表的微博加以評論，用字母C來表示，評論次數(shù)即為對應的權值。這幾種關系因用途不同而擁有不同的權值，所以需要分別記錄，在做數(shù)據(jù)挖掘時這些權值有很大的作用。

和一般的靜態(tài)網(wǎng)絡不同，這個用戶網(wǎng)絡是一個動態(tài)的網(wǎng)絡，它需要在網(wǎng)絡遍歷的過程中不斷加入新頂點，采用的算法如下：

Step1隨機選取一頂點為種子。

Step2抓取該頂點URL的網(wǎng)頁內容，并分析其內容，提取其中的鏈接，將其放入隊列l(wèi)inkQueue中。

Step3linkQueue中是否還有鏈接，如果有，轉Step4；否則轉Step5。

Step4檢查該鏈接是否為微博用戶，如果是，轉Step6；否則轉Step3。

Step5分析該網(wǎng)頁內容是否有微博，如果有，將微博存入數(shù)據(jù)庫，轉Step9；如果沒有，轉Step9。

Step6檢查該用戶是否已經在網(wǎng)絡中存在，如果存在，轉Step7；否則轉Step8。

Step7根據(jù)鏈接的性質，修改其權值向量中的對應分量，然后轉Step3。

Step8在這兩點之間建立新的邊，并賦上相應的權值，再轉到Step3。

Step9判斷網(wǎng)絡中是否還有未訪問的點，如果有，進入下一頂點，轉Step2；否則轉Step1。

因為新用戶的加入過程是永遠不會終止的，所以該算法是一個無限循環(huán)。通過上述算法，就能不斷地擴充微博用戶網(wǎng)絡，從而能抓取到微博上絕大部分的正常用戶。一般靜態(tài)網(wǎng)絡的訪問有深度優(yōu)先遍歷和廣度優(yōu)先遍歷[7]。根據(jù)用戶網(wǎng)絡的實際情況，選取廣度遍歷算法來訪問該用戶網(wǎng)絡。

在不斷擴充網(wǎng)絡的同時，還需要將這些微博用戶按照一定的規(guī)則放到隊列中。如果發(fā)現(xiàn)的是新用戶，則放入新用戶隊列。對于每個用戶，都用唯一的一個數(shù)字表示。這樣用二分法查找很快能確定該用戶是否訪問過。對于任何一個新用戶，一旦被訪問一次之后，即變?yōu)槔嫌脩?，按照預先確定的規(guī)則放入另外一個專用于存放老用戶的優(yōu)先隊列。

考慮到算法的通用性，采用單線程來訪問這2個不同的隊列。為了能并行地訪問這2個隊列，采用按照比例訪問的算法，即在新隊列中訪問了n個用戶之后，就在老用戶隊列中訪問k×n個用戶。在實驗中，n和k分別取值為1 和100。

新用戶隊列的建立和訪問都比較簡單，有很成熟的算法，在此略過。

4 優(yōu)先隊列的構建以及優(yōu)先級的計算模型

由于微博用戶數(shù)目十分龐大，為及時更新微博數(shù)據(jù)，因此需要在帶寬、時間均有限的條件下盡量獲取有質量的數(shù)據(jù)。所謂有質量的數(shù)據(jù)有2種：(1)內容上具有爆炸性或者與普通網(wǎng)民利益密切相關，能迅速吸引網(wǎng)民的注意。例如7.23動車事故、轉基因的爭論等。(2)擁有龐大粉絲數(shù)的用戶所發(fā)的每條微博都能被大量粉絲看到，也極易被轉發(fā)。這2類信息的共同點是容易吸引網(wǎng)民注意，并迅速傳播從而形成網(wǎng)絡輿情。所以，針對整個微博網(wǎng)絡上的信息，更關注那些被用戶轉發(fā)、評論的次數(shù)多的數(shù)據(jù)。

在保證數(shù)據(jù)質量的前提下還要盡量抓取更多的數(shù)據(jù)，這就需要對不同用戶采用不一樣的訪問頻率，本文選擇了優(yōu)先隊列。因為可以通過優(yōu)先隊列中的優(yōu)先級來控制出隊的順序。

4.1 優(yōu)先隊列

隊列即先進先出(first in first out)線性表，只允許在隊尾添加數(shù)據(jù)，在頭部刪除數(shù)據(jù)。優(yōu)先隊列是隊列的一種擴展，它將隊列中的元素賦予不同的優(yōu)先級，然后按照優(yōu)先級次序出隊列。優(yōu)先隊列的計算算法有基于binary heaps的改進算法[8]、基于reduce number of comparison的算法[9]、基于self-adjust的算法[10]、基于double-ended的算法[11]和基于Distribution se nsitive的算法[12]等。按照優(yōu)先權值的大小不同，分為最小優(yōu)先隊列和最大優(yōu)先隊列，本文選擇的是最大優(yōu)先隊列。能否達到預期的抓取效果，其關鍵在于隊列中優(yōu)先級的設計是否合適。而優(yōu)先級的設計需要從實際情況來考慮各方面的因素，并且不斷地調整各個因素所占的比重，以達到期望的效果。

4.2 優(yōu)先級的計算模型

顯而易見，對于內容相同的微博，影響力[13]越大的用戶所發(fā)表的微博產生的影響也越廣泛。新浪微博對用戶影響力的定義如下：衡量一個用戶在微博中影響力的大小，可以通過該賬號的發(fā)微博情況、被評論、轉發(fā)的情況以及活躍粉絲的數(shù)量來綜合評定，其公式如下：

其中，X為用戶的影響力；H表示活躍度；C是傳播力；F表示覆蓋度。活躍度代表該賬號每天主動發(fā)微博、轉發(fā)、評論的有效條數(shù)；傳播力與該賬號的微博被轉發(fā)、被評論的有效條數(shù)和有效人數(shù)相關；覆蓋度的高低則取決于該賬號微博的活躍粉絲數(shù)的多少[14]；wi為權重，其和為1。

根據(jù)式(1)，在設計優(yōu)先級計算公式時主要考慮以下因素：(1)微博用戶的粉絲數(shù)目。(2)發(fā)言量，指發(fā)表、評論、轉發(fā)微博的有效條數(shù)。(3)傳播力，為微博被轉發(fā)、評論的次數(shù)。(4)關注其他用戶的數(shù)目。(5)時間間隔，表示距離上次抓取的時間，這個是為防止優(yōu)先級較小的用戶沒機會被抓取。

將優(yōu)先級分為2類，除了時間因素外的其他數(shù)值的和稱為活躍值；時間因素需要單獨考慮。下面是優(yōu)先級的計算公式：

其中，Y為該用戶最終的優(yōu)先級值；F為粉絲數(shù)；H為發(fā)言量；C為傳播力；G為關注數(shù)；T為抓取該用戶的時間間隔。

4.2.1 粉絲數(shù)

在新浪微博中，粉絲的數(shù)量是相差較大的，一些人的粉絲能到千萬級，而有些人的粉絲數(shù)目只有幾個，兩者之間的數(shù)值相差較大，離散程度很高，數(shù)據(jù)的可比性不強。對粉絲數(shù)取對數(shù)，減少兩者之間的離散程度，具體計算公式如下：

其中，F(xiàn)表示該用戶的粉絲值；f為該用戶所擁有的粉絲數(shù)目；n表示從眾多用戶中隨機選取的n個用戶；fj是第j個用戶的粉絲數(shù)目。如果真數(shù)為0，則將其變?yōu)?，這樣變換對后面計算影響非常小。

4.2.2 發(fā)言量

發(fā)言量為用戶在一段時間內所發(fā)表、評論、轉發(fā)的微博條數(shù)，其計算公式如下：

其中，hi表示第i個用戶在最近一段時間內平均每天所發(fā)表、評論、轉發(fā)的微博數(shù)目；H是第i個用戶的發(fā)言量，隨機選擇的n個用戶，對其平均一天發(fā)表、評論、轉發(fā)微博條數(shù)取平均。hi的計算公式如下：

其中，N為固定值，表示所發(fā)表、轉發(fā)、評論微博的數(shù)目；Te表示最后一條微博發(fā)表的時間；Ts表示最初發(fā)表時間。

4.2.3 傳播力

因為輿情在很大程度上是因傳播而形成，所以傳播力是本文計算的重點。在微博中，傳播力主要由微博的轉發(fā)和評論來決定。其計算公式如下：

其中，C表示用戶的傳播力；a表示a條最新微博；cm則是該用戶所發(fā)表的第m條微博的轉發(fā)數(shù)目；cn則為該用戶所發(fā)表的第n條微博的評論數(shù)目；wf和wc為轉發(fā)數(shù)目與評論數(shù)的權重，其和為1；Cforword是隨機選取n個人所求的平均轉發(fā)數(shù)目；Ccomment即平均的評論數(shù)目，其計算公式如下：

其中，cij表示第j個人的第i條微博的轉發(fā)數(shù)。Ccomment的計算公式和式(7)相同，只是其中的cij表示的是第j個人的第i條微博的評論數(shù)。

4.2.4 關注數(shù)

G代表用戶所關注的其他用戶的數(shù)目，其計算公式與式(3)類似，如下：

其中，gj表示第j個用戶所關注的人數(shù)；n表示從眾多用戶中隨機選取的n個用戶。

4.2.5 時間間隔

時間間隔是為那些影響力較小的用戶而設計的。在待抓取的優(yōu)先隊列中，當優(yōu)先級最高的元素出隊列之后，會重新計算其優(yōu)先級，然后再加入到隊列中，由于其優(yōu)先級較高，因此插入的位置會比較靠前，從而導致隊列后面的元素沒有機會移動到隊頭。為防止這種情況出現(xiàn)，引入了時間間隔這個因子來降低高優(yōu)先級元素的優(yōu)先級值。其計算公式如下：

其中，j表示抓取該用戶的第j次；k為權值。y是前文中提到的活躍值，是粉絲數(shù)、關注數(shù)、發(fā)言量和傳播力的綜合體現(xiàn)，其計算公式為：

而Ys是隨機選取n個樣本并計算其y值然后求平均得到的平均值。J為一常數(shù)，表示連續(xù)計算的最大次數(shù)，當j的值不小于J時，就將其歸零。

以上就是各個因子對優(yōu)先級的影響以及計算公式。至于系數(shù)的確定，主要通過邏輯推理和多次實驗來確定。最終得到如表1所示的權值表。

表1 權重的取值

優(yōu)先級的大小主要從粉絲值、發(fā)言量、傳播力、關注值4個方面來考慮；同時為防止隊列中影響力小的用戶沒有被抓取的機會，又輔以時間間隔這個因素來定時調節(jié)隊列中靠后的用戶。這樣就在保證數(shù)據(jù)質量的情況下抓取更多數(shù)據(jù)。

5 實驗結果

在采集速度方面，新浪微博API和模擬瀏覽器登錄抓取有較大的差別，表2是以上2種算法的實驗結果。

表2 2種采集方式的性能對比

從表2中可以看出，模擬瀏覽器登錄抓取的算法在采集用戶上有較大的優(yōu)勢。具體原因是新浪微博API的限制，每個用戶最多每小時爬取150次。模擬瀏覽器算法的速度瓶頸在于新浪微博對IP的限制，每個小時最多只允許同一個IP訪問1 000次。

根據(jù)以上算法設計了Java程序，在一臺普通PC機連續(xù)運行12 h，以新浪微博的大V用戶李開復為種子開始，共抓取了10 043個用戶的數(shù)據(jù)，獲取了92 363條微博，并同時發(fā)現(xiàn)了2 000 115個新的微博用戶。將這些已抓取的用戶按照式(10)計算其活躍值。將用戶按照活躍值的大小劃分為4個等級，分別是非?；钴S、比較活躍、一般活躍、不活躍，其活躍值的范圍如表3所示。

表3 微博用戶按活躍值的分類

在表3中，Avg是隨機選取的N個樣本，然后按照式(10)計算出的活躍值再取平均的值。從實驗結果來看，非常活躍的用戶大概200個左右，占總人數(shù)的2%，計算出最高值是32.384 5；這些人擁有如下特點：(1)粉絲比較多，通常在千萬級以上；(2)發(fā)表的微博多，平均一天有5條以上的微博。(3)微博被轉發(fā)評論的次數(shù)也很多，平均都在千次左右。而較活躍的用戶則相對較多，達到1 400人左右，占總人數(shù)的14%，這部分人的粉絲在百萬級別，發(fā)表的微博也比較多，但這些微博被轉發(fā)、評論的次數(shù)則明顯較小，一般在1 000以內。一般活躍的用戶則更多，約有2 600人，占總人數(shù)的26%左右，這部分用戶的粉絲數(shù)大多在一萬到十萬之間，并且評論、轉發(fā)別人的微博相對較多，而原創(chuàng)的相對較少，并且這些原創(chuàng)的微博被轉發(fā)、評論的次數(shù)相當小，都在100以內。最后一部分用戶最多，大約6 000人，這部分人基本上就是所謂的僵尸粉，即發(fā)表、轉發(fā)、評論的微博數(shù)目都很少，幾乎為0。

優(yōu)先隊列的抓取方式在數(shù)據(jù)質量上有比較大的改進，實驗結果如表4所示。

表4 非優(yōu)先和優(yōu)先的性能對比

從表4中可以看出，優(yōu)先隊列非常適合于采集頻率不同的情況，實驗結果說明同優(yōu)先級的計算模型比較成功，能在相同條件下抓取更多有質量的數(shù)據(jù)。

6 結束語

本文主要介紹如何靈活地抓取微博數(shù)據(jù)，并在一定時間內更新具有較大影響力用戶的數(shù)據(jù)，重點分析了微博用戶網(wǎng)絡的構建過程以及更新數(shù)據(jù)時需要用到的優(yōu)先隊列算法，并對其優(yōu)先級的設計進行了詳細闡述。從實驗結果可以發(fā)現(xiàn)：(1)這種算法能不斷發(fā)現(xiàn)新用戶，并抓取該用戶的有用信息，是一種行之有效的算法；(2)優(yōu)先隊列的優(yōu)先級的設計比較合理，獲取的數(shù)據(jù)質量較高，即時性比傳統(tǒng)算法的性能更好，能較好地適應輿情網(wǎng)絡監(jiān)測的要求。但是該算法還有很多值得研究的地方。比如，在構建用戶網(wǎng)絡時，如何來降低存儲空間的需求；對于影響力不大的用戶，是否更好的更新方式。另外算法設計時只考慮了單機單線程的情況，而在實際應用中，需要將其并行化處理來加快速度。這些問題都是后續(xù)研究的重點。

[1] 新華網(wǎng). 新浪微博用戶數(shù)超5億[EB/OL]. (20 13-02-21). http://news.xinhuanet.com/newmedia/2013-02/21/c_12436989 6.htm.

[2] 新浪網(wǎng). 新浪微博API開放平臺[EB/OL]. (2013-0 3-12). http://open.t.sina.com.cn/wiki/index.hph.

[3] 李曉明, 閆宏飛, 王繼民. 搜索引擎: 原理, 技術與系統(tǒng)[M]. 北京: 科學出版社, 2005.

[4] 周立柱, 林 玲. 聚焦爬蟲技術研究綜述[J]. 計算機應用, 2005, 25(9): 1965-1969.

[5] 劉任任. 離散數(shù)學[M]. 2版. 長沙: 湖南科學技術大學出版社, 2001.

[6] 戴月卿, 鐘 玲, 林柏鋼, 等. 基于微博的人物關系網(wǎng)絡挖掘系統(tǒng)[J]. 信息網(wǎng)絡安全, 2013, (2): 83-86.

[7] 嚴蔚敏, 吳偉民. 數(shù)據(jù)結構[M]. 北京: 清華大學出版社, 2009.

[8] Liu Y ujie, Spear M. A Lock-f ree, Ar ray-based Pr iority Queue[J]. ACM SIGPLAN Notices, 2012, 47(8): 323-324.

[9] Elmasry A, Jens en C, Kat ajainen J. M ultipartite Pri ority Queues[J]. ACM Transactions o n Algorithms, 2008, 5(1): 1-19.

[10] Elmasry A. Pairing Heaps with Costless M eld[M]. B erlin, Germany: Springer, 2010.

[11] Cho S, Sahni S. Mer geable Double-ended Priority Queues[J]. International Journal of Foundations of Comp uter Science, 1999, 10(1): 1-17.

[12] Elmasry A, Farzan A, Iacono J. A Priority Queue with the Time-finger Property[J]. Journal of Discrete Algorithms, 2012, 16(1): 206-212.

[13] 于 洪, 楊 顯. 微博中節(jié)點影響力度量與傳播路徑模式研究[J]. 通信學報, 2012, 33(Z2): 97-102.

[14] 新浪網(wǎng). 新浪微博中影響力的定義[EB/OL]. (2013-03-1 2). http://data.weibo.com/top/help.

編輯 任吉慧

Universal Crawling Algorithm for Microblogging Data

LU Ti-guang, LIU Xin, LIU Ren-ren

(Key Laboratory of Intelligent Computing and Information Processing, Ministry of Education, Institute of Information Engineering, Xiangtan University, Xiangtan 411105, China)

Currently, Web crawler and microblog API which are used to grab data f rom the microblog are difficult to satisfy the public opinion system demands for microblog data. To settle the problem, this paper presents a feasible solution which is the similar as the browser login microblog to capture data from Web p ages. It can easily get all data from any microblog users. On this basis, it construc ts a microblogging network through interconnections among users, and discovers new users through it. In order to get high quality data, it builds mathematical models to calculate the user’s influence index by using posting number, posting frequency, fans number, forwarding number and comments number. Moreover, it builds priority queue according to the calculated influence factor, which let those that have bigger influence index have high acquisition frequency. Finally, it calculates time interval to balance the lower frequency of non-active microblog user. The experimental results sh ow that this method not only processes easily and has higher speed but also can o btain high qu ality information and have huge versatility.

microblogging data; analog login; user network; user influence; Internet public opinion; priority queue

10.3969/j.issn.1000-3428.2014.05.003

湖南省自然科學基金資助項目(12JJ3066)；湖南省高校科技成果產業(yè)化培育基金資助項目(11CY018)；湖南省重點學科基金資助項目。

盧體廣(1988－)，男，碩士研究生，主研方向：社會計算，信息安全；劉 新，副教授；劉任任，教授、博士生導師。

2013-10-31

2014-01-27E-mail：lutiguang7@163.com

1000-3428(2014)05-0012-05

A

TP311.13