李偉鋼，鄭建亞

（巴西利亞大學(xué)計(jì)算機(jī)系TransLab實(shí)驗(yàn)室，巴西利亞70910- 900）

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

李偉鋼，鄭建亞

（巴西利亞大學(xué)計(jì)算機(jī)系TransLab實(shí)驗(yàn)室，巴西利亞70910- 900）

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

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

0 引言

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

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

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

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

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

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

1 用戶關(guān)系邏輯模型

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

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

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

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

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

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

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

1.1 反對(duì)稱與對(duì)稱性

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

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

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

fout（A）=｛B｜（A，B）∈E｝，表示A 的關(guān)注人集函數(shù)，A關(guān)注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ù)。

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

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

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

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

1.2 可擴(kuò)展性

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

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

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

1.3 可組合性

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

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

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

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

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

2 用戶關(guān)系邏輯模型的鄰接矩陣表述

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

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

2.1 圖和鄰接矩陣的定義

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

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

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

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

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

2.2 粉絲矩陣的定義

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

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

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

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

2.3 粉絲矩陣的計(jì)算實(shí)例

使用一簡(jiǎn)單例子，說(shuō)明粉絲矩陣Ain，Aout，A的具體計(jì)算和實(shí)際應(yīng)用。

圖2表達(dá)一個(gè)簡(jiǎn)單社交網(wǎng)絡(luò)，其中各種關(guān)系均相對(duì)于用戶v：用戶u關(guān)注v和x，用戶v關(guān)注w和x，用戶x關(guān)注u和v。在此基礎(chǔ)上，列出的粉絲矩陣Ain和關(guān)注矩陣Aout的具體表達(dá)。

圖2 簡(jiǎn)單在線社交網(wǎng)絡(luò)中相對(duì)于用戶v的粉絲、關(guān)注和互粉關(guān)系Fig.2 Follower，followee and v-friends relationships in online social network

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

當(dāng)需要查詢朋友的朋友相關(guān)信息時(shí)，可以運(yùn)用粉絲矩陣的兩階運(yùn)算A。從A可看出，用戶u的朋友的朋友是v；v的朋友的朋友是u和x；等等。

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

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

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

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

3.1 基礎(chǔ)查詢算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 聚合-排序-刪除算法

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

3.3.1 聚合

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

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

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

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

3.3.3 刪除

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

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

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

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

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

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

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

映射關(guān)注和化簡(jiǎn)粉絲算法查詢微博平臺(tái)的Top-X：

1）建立關(guān)系對(duì)過(guò)程，建立轉(zhuǎn)發(fā)一用戶微博的m個(gè)用戶集為Z=［A，B，C，…，P，Q，R，…］的關(guān)注關(guān)系對(duì)，如表1中，User A關(guān)注User P等等，這些關(guān)系對(duì)一般大于m。

表1 映射關(guān)注和化簡(jiǎn)粉絲算法查詢Top-XTab.1 Map followee &reduce follower algorithm for Top-Xquery

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

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

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

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

5 應(yīng)用舉例和結(jié)語(yǔ)

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

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

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

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

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

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

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

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

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

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

李偉鋼（1958-），男，河南南陽(yáng)人，博士，副教授，主要研究方向?yàn)楹娇战煌Ｐ团c人工智能。

（責(zé)任編輯 耿金花）