李偉鋼，鄭建亞

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

在線社交網(wǎng)絡的邏輯模型和并行查詢

李偉鋼，鄭建亞

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

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

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

0 引言

在線社交網(wǎng)絡具有動態(tài)變化、在線即時、個性行為、異構互聯(lián)和大數(shù)據(jù)生成等特點?；诤棋W(wǎng)絡拓撲、海量數(shù)據(jù)處理、多重關系分析和信息傳播擴散等對其機制進行研究，面臨著理論建模和技術實踐的各項挑戰(zhàn)。國內(nèi)外若干著名智能網(wǎng)絡、數(shù)據(jù)挖掘和復雜系統(tǒng)等研究中心，無不投入大量人力物力，從事這方面研究。

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

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

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

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

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

1 用戶關系邏輯模型

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

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

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

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

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

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

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

1.1 反對稱與對稱性

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

定理1 fin和fout互為反函數(shù)。

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

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

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

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

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

證得fin和fout互為反函數(shù)。

定理2 fr和fr自為反函數(shù)。

證明：對有向圖：G=（V，E），節(jié)點V 表示用戶；節(jié)點間的有向連接為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的互粉集函數(shù)，A的關注人集合與關注A的粉絲集合之并集。

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

證得fr自為反函數(shù)。

1.2 可擴展性

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

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

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

1.3 可組合性

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

有了對微博用戶關系邏輯描述的粉絲模型的函數(shù)定義和特性，具體問題的表達會更方便和實用。若以姚晨博友微博平臺的網(wǎng)友關系在線查詢?yōu)槔@些查詢提示可以較正式地用粉絲模型表示。

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

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

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

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

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

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

2.1 圖和鄰接矩陣的定義

為便于描述問題，按圖論來定義在線社交網(wǎng)絡的元素和關系。4個節(jié)點和連接構成一個簡單的無向圖G=（V，E），如圖1所示。節(jié)點集V 內(nèi)有：A，B，C，D∈V；各節(jié)點內(nèi)含一元素，這里指用戶名u，v，w 和x；節(jié)點間形成無向連接集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。

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

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

圖1 四節(jié)點形成的無向圖，網(wǎng)絡研究的出發(fā)點Fig.1 Simple network with four nodes of an undirected subgraph

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

2.2 粉絲矩陣的定義

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

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

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

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

2.3 粉絲矩陣的計算實例

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

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

圖2 簡單在線社交網(wǎng)絡中相對于用戶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，等等。

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

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

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

3.1 基礎查詢算法

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

3.1.1 有序數(shù)據(jù)的邏輯乘運算

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

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

3.1.2 有序數(shù)據(jù)的計數(shù)運算

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

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

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

3.2 時間區(qū)間內(nèi)的查詢：數(shù)據(jù)索引法

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

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

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

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

圖3表示事件ek發(fā)生13次的時間分布軸，數(shù)值1表示ek第一次發(fā)生，13表示ek第13次發(fā)生。在ta和tb時間區(qū)間內(nèi)事件發(fā)生的次數(shù)就是出現(xiàn)在tb之后的事件的第一個序號減去ta之后事件的第一個序號，既是9-6=3，說明在時間區(qū)間［ta，tb］內(nèi)，事件ek發(fā)生了3次。

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

3.3 聚合-排序-刪除算法

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

3.3.1 聚合

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

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

圖3 數(shù)據(jù)索引法步驟Fig.3 Data indexing method procedure

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

3.3.2 排序

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

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

3.3.3 刪除

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

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

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

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

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

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

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

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

1）建立關系對過程，建立轉(zhuǎn)發(fā)一用戶微博的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，…］內(nèi)各用戶的關注人的集合fout（X），如表1中關注User P的用戶有A，關注User Q的用戶有A、B等等。

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

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

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

5 應用舉例和結(jié)語

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

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

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

本文第3節(jié)介紹的“聚合-排序-刪除”算法，就是應用粉絲模型，開發(fā)出來的微博平臺優(yōu)化算法，實現(xiàn)此類組查詢，取得數(shù)據(jù)規(guī)模單項競賽并列第1名的成績［12］。

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

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

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

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

［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，F(xiàn)aloutsos 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］方錦清，汪小帆，鄭志剛，等.一門嶄新的交叉科學：網(wǎng)絡科學（下篇）［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］段磊，唐常杰，楊寧，等.干預規(guī)則挖掘的概念、任務與研究進展［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］楊涵新，汪秉宏.復雜網(wǎng)絡上的演化博弈研究［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］李偉鋼.復雜系統(tǒng)結(jié)構有序度——負熵算法［J］.系統(tǒng)工程理論實踐，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

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

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

（責任編輯 耿金花）