盧體廣，劉 新，劉任任

(湘潭大學(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)對(duì)微博數(shù)據(jù)的需求。為此，提出一種模擬瀏覽器登錄微博抓取網(wǎng)頁(yè)數(shù)據(jù)的算法，以方便地獲取任意微博用戶網(wǎng)頁(yè)上的所有數(shù)據(jù)。通過(guò)微博用戶之間的關(guān)系構(gòu)建用戶網(wǎng)絡(luò)，并通過(guò)該網(wǎng)絡(luò)發(fā)現(xiàn)新用戶。為獲取微博上有質(zhì)量的數(shù)據(jù)，建立一個(gè)完整的數(shù)學(xué)模型，根據(jù)用戶的發(fā)帖數(shù)、發(fā)帖頻率、粉絲數(shù)、轉(zhuǎn)發(fā)數(shù)、評(píng)論數(shù)等因素來(lái)計(jì)算用戶影響力，以影響力為主要因子構(gòu)建優(yōu)先隊(duì)列，使得影響力越大的用戶數(shù)據(jù)采集頻率越高，同時(shí)計(jì)算時(shí)間間隔以兼顧非活躍用戶的數(shù)據(jù)獲取。實(shí)驗(yàn)結(jié)果表明，該算法具有通用性強(qiáng)、完全無(wú)需人工干預(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)注。近幾年來(lái)，微博用戶呈現(xiàn)出幾何式的增長(zhǎng)(如新浪微博的用戶已經(jīng)超5億[1])，為輿論的產(chǎn)生和傳播提供了良好的平臺(tái)。從近期各級(jí)地方政府、事業(yè)單位、企業(yè)等紛紛開通官方微博的動(dòng)作不難看出微博在當(dāng)前網(wǎng)絡(luò)輿論中的重要地位。微博的崛起使得輿論陣地逐漸的從各大貼吧、論壇轉(zhuǎn)向微博。對(duì)政府而言，第一時(shí)間掌握網(wǎng)絡(luò)上的各種輿論消息，并及時(shí)疏通、引導(dǎo)和處理是十分重要的。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Step2抓取該頂點(diǎn)URL的網(wǎng)頁(yè)內(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)頁(yè)內(nèi)容是否有微博，如果有，將微博存入數(shù)據(jù)庫(kù)，轉(zhuǎn)Step9；如果沒(méi)有，轉(zhuǎn)Step9。

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

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

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

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

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

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

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

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

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

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

在保證數(shù)據(jù)質(zhì)量的前提下還要盡量抓取更多的數(shù)據(jù)，這就需要對(duì)不同用戶采用不一樣的訪問(wèn)頻率，本文選擇了優(yōu)先隊(duì)列。因?yàn)榭梢酝ㄟ^(guò)優(yōu)先隊(duì)列中的優(yōu)先級(jí)來(lái)控制出隊(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)先級(jí)，然后按照優(yōu)先級(jí)次序出隊(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)先級(jí)的設(shè)計(jì)是否合適。而優(yōu)先級(jí)的設(shè)計(jì)需要從實(shí)際情況來(lái)考慮各方面的因素，并且不斷地調(diào)整各個(gè)因素所占的比重，以達(dá)到期望的效果。

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

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

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

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

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

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

4.2.1 粉絲數(shù)

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

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

4.2.2 發(fā)言量

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

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

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

4.2.3 傳播力

因?yàn)檩浨樵诤艽蟪潭壬鲜且騻鞑ザ纬桑詡鞑チκ潜疚挠?jì)算的重點(diǎn)。在微博中，傳播力主要由微博的轉(zhuǎn)發(fā)和評(píng)論來(lái)決定。其計(jì)算公式如下：

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

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

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

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

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

4.2.5 時(shí)間間隔

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

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

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

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

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

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

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

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

表2 2種采集方式的性能對(duì)比

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

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

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

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

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

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

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

6 結(jié)束語(yǔ)

本文主要介紹如何靈活地抓取微博數(shù)據(jù)，并在一定時(shí)間內(nèi)更新具有較大影響力用戶的數(shù)據(jù)，重點(diǎn)分析了微博用戶網(wǎng)絡(luò)的構(gòu)建過(guò)程以及更新數(shù)據(jù)時(shí)需要用到的優(yōu)先隊(duì)列算法，并對(duì)其優(yōu)先級(jí)的設(shè)計(jì)進(jìn)行了詳細(xì)闡述。從實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)：(1)這種算法能不斷發(fā)現(xiàn)新用戶，并抓取該用戶的有用信息，是一種行之有效的算法；(2)優(yōu)先隊(duì)列的優(yōu)先級(jí)的設(shè)計(jì)比較合理，獲取的數(shù)據(jù)質(zhì)量較高，即時(shí)性比傳統(tǒng)算法的性能更好，能較好地適應(yīng)輿情網(wǎng)絡(luò)監(jiān)測(cè)的要求。但是該算法還有很多值得研究的地方。比如，在構(gòu)建用戶網(wǎng)絡(luò)時(shí)，如何來(lái)降低存儲(chǔ)空間的需求；對(duì)于影響力不大的用戶，是否更好的更新方式。另外算法設(shè)計(jì)時(shí)只考慮了單機(jī)單線程的情況，而在實(shí)際應(yīng)用中，需要將其并行化處理來(lái)加快速度。這些問(wèn)題都是后續(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開放平臺(tái)[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版. 長(zhǎng)沙: 湖南科學(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－)，男，碩士研究生，主研方向：社會(huì)計(jì)算，信息安全；劉 新，副教授；劉任任，教授、博士生導(dǎo)師。

2013-10-31

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

1000-3428(2014)05-0012-05

A

TP311.13