微博數據通用抓取算法

盧體廣，劉 新，劉任任

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

微博數據通用抓取算法

盧體廣，劉 新，劉任任

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

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

微博數據；模擬登錄；用戶網絡；用戶影響力；網絡輿情；優先隊列

1 概述

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

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

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

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

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

2 單個微博網頁數據的獲取

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

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

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

(2)將cookie添加到請求網頁的數據包的頭部。

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

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

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

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

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

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

3 微博用戶網絡的構建

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

圖1 頂點和邊構成的網絡

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

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

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

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

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

Step2抓取該頂點URL的網頁內容，并分析其內容，提取其中的鏈接，將其放入隊列linkQueue中。

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

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

Step5分析該網頁內容是否有微博，如果有，將微博存入數據庫，轉Step9；如果沒有，轉Step9。

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

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

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

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

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

在不斷擴充網絡的同時，還需要將這些微博用戶按照一定的規則放到隊列中。如果發現的是新用戶，則放入新用戶隊列。對于每個用戶，都用唯一的一個數字表示。這樣用二分法查找很快能確定該用戶是否訪問過。對于任何一個新用戶，一旦被訪問一次之后，即變為老用戶，按照預先確定的規則放入另外一個專用于存放老用戶的優先隊列。

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

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

4 優先隊列的構建以及優先級的計算模型

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

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

4.1 優先隊列

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

4.2 優先級的計算模型

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

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

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

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

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

4.2.1 粉絲數

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

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

4.2.2 發言量

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

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

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

4.2.3 傳播力

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

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

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

4.2.4 關注數

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

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

4.2.5 時間間隔

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

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

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

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

表1 權重的取值

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

5 實驗結果

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

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

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

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

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

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

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

表4 非優先和優先的性能對比

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

6 結束語

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

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

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

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

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

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

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

[7] 嚴蔚敏, 吳偉民. 數據結構[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] 于 洪, 楊 顯. 微博中節點影響力度量與傳播路徑模式研究[J]. 通信學報, 2012, 33(Z2): 97-102.

[14] 新浪網. 新浪微博中影響力的定義[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)；湖南省高校科技成果產業化培育基金資助項目(11CY018)；湖南省重點學科基金資助項目。

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

2013-10-31

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

1000-3428(2014)05-0012-05

A

TP311.13