盧體廣，劉 新，劉任任

(湘潭大學(xué)信息工程學(xué)院智能計(jì)算與信息處理教育部重點(diǎn)實(shí)驗(yàn)室，湖南 湘潭 4 11105)

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

盧體廣，劉 新，劉任任

(湘潭大學(xué)信息工程學(xué)院智能計(jì)算與信息處理教育部重點(diǎn)實(shí)驗(yàn)室，湖南 湘潭 4 11105)

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

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

1 概述

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

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

傳統(tǒng)網(wǎng)絡(luò)輿情監(jiān)測系統(tǒng)的工作流程大致如下：首先從被監(jiān)測社交網(wǎng)絡(luò)平臺上不斷抓取數(shù)據(jù)；然后對數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析；最后對分析結(jié)果進(jìn)行評判，形成輿情報(bào)告。和傳統(tǒng)的社交平臺不同，微博(包括新浪、騰訊、搜狐、網(wǎng)易等主流微博)上的數(shù)據(jù)抓取是非常困難的。普通的網(wǎng)絡(luò)爬蟲在獲取網(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ù)更新太快有關(guān)，系統(tǒng)同時提供動態(tài)和靜態(tài)2套數(shù)據(jù)負(fù)擔(dān)太大，也很難同步)，所以正常的網(wǎng)絡(luò)爬蟲無法獲取微博中的數(shù)據(jù)。目前谷歌、必應(yīng)、搜狗、即刻搜索等商業(yè)搜索引擎都無法提供微博數(shù)據(jù)搜索服務(wù)；唯一能提供微博數(shù)據(jù)的是百度，但它所提供的微博數(shù)據(jù)是向微博運(yùn)營商購買的，時效性并不太好。

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

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

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

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

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

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

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

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

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

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

(1)新用戶的發(fā)現(xiàn)。因?yàn)楸疚木幹频呐老x預(yù)先并不知道微博中有哪些用戶存在，需要有一種算法自動獲得這些用戶的有關(guān)信息。

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

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

3 微博用戶網(wǎng)絡(luò)的構(gòu)建

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

圖1 頂點(diǎn)和邊構(gòu)成的網(wǎng)絡(luò)

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

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

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

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

Step1隨機(jī)選取一頂點(diǎn)為種子。

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

Step3linkQueue中是否還有鏈接，如果有，轉(zhuǎn)Step4；否則轉(zhuǎn)Step5。

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

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

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

Step7根據(jù)鏈接的性質(zhì)，修改其權(quán)值向量中的對應(yīng)分量，然后轉(zhuǎn)Step3。

Step8在這兩點(diǎn)之間建立新的邊，并賦上相應(yīng)的權(quán)值，再轉(zhuǎn)到Step3。

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

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

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

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

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

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

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

在保證數(shù)據(jù)質(zhì)量的前提下還要盡量抓取更多的數(shù)據(jù)，這就需要對不同用戶采用不一樣的訪問頻率，本文選擇了優(yōu)先隊(duì)列。因?yàn)榭梢酝ㄟ^優(yōu)先隊(duì)列中的優(yōu)先級來控制出隊(duì)的順序。

4.1 優(yōu)先隊(duì)列

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

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

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

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

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

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

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

4.2.1 粉絲數(shù)

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

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

4.2.2 發(fā)言量

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

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

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

4.2.3 傳播力

因?yàn)檩浨樵诤艽蟪潭壬鲜且騻鞑ザ纬?，所以傳播力是本文?jì)算的重點(diǎn)。在微博中，傳播力主要由微博的轉(zhuǎn)發(fā)和評論來決定。其計(jì)算公式如下：

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

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

4.2.4 關(guān)注數(shù)

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

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

4.2.5 時間間隔

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

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

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

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

表1 權(quán)重的取值

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

5 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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

[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] 李曉明, 閆宏飛, 王繼民. 搜索引擎: 原理, 技術(shù)與系統(tǒng)[M]. 北京: 科學(xué)出版社, 2005.

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

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

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

[7] 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu)[M]. 北京: 清華大學(xué)出版社, 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é)點(diǎn)影響力度量與傳播路徑模式研究[J]. 通信學(xué)報(bào), 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

湖南省自然科學(xué)基金資助項(xiàng)目(12JJ3066)；湖南省高?？萍汲晒a(chǎn)業(yè)化培育基金資助項(xiàng)目(11CY018)；湖南省重點(diǎn)學(xué)科基金資助項(xiàng)目。

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

2013-10-31

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

1000-3428(2014)05-0012-05

A

TP311.13