在線社交網絡的邏輯模型和并行查詢

李偉鋼，鄭建亞

（巴西利亞大學計算機系TransLab實驗室，巴西利亞70910- 900）

在線社交網絡的邏輯模型和并行查詢

李偉鋼，鄭建亞

（巴西利亞大學計算機系TransLab實驗室，巴西利亞70910- 900）

歸納出對在線社交網絡研究具有挑戰性的一些課題，介紹描述用戶關系的邏輯模型（粉絲模型），提出邏輯關系寓意鄰接矩陣（粉絲矩陣）。用此模型展示對微博平臺Top-X信息查詢的聚合-排序-刪除算法。進一步應用映射和化簡概念將上述Top-X信息查詢算法擴展于并行計算環境，給出映射關注和化簡粉絲在Hadoop系統聯機實現的算法。粉絲模型和相應的算法實現了對新浪微博74.7GB和Twitter的101GB實際數據的多種約束下信息查詢和微博轉發預測，特別是在Hadoop系統聯機環境下，新方法的信息化簡和計算性能明顯提高。

復雜網絡；平行算法；微博；信息查詢；映射和化簡；在線社交網絡

0 引言

在線社交網絡具有動態變化、在線即時、個性行為、異構互聯和大數據生成等特點。基于浩瀚網絡拓撲、海量數據處理、多重關系分析和信息傳播擴散等對其機制進行研究，面臨著理論建模和技術實踐的各項挑戰。國內外若干著名智能網絡、數據挖掘和復雜系統等研究中心，無不投入大量人力物力，從事這方面研究。

梳理新近文獻，發現對社交網絡信息傳播機制的研究離不開對圖論的完善以及數據挖掘的深入研究，同時還具有以下特點：Jiawei Han團隊等提出異構信息網絡理論，對大型信息技術文獻庫DBLP的論文引用和共同作者進行預測［1］。亞洲微軟Haixun Wang團隊提出10億節點巨型網絡子圖匹配的分布式優化算法，大大提高了網絡咨詢分析效率［2］。加州大學圣塔芭芭拉分校的Ben Y Zhao團隊注重在線網絡大尺度和多層次的動態特性，研究微博海量信息分布和傳播機制［3］。卡內基梅隆大學的C Faloutsos團隊在分析大規模網絡，使用云計算進行知識挖掘，完善圖論方法等方面的工作值得注目［4］。斯坦福大學J Leskovec團隊提出多元素、多關系的新型圖論模型，廣泛應用于多種網絡研究［5］。

國內不少學者和機構也在相關方面進行了卓有成效的研究。例如中國原子能科學研究院方錦清團隊近年來致力于推動社交網絡研究，對博客-微博網及其特點進行了全面闡述，并對在線社交網絡若干研究問題進行了展望［6］；清華大學唐杰團隊開發應用大型文獻庫并付諸于實［7］；華東師大周傲英團隊和四川大學唐常杰團隊在大數據和知識發現等方面的工作［8-9］；中科院程學旗團隊使用傳播動力學的方法來進行社區發現［10］并通過分布式計算來提高計算效率，等等。另外，一些物理學和數學方面的專家從復雜網絡系統角度，研究社交網絡相關模型，如中科大的汪秉宏團隊對復雜網絡博弈的研究［11］和電子科技大學周濤團隊對鏈路預測等的研究［12］，程代展團隊通過矩陣半張量積這一創新計算方法對一般邏輯網絡進行研究［13］，并利用演化博弈來對復雜網絡進行建模和分析，等等。2012年參加WISE新浪微博競賽的若干團隊［14-15］，也在信息查詢和轉發預測等方面，進行較全面的研究。

總的來看，當前對在線社交網絡的研究已取得了階段性成果，但實際上，在對在線社交網絡和其它復雜信息網絡機制研究時，人們往往采取拿來主義，即基于現有圖論衍生的網絡技術，注重計算技巧，缺乏理論研究。例如，新浪和騰訊等微博是網友在線社交平臺，用戶間的關系盤根交錯，極其復雜［16］。學術界對微博的研究方興未艾，迅速發展。上面提到的一些科技文獻，盡管成效顯著，但在網絡節點間關系和反映這些關系相互作用方面，來自數學、物理、生物和工程等領域的研究成果，尚無深刻描述和有效模型。尤其是對多層次用戶關系的微博轉發預測時，經典的鄰接矩陣定義和在此基礎上研發的數學模型，顯得單調，亟需跨學科理論和技術的交叉性研究。本文針對該問題，從以下兩方面進行建模研究：一是微博機制的用戶關系邏輯描述；二是微博信息查詢的高效平行算法。

以新浪微博平臺上信息查詢和知識挖掘為例［14-15］，數億條微博短信，幾千萬級的復雜的客戶關系數據，簡單的查詢都需要從海量數據中理清客戶關系。本文以多項約束條件下組合為切入點，得出合乎查詢要求的Top-X，如常說的前10名、前50或100名。初步研究可以分以下五類較復雜的組合：1）基于微博用戶的基本人際關系的組合查詢，如粉絲、關注人和互粉關系，可能涉及與一個或多個用戶；2）基于用戶間發生活動的組合查詢，例如發博、提及、評論或轉發等活動等，可能涉及與一個或多個活動；3）基于微博、提及、評論或轉發等文本的議題和相關社會事件等的組合查詢，可能涉及與一項或多項議題或事件；4）基于上述微博關系、活動或事件等的某時間段的組合查詢，此時間范圍可以是1小時、1天、1周或1年等等。對于這4項內容的任意或特殊的復雜組合查詢，考慮到微博用戶的關系復雜性、活動多項性、議題豐富性和事件突發性，以及時間間隔和海量數據等特征，可知微博用戶信息復雜組合查詢的表述和實現是非常艱巨的計算分析活動。

在上述文獻研讀基礎上，本文介紹描述用戶關系的邏輯模型，粉絲模型［12］，提出邏輯關系寓意鄰接矩陣（Relationship Committed Adjacency Matrix-RCAM，簡稱粉絲矩陣）。用此模型可以展示對微博平臺Top-X信息查詢的聚合-排序-刪除算法。并進一步應用映射和化簡［17］概念將上述Top-X信息查詢算法適用于并行計算環境，介紹映射關注，化簡粉絲算法和在Hadoop系統的聯機實現。在對新浪微博74.7GB和Twitter的101GB實際數據的查詢和微博轉發預測，Hadoop系統聯機環境下的新方法在信息存儲量化簡和計算能力等方面的性能明顯提高。

1 用戶關系邏輯模型

微博平臺上，最常見的社交關系是用戶間的關注關系。有一群人被稱為“博主”，也有一群人叫做“粉絲”。在這個社區內，如果用戶A關注B，稱A是B的粉，稱B是A的關注人。如果A是B的粉，B亦是A的粉，稱A和B為互粉關系。

在線社交網絡一般可以描述為有向圖：G=（V，E），這里圖的節點V表示用戶；節點間的有向連接為E：V×V，表示用戶間的關系。（A，B）∈E，表明用戶A關注用戶B，即，A是B的粉，B是A的關注人。

較正式的用戶關系數學描述［14］為：對于用戶間關系函數fin，fout，fr，V→V＊，有：

fout（A）=｛B｜（A，B）∈E｝，表示A 的關注人集函數，A關注B；

fin（B）=｛A｜（A，B）∈E｝，表示B的粉絲集函數，A 為B 的粉；

fr（A）=fout（A）∩fin（A），表示A的互粉集函數，A的關注人集合與關注A的粉絲集合之交集。

這些函數把微博用戶關系簡潔準確地描述出來，為便于分析和應用，暫將其稱為粉絲模型。該模型同時具備反對稱與對稱性、可擴展性和可組合性，使得傳統的圖論理論在微博機制分析上拓寬了新的邏輯關系表達模式。

1.1 反對稱與對稱性

從函數的對稱意義來看，可以定義其反函數。若f∈｛fin，fout，fr｝，有其反函數f′定義為

定理1 fin和fout互為反函數。

證明：對有向圖：G=（V，E），節點V表示用戶；節點間的有向連接為E：V×V，表示用戶間的關系。（A，B）∈E，表明用戶A關注用戶B，A是B的粉絲，B是A的關注人。有：

fout（A）=｛B｜（A，B）∈E｝，表示A 的關注人集函數，A關注B；

fin（A）=｛B｜（B，A）∈E｝，表示A 的粉絲集函數，B為A 的粉絲；

有反函數：（fout（A））′=（｛B｜（A，B）∈E｝）′=｛B｜（B，A）∈E｝=fin（A）；

有反函數：（fin（A））′=（｛B｜（B，A）∈E｝）′=｛B｜（A，B）∈E｝=fout（A）；

證得fin和fout互為反函數。

定理2 fr和fr自為反函數。

證明：對有向圖：G=（V，E），節點V 表示用戶；節點間的有向連接為E：V×V，表示用戶間的關系。（A，B）∈E，表明用戶A關注用戶B，A是B的粉絲，B是A的關注人。如果A是B的粉絲，B亦是A的粉絲，稱A和B為互粉關系，有：

fr（A）=fout（A）∩fin（A），表示A的互粉集函數，A的關注人集合與關注A的粉絲集合之并集。

其中，fout（A）=｛B｜（A，B）∈E｝，fin（A）=｛B｜（B，A）∈E｝，

證得fr自為反函數。

1.2 可擴展性

若f1，f2∈｛fin，fout，fr｝，對于用戶間關系函數f1，f2，V→V＊，則函數間的并集、交集計算為

這里如果f1，f2相同，并集計算有f·f=f2和進一步的f·fn-1=fn。例如，f2in（A）就是A的粉絲的粉絲的集函數；而fnr（A）就是A的互粉的互粉的……互粉的集函數。

對于交集計算，前述的互粉關系函數定義就是特例：fr（A）=fout（A）∩fin（A），這里f1=fout，f2=fin。

1.3 可組合性

考慮到進一步的操作性，這些函數間的組合可表達更多的用戶關系，實現相關計算。例如，fin·fout（A）是指A關注人的粉絲集函數，而f2in（A）就是A的粉絲的粉絲集函數。

有了對微博用戶關系邏輯描述的粉絲模型的函數定義和特性，具體問題的表達會更方便和實用。若以姚晨博友微博平臺的網友關系在線查詢為例，這些查詢提示可以較正式地用粉絲模型表示。

關注她的人同時關注了……，對應上述定義的微博用戶邏輯關系，是對foutfin（A）的求解，A在這里就是博主姚晨，函數集表示關注她的粉絲同時關注的網友。

這些人也關注她……，對應上述定義的微博用戶邏輯關系，是對fout（A）∩fin（B）的求解，這里的A是筆者，B是姚晨博主，就是說這個用戶集是筆者所關注的網友，同時也是姚晨的粉絲。

我和她都關注了……，對應上述定義的微博用戶邏輯關系，是對fout（A）∩fout（B）的求解，這里的A是筆者，B是明星姚晨。函數集表達我和她共同感興趣的網友。

2 用戶關系邏輯模型的鄰接矩陣表述

研究各類復雜網絡理論時，在高效率計算的意義下，用鄰接矩陣來表示網絡拓撲，是研究人員的基本選擇。隨著在線社交網絡的蓬勃發展和深入研究，尤其是在關系錯綜復雜的微博平臺內，還沒有對用戶各種行為和關系給予準確描述的貼切的數學模型，人們越來越感到直接使用鄰接矩陣的乏力。

基于粉絲模型［14］，注意到在線社交網絡用戶間的多重、多層的復雜關系和大網絡并行計算的潛力，這里進一步提出關系寓意鄰接矩陣概念，簡稱粉絲矩陣。按照粉絲模型的定義，Ain為粉絲鄰接矩陣，其轉置矩陣就是關注矩陣，具體表示為Aout=ATin。經過多次相乘，Akin=AinAin…Ain是k-階粉絲矩陣。如果把n個節點的社交網絡用n×n矩陣Ain表示，則通過A2in可查詢粉絲的粉絲信息；利用AinAout查詢關注人的粉絲信息；利用AoutAin查詢粉絲的關注人信息等等。

2.1 圖和鄰接矩陣的定義

為便于描述問題，按圖論來定義在線社交網絡的元素和關系。4個節點和連接構成一個簡單的無向圖G=（V，E），如圖1所示。節點集V 內有：A，B，C，D∈V；各節點內含一元素，這里指用戶名u，v，w 和x；節點間形成無向連接集E：V×V：（A，B），（A，D），（B，C），（B，D）和（C，D）∈E；用戶間可能的關系為：（u，v），（u，x），（v，w），（v，x）和（w，x）∈R。

在此定義里，節點和元素、連接和關系是有意分開的，因為網絡內的節點和連接一般是不變的，但在線社交網絡的元素和關系隨時會發生變化。例如，節點可能會是用戶，也可能是微博；關系可能是關注關系，也可能是微博轉發關系。

鄰接矩陣A的定義為A（u，v）=1。如果（u，v）∈E；否則，A（u，v）=0。如果圖內有n個節點，則鄰接矩陣A的元素為n×n。

圖1 四節點形成的無向圖，網絡研究的出發點Fig.1 Simple network with four nodes of an undirected subgraph

圖論研究表明［18］，k-階鄰接矩陣即矩陣的k次連乘，Ak=AA…A。如果兩個節點（u，v）間的連接賦予權重為w（u，v），如果（u，v）∈E；否則，w（u，v）=0。w（u，v）可定義為距離、成本或效益。通過計算Ak，可以得出兩點間最優k段路經，如果存在這些路徑的話。

2.2 粉絲矩陣的定義

結合粉絲模型［14］，參照無向無權重圖的基本定義，以圖1為基礎來表征社交網絡，加上節點間的指向，表明用戶間的關系，參見圖2。把上述定義的鄰接矩陣賦予這種微博用戶間的關系，可使用粉絲矩陣Ain來表達該網絡內各用戶間的關注關系。如果用戶u關注用戶v 且 （u，v）∈E，Ain（u，v）=1；否則，Ain（u，v）=0。這里的下標in和粉絲模型的函數fin（.）相對應，表示用戶v的粉絲集（即關注v的所有用戶集）。如果該圖有n個節點，Ain具有n×n元素。

粉絲矩陣Ain描述了相關元素的關注關系，通過對該矩陣行的閱讀，查詢到有關用戶的粉絲信息。粉絲矩陣的轉置A，定義為關注矩陣Aout=A。關注矩陣Aout描述了相關元素的關注關系，通過對該矩陣行的閱讀，查詢到有關用戶的關注人信息。

為便于廣泛應用，本文通稱粉絲矩和關注矩陣為關系寓意鄰接矩陣，簡稱粉絲矩陣。值得提出的是，文獻［19］在研究復雜系統結構有序度時，曾定義過反映結構元素間關系屬性的關系矩陣。而且，基于負熵的有序度概念，對研究在線社交網絡的關系和結構也有現實意義。

在線社交網絡用戶間的關系并不僅僅是一個層次的關系，而是多層次關系，例如，朋友的朋友的朋友……，就是多層次關系。有了粉絲矩陣，就可以方便地對這些關系加以描述。用A=AinAin…Ain來表達k-階粉絲關系，A是粉絲矩陣Ain的k次相乘。

2.3 粉絲矩陣的計算實例

使用一簡單例子，說明粉絲矩陣Ain，Aout，A的具體計算和實際應用。

圖2表達一個簡單社交網絡，其中各種關系均相對于用戶v：用戶u關注v和x，用戶v關注w和x，用戶x關注u和v。在此基礎上，列出的粉絲矩陣Ain和關注矩陣Aout的具體表達。

圖2 簡單在線社交網絡中相對于用戶v的粉絲、關注和互粉關系Fig.2 Follower，followee and v-friends relationships in online social network

粉絲矩陣Ain第一行，可以表達/查詢用戶u是v和x的粉絲的信息。關注矩陣Aout第二行，可以表達/查詢用戶v被u和x關注的信息。

當需要查詢朋友的朋友相關信息時，可以運用粉絲矩陣的兩階運算A。從A可看出，用戶u的朋友的朋友是v；v的朋友的朋友是u和x；等等。

如果需要查詢用戶的關注人的粉絲，粉絲矩陣與關注矩陣的乘積，AinAout可提供相應信息。如AinAout所示，用戶u的關注人的粉絲為v和x；v的關注人的粉絲為u，等等。

通過粉絲矩陣和關注矩陣的各種組合、各階計算，可以對在線社交網絡的各類相關信息進行查詢。這些查詢對于微博轉發預測和信息傳播預測都有著積極的意義。同時，矩陣操作對于開發并行計算資源，意義重大。可以說整個網絡各節點的計算都將一次性的甚至是同步的。如果說二階粉絲矩陣A2in的計算復雜度為O（n3），當k為有限值時，Akin的計算復雜度仍為O（n3）。這一點也是有意義的，在第一次計算A2in后，Akin將會在各項查詢和微博轉發預測中多次使用，這正是提出關系寓意鄰接矩陣的真正意義之一。

3 微博信息查詢Top-X的減少數據存儲量算法

新穎的社交網絡形成海量的大數據，已達到TB甚至PB規模，出于政治、商業和技術等目的的信息查詢，如同大海撈針，需要有效的算法來尋找知識性信息。針對引言部分有關微博平臺多約束組合信息查詢問題，介紹文獻［14］提出的基于粉絲模型，在給定時間段內的Top-X的“聚合-排序-刪除”查詢算法。

3.1 基礎查詢算法

在線社交網絡信息查詢的簡單通用方法，主要有兩種。

3.1.1 有序數據的邏輯乘運算

若想通過微博平臺信息查詢，得知本人和某人共同關注的用戶集。用粉絲模型即：I（a，b）=fout（a）∩fout（b），這里的fout（.）是粉絲模型的某用戶關注人的集函數，fout（a）=｛a1，a2，…，an｝，fout（b）=｛b1，b2，…，bn｝。這樣問題相當于邏輯乘運算，例如，曾博主關注的博主有張、王、李和趙，劉博主關注的博主有張、王、李和黃，則他們共同關注的博主有：張、王和李。

假設需要對集合fout（a）=｛a1，a2，…，an｝和fout（b）=｛b1，b2，…，bn｝求交集。為了使計算更有效率，最好首先對集合內的數據進行排序，如a1＜a2＜…＜an，b1＜b2＜…＜bn。有序數據的邏輯乘運算的時間復雜度為O（m+n），只需要進行簡單的合并操作，并標記出在兩個集合中都出現的元素。

3.1.2 有序數據的計數運算

如果某用戶希望通過自我查詢或是微博平臺推薦來獲得關注對象，最簡單的方法是看看他已關注的人的關注人。用粉絲模型就是某用戶關注人集函數的兩次操作：fout（fout（.））。例如，曾博主關注的博主有張、劉和趙；張博主關注的博主集合內有王、李和黃，劉博主關注的博主集合內有王、陸和姜，趙博主關注的博主集合內有王、李和姜；則系統會根據并集結果向曾博主推薦應該關注的博主有：王、李、姜、黃和陸。其中王博主有3人關注，李和姜博主分別有兩人關注，黃和陸博主各有一人關注。

假設有相當于上述張、劉和趙等博主關注的博主集合 m 個：A1=｛a11，a12，…，a1n1｝，A2=｛a21，a22，…，a2n2｝，……，Am=｛am1，am2，…，amnm｝，需要查詢在所有集合中重復次數最多的元素。和上述有序數據的邏輯乘運算一樣，首先對所有的m個集合進行排序，然后對排序后的集合進行合并，在合并的過程中就可以對每一個元素的出現次數進行統計，最后對元素的出現次數進行排序，得到要查詢的結果。在合并的過程中使用堆積樹能使算法得到進一步的優化。

上述例子中，得出的結果有5位博主，一目了然。如果得出的推薦集內含成千上萬個博主，這就涉及到Top-X問題。此例中，可以把“約束”定義為：關注人多于兩人的博主，推薦結果為：王、李和姜。還可以把“約束”定義為前 X 名粉絲最多的博主，相應的粉絲模型函數應為：fin（fout（fout（.）））。

3.2 時間區間內的查詢：數據索引法

前面的查詢舉例僅涉及用戶間的基本關系，與時間因素關系不大，如果要查詢用戶間發或轉發微博、推薦、評論和提醒等互動行為，則與時間關系密切。例如，用戶希望查詢在時間區間［ta，tb］內，粉絲對其微博的轉發次數等，就需要重新分析問題，研究新的查詢算法。

例如，王博主（A）發的微博，在t1和t2時被某兩粉絲轉發，張博主（B）的微博在t3時被某粉絲轉發。微博被轉發一次，稱為一項事件，標記為ek，在時間區間［t1，t3］內，共發生3項事件。可以用集合S表示這些事件和發生的時間：S=｛（eA，t1），（eA，t2），（eB，t3）｝；用集合C 表示與某用戶有關的事件發生時間：如王博主的微博被轉發的事件eA的時間集：C（eA）=｛t1，t2｝，張博主的微博被轉發的事件eB的時間集：C（eB）=｛t3｝。

還有另外一種表示方式。假設集合S=｛（e1，t1），（e2，t2），…，（en，tn）｝表示一系列的事件和其發生時間。使用集合C（ek）=｛t1，t2，…，tm｝表示S中事件ek發生的時間集合，那么m=｜C（ek）｜就表示事件ek發生的次數。同樣使S［ti，tj］表示在［ti，tj］時間范圍內事件ek發生的集合。

如果需要查詢ek在時間段S［ti，tj］內的出現次數，如果數據集S過大，進行遍歷查詢的工作量很大，效率非常低。一個優化的方法就是為每一個事件ek維護一個按發生時間排序的列表C（ek）=｛t1，t2，…，tm｝，其中t1＜t2＜…＜tm。通過二叉樹查找算法，以O（log（n））的復雜度找到第一個tx＞ta和第一個ty＞tb的事件元素。因此，事件ek的出現次數就是這兩事件序號之差。

圖3表示事件ek發生13次的時間分布軸，數值1表示ek第一次發生，13表示ek第13次發生。在ta和tb時間區間內事件發生的次數就是出現在tb之后的事件的第一個序號減去ta之后事件的第一個序號，既是9-6=3，說明在時間區間［ta，tb］內，事件ek發生了3次。

以上3種算法都是運用了有序數據可以提高查詢效率的基本原理。用數據索引法來查詢時間區間［ta，tb］內某事件的發生次數。實際工作中，有兩方面的問題：一是查詢計算不具備再利用性，特別是在數據集較大情況下，費很大力氣查得某事件的次數后，如果需要查詢另一事件，還要重新查詢。同時，查詢時間區間變化后，新的查詢也要從頭開始。二是，當需要查詢時間區間［ta，tb］內出現次數最多的某事件及相關用戶的Top-X時，用數據索引法計算該事件的出現次數，然后求出Top-X來，這只是在數據集比較小的時候，方能奏效。對于大數據，需要開發高效并可重復利用的算法。

3.3 聚合-排序-刪除算法

考慮到在線社交網絡的特性和對信息Top-X查詢的困難，文獻［14］提出“聚合-排序-刪除”算法，通過保留含有效信息的數據，大量減少存儲量的方法，來優化計算，實現此類查詢。

3.3.1 聚合

首先定義查詢時間區間為［ta，tb］，根據客戶需要可取為1小時、1天、1個月或1年等等。然后，將時間軸劃分成連續的、相等間隔的時間片Δt，一般取值為10分鐘、半個小時等等。對于每一個時間片S［ts，ts+Δt］，計算出每個事件ek相關的兩個指標：min（ek，ts）和 max（ek，ts）。其中 min（ek，ts）代表事件ek在給定時間區間［ti，tj］內的最小出現次數，并且，tj∈［ts，ts+Δt］和tj-ti=tb-ta。同理，max（ek，ts）就是在這個時間片內結束的時間區間內，事件ek出現的最大次數。

圖4給出聚合過程的一個具體例子，其中事件ek在整個時間軸上發生了13次，每次發生的時間如圖4時間軸所示。時間軸下面的數字曲線展示了每個時刻在指定的時間區間內事件的發生次數。假設時間區間隔是1個小時，那么在第8次之前的1個小時內，ek共發生了3次。若將時間軸劃分成均等的時間片Δt=20 min，計算時間區間內所含的時間片事件發生次數的最小值和最大值。就圖4的例子來說，在該指定的時間區間內，第7、8次的時間片內ek發生次數的最小值為1，最大值為3。

圖3 數據索引法步驟Fig.3 Data indexing method procedure

圖4 事件聚合步驟Fig.4 Event aggregation procedure

3.3.2 排序

聚合方法存儲了所有時間片內事件發生的信息，這種操作會占用大量的存儲空間，就聚合本身來講，是一個費時和費空間的低效方法。為了減少占用空間，需要刪除那些對要求的查詢結果無關的信息。因為查詢的要求最大情況下為Top-X，以X=100為例，只需要保留那些對Top-100有關的信息就可以。這樣，對于每一個時間片，通過發生最小值 min（ek，ts）遞減排序得到該時間區間發生次數的列表（e1，e2，…，e99，e100，e101，…，en）。必須始終保持前100的值，然而如果一個時間發生的最小值不在前100以內，但是它發生次數的最大值大于min（e100，ts），那么同樣也要放在該序列內。通過這個方法，即可大大減少算法對空間的需求，也就是說，減少了千千萬萬無查詢價值的事件發生的最大值和最小值。

刪除過程就是減少對查詢結果無用信息的儲存，大大減少對無關數據的處理。同樣，可以將ARD過程循環使用，以便得到更小的Δt時間片內相關信息，提高查詢范圍。

3.3.3 刪除

圖5描述了確定時間片內數據的信息保留和刪除過程。例如，在每一個時間片上相對縱坐標的事件A，B，C的最大值和最小值的排序位置。如果查詢只求Top 1的話，那么列表中只維護兩種信息：1）具有最大max值和相應min值的事件，如圖5第一時間片中的A事件；2）max值大于保留事件的min值的事件，如圖5中第一時間片中的B、C事件。在圖5中的其它事件片內，被去除掉的元素已用X標識。

需要指出的是，考慮到多個時間區間查詢需求，如1小時、1天、1個月甚至1年等，需要為每一個時間區間維護一個序列，但由于時間片選取的標準化，這樣的計算并不費事。例如上例中，時間片為20分鐘，時間區間為1小時，則一個時間區間由3個時間片組成。而時間區間為一天時，一個時間區間由72個時間片組成。實際計算時，這些工作并不困難，這主要是聚合-排序-刪除算法考慮到Top-X的限制，使得大數據集的計算問題變成小數據集的計算。例如，在查詢轉發某微博的用戶粉絲Top-50時，刪除后應存儲的數據量僅需8%左右。

圖5 排序和無用信息刪除步驟Fig.5 The procedure of ranking and useless information deletion

4 微博信息查詢Top-X的平行算法

隨著在線社交網絡用戶的激增，平臺上相應的功能也在不斷完善，微博信息查詢也面臨著新挑戰。例如國內一些微博平臺在原有的轉發、提及和評論等動作之外，還增加了推薦功能。在這些平臺上發現誰是誰的粉絲，誰的粉絲最多，這都不是太大的問題，如前面章節介紹的粉絲模型和查詢算法都相應提及。

比較棘手的問題是在給定時間區間［ta，tb］內，查找轉發（或者推薦、提及或推薦等）某些用戶在一動態群體內的粉絲數等信息的Top-X。這種動態形成的用戶集合，微博平臺并沒有現成的排行結果，他們也需要即時在線查詢。本節提出的Top-X查詢平行算法就是針對這一實際問題，應用映射和化簡概念［17］，在Hadoop系統支持下，聯機跨平臺上實現。

假設在給定時間區間［ta，tb］內轉發一用戶微博的用戶集為Z=［A，B，C，…，P，Q，R，…］，共m 個。正常情況是查詢出該集合內各用戶的關注人的集合fout（X），X=A，B，C，…，P，Q，R，…。這個查詢的空間幾乎是微博平臺的所有用戶，工作十分艱巨。如果把這個查詢過程在Hadoop平臺實現，就是所謂的映射過程，其間利用平行計算的模式，大大提高了計算效率。其具體算法如表1所示。

映射關注和化簡粉絲算法查詢微博平臺的Top-X：

1）建立關系對過程，建立轉發一用戶微博的m個用戶集為Z=［A，B，C，…，P，Q，R，…］的關注關系對，如表1中，User A關注User P等等，這些關系對一般大于m。

表1 映射關注和化簡粉絲算法查詢Top-XTab.1 Map followee &reduce follower algorithm for Top-Xquery

2）映射過程，整理建立的關系對，映射出用戶集Z=［A，B，C，…，P，Q，R，…］內各用戶的關注人的集合fout（X），如表1中關注User P的用戶有A，關注User Q的用戶有A、B等等。

3）化簡過程，算出用戶集Z=［A，B，C，…，P，Q，R，…］內各用戶的關注人的粉絲數｜fin（X）｜，如表1中，User P的粉絲數為1，User Q的粉絲數為2，等等。

4）排行過程，對用戶集Z=［A，B，C，…，P，Q，R，…］內各用戶的關注人的粉絲數｜fin（X）｜進行排行，求出Top-X，如表1中X=2，即User Q和R的粉絲數多于2。

“映射關注和化簡粉絲”算法已在Hadoop系統上調試，利用多臺計算機實現并行計算，提高了微博平臺內信息查詢和化簡存儲的效率。與第3節介紹的“聚合-排序-刪除”算法相比較，前者從平行計算的角度來提高查詢效率。兩個算法都說明了粉絲模型應用的方便之處。映射和化簡理念在微博平臺用戶關系查詢推廣方面的應用，有待深入研究。

5 應用舉例和結語

粉絲模型的提出，為在線社交網絡等類型的復雜網絡的用戶關系描述提供了有效的邏輯模型。已實現的應用研究主要在微博平臺信息查詢和微博轉發預測等方面，主要有4點。

1）粉絲模型和粉絲矩陣。粉絲模型［14］的提出在于描述在線網絡等復雜網絡的用戶邏輯關系，其定義的3個函數fin（.），fout（.），fr（.）分別準確、簡練地給出了用戶的粉絲集、關注人集和互粉集。這些函數的反對稱性、可擴展性和可組合性，使得用戶間的關系更復雜，例如粉絲的粉絲（f2in（.））、粉絲的關注人（foutfin（.））以及關注人的粉絲（finfout（.））等得以進一步的描述。同時，互粉函數的對稱性，也提供了互粉的互粉關系的函數（f2r（.））。這些用戶關系的邏輯模型，以及第2節介紹的對粉絲模型的關系矩陣表示，為研究微博平臺信息查詢算法和微博轉發預測方法，以及信息傳播機制等的研究奠定了良好基礎。

2）聚合-排序-刪除的查詢算法。粉絲模型的建立，為開發微博平臺信息的查詢算法提供了方便，聚合-排序-刪除的查詢算法［14］就是其中一例。在網絡信息技術方面頗有影響的國際Web信息系統工程會議（The 13th International Conference on Web Information System Engineering，WISE）2012年舉辦以新浪微博為主題的兩個競賽項目。組織者從新浪微博收集到的12.9GB的用戶關系數據和61.8GB微博信息數據為基礎。第一個項目是對客戶關系和微博信息數據的查詢性能比賽，組織者歸納出微博關系和轉發的19個查詢題目，要求參賽者開發優化算法，使用由中國IMC公司推出的BSMA性能測試工具，對這些查詢進行通過量、延時和數據規模等3項指標的性能分析。

本文第3節介紹的“聚合-排序-刪除”算法，就是應用粉絲模型，開發出來的微博平臺優化算法，實現此類組查詢，取得數據規模單項競賽并列第1名的成績［12］。

3）微博轉發預測。2012年WISE的第2個競賽項目是預測新浪微博與6個社會事件有關的33個微博的轉發情況。主辦方界定一個時間戳，并給出在此時間前用戶對這些微博的原始資料。參賽者應根據發表在30天內的這33個微博，預測原微博被轉發的次數和原微博可能被閱讀的次數。一次微博轉發行為后，微博可能被閱讀數定義為轉發該微博的用戶粉絲數。原微博可能被閱讀的總次數是所有轉發行為后該微博可能被閱讀數之和。

這兩個數字的計算取決于微博轉發的若干特性、粉絲模型以及相關優化算法，由此建立預測模型，如基于條件隨機場模型。具體預測方法和結果分析，參見文獻［20］。

4）映射關注和化簡粉絲算法。“映射關注和化簡粉絲”算法的功能在于，首先從原數據集中映射出具有某特性用戶間的關注關系，然后在所得到的粉絲集（fin（.））里邊通過化簡算出Top-X用戶來。對該算法的檢驗，是使用由H.Kwak團隊從Twitter收集的26GB用戶關系數據［16］和J.Yang等提供的75GB Tweets數據［21］。在Hadoop系統的并行聯機計算環境支持下，算法的信息查詢和化簡存儲性能明顯優于傳統方式。該案例是映射和化簡方法在微博大數據研究的首次嘗試，也進一步驗證了粉絲模型應用的潛在能力。

本文系TransLab實驗室2011年以來對在線社交網絡，特別是對微博和Twitter研究的綜合報告，涉及到的社交網絡的用戶間關系和行為的邏輯描述和相關計算方法。鑒于網絡結構的復雜性、信息查詢的艱巨性，這些研究工作引進了粉絲模型、映射和化簡等新理念和Hadoop數據管理新技術等，使得在線社交網絡的研究方法和結果引人注目和富有挑戰。本文描述的模型和算法雖然通過實際案例分析得到了初步檢驗，但理論分析需要進一步加強，亦希望得到同行評議和指正。

［1］Sun Y，Han J，Aggarwal C C，et al.When will it happen？—relationship prediction in heterogeneous information networks［C］//Proceedings of the fifth ACM international Conference on Web Search and Data Mining.New York，USA：ACM，2012：663-672.

［2］Sun Z，Wang H，Wang H，et al.Efficient subgraph matching on billion node graphs［J］.Proc VLDB Endow，2012，5（9）：788-799.

［3］Zhao X，Sala A，Wilson C，et al.Multi-scale dynamics in a massive online social network［C］//Proceedings of the 2012 ACM Conference on Internet Measurement Conference.New York，USA：ACM，2012：171-184.

［4］Kang U，Chau D H，Faloutsos C.Pegasus：Mining billion-scale graphs in the cloud［C］//2012IEEE International Conference on Acoustics，Speech and Signal Processing（ICASSP）.Kyoto，2012：5341-5344.

［5］Kim M，Leskovec J.Multiplicative attribute graph model of real-world networks［J］.Internet Mathematics，2012，8（1/2）：113-160.

［6］方錦清，汪小帆，鄭志剛，等.一門嶄新的交叉科學：網絡科學（下篇）［J］.物理學進展，2008，27（4）：361-448.

Fang Jinqing，Wang Xiaofan，Zheng Zhigang，et al.New interdisciplinary science：network science（II）［J］.Progress in Physics，2008，27（4）：361-448.

［7］Tang J，Zhang J，Yao L，et al.ArnetMiner：extraction and mining of academic social networks［C］//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York，USA：ACM，2008：990-998.

［8］Zhou A，Qian W，Ma H.Social media data analysis for revealing collective behaviors［C］//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York，USA：ACM，2012：1402-1402.

［9］段磊，唐常杰，楊寧，等.干預規則挖掘的概念、任務與研究進展［J］.計算機學報，2011，34（10）：1831-1843.

Duan Lei，Tang Changjie，Yang Ning，et al.Concepts，tasks and research advances of intervention rule ming［J］.Chinese Journal of Computers，2011，34（10）：1831-1843.

［10］Cheng X，Shen H.Uncovering the community structure associated with the diffusion dynamics on networks［J］.Journal of Statistics Mechanics，2010（4）：4-24.

［11］楊涵新，汪秉宏.復雜網絡上的演化博弈研究［J］.上海理工大學學報，2012，34（2）：166-171.

Yang Hanxin，Wang Binghong.A review about the evolutionary games on complex networks［J］.Journal of University of Shanghai for Science and Technology，2012，34（2）：166-171.

［12］LüL，Zhou T.Link prediction in complex networks：a survey［J］.Physica A：Statistical Mechanics and Its Applications，2011，390（6）：1150-1170.

［13］Cheng D，Qi H，Zhao Y.Analysis and control of general logical networks-an algebraic approach［J］.Annual Reviews in Control.2012，36（1）：11-25.

［14］Sandes E F O de，Li W G，Melo A C M A de.Logical model of relationship for online social networks and performance optimizing of queries［G］//Wang X S，Cruz I，Delis A，et al.Web Information Systems Engineering-WISE 2012.New York：Springer Berlin Heidelberg，2012：726-736.

［15］Unankard S，Chen L，Li P，et al.On the prediction of re-tweeting activities in social networks—a report on WISE 2012 challenge［G］//Wang X S，Cruz I，Delis A，et al.Web Information Systems Engineering-WISE 2012.Springer Berlin Heidelberg，2012：744-754.

［16］Kwak H，Lee C，Park H，et al.What is twitter，a social network or a news media？［C］//Proceedings of the 19th International Conference on World wide web.New York，USA：ACM，2010：591-600.

［17］Ghemawat S，Dean J.MapReduce：simplified data processing on large clusters［C］//Proceedings of Symposium on Operating System Design and Implementation（OSDI 2004）.San Francisco，California，USA：137-150.

［18］Foley J D.Computer Graphics：Principles and Practice［M］.New York：Addison-Wesley Professional，1996.

［19］李偉鋼.復雜系統結構有序度——負熵算法［J］.系統工程理論實踐，1988，8（4）：15-22.

Li Weigang.Negative Entropy-the sequence of the complex system structure［J］.System Engineering-Theory &Practice，1988，8（4）：15-22.

［20］Junior J，Almeida L，Modesto F，et al.An investigation on repost activity prediction for social media events［G］//Wang X S，Cruz I，Delis A，et al.Web Information Systems Engineering-WISE 2012.Springer Berlin Heidelberg，2012：719-725.

［21］Yang J，Leskovec J.Patterns of temporal variation in online media［C］//Proceedings of the Fourth ACM international Conference on Web Search and Data Mining.New York，USA：ACM，2011：177-186.

Logical Model and Parallel Querying in Online Social Networks

LI Wei-gang，ZHENG Jian-ya
（TransLab，Department of Computer Science，University of Brasilia，Brasilia 70910-900，Brazil）

Based on a thorough literature review in the related field，this paper presents some meaningful but challenging research topics in OSNs.The logical model（Follow Model）is introduced.To present the basic relationships between the users，the Relationship Committed Adjacency Matrix （Follow Matrix）is put forward.Then applying this logical model to show its effect，the Aggregation-Ranking-Delete algorithm is presented to rank the Top-X in OSNs.The paper further puts the new way of computing，combining the concept of MapReduce，into the parallel querying，which further leads to Map Followee and Reduce Follower algorithm implemented in Hadoop system.Follow Model and related algorithms are applied with the data collected from Sina Weibo（74.7GB）and Twitter（101GB）for the multi-constraint querying and retweeting prediction.The results demonstrate that the new solution with parallel paradigms in Hadoop has significantly improved the effect with the information storage adequately reduced and the computing power greatly increased.

complex system；parallel computing；Micro-blog；information query；MapReduce；online social networks；

N945

A

1672-3813（2013）02-0077-11

2013-03-20

巴西科學技術發展委員會（CNPq，304058/2010-6，478039/2012-3）

李偉鋼（1958-），男，河南南陽人，博士，副教授，主要研究方向為航空交通模型與人工智能。

（責任編輯 耿金花）