周 濤

(電子科技大學(xué)互聯(lián)網(wǎng)科學(xué)中心 成都 610054)

2012年3月，奧巴馬政府公布了“大數(shù)據(jù)研發(fā)計劃”，美國國家科學(xué)基金會、國防部、能源部、國家健康研究所、地質(zhì)勘探局和國防部先進(jìn)研究計劃局六個聯(lián)邦部門和機(jī)構(gòu)共同投資2億美元，致力于提高和改進(jìn)人們從海量和復(fù)雜的數(shù)據(jù)中獲取知識的能力。這是美國1993年宣布“信息高速公路”計劃后又一次重大科技發(fā)展部署。2012年5月，我國召開第424次香山科學(xué)會議，這是我國第一個以大數(shù)據(jù)為主題的重大科學(xué)工作會議。中國計算機(jī)學(xué)會、通信學(xué)會等于今年分別成立了“大數(shù)據(jù)專家委員會”。國家自然科學(xué)基金委員會2013年的《項目指南》中，大數(shù)據(jù)成為最熱門關(guān)鍵詞！2012年12月13日，中關(guān)村成立大數(shù)據(jù)產(chǎn)業(yè)聯(lián)盟，由云基地、聯(lián)通、用友、聯(lián)想、百度、騰訊、阿里巴巴等企業(yè)組成了第一批理事單位。

數(shù)據(jù)量的激增帶來了很多共性問題，譬如數(shù)據(jù)的可表示、可處理和可靠性問題等等。與此同時，各學(xué)科自身也有各具特色的大數(shù)據(jù)問題。網(wǎng)絡(luò)科學(xué)既是以網(wǎng)絡(luò)為研究對象的一門有數(shù)百年歷史的專業(yè)性很強(qiáng)的學(xué)科，又是眾多學(xué)科中不同研究對象的統(tǒng)一抽象的表達(dá)方式，其所遭遇的問題和挑戰(zhàn)往往特別典型、特別重要！目前萬維網(wǎng)具有超過萬億的統(tǒng)一資源定位符(URL)，F(xiàn)acebook有10億節(jié)點(diǎn)和千億連邊，大腦神經(jīng)元網(wǎng)絡(luò)有數(shù)百億節(jié)點(diǎn)，中國三大運(yùn)營商的手機(jī)通訊網(wǎng)絡(luò)無一不擁有數(shù)億用戶……如何處理超大規(guī)模的網(wǎng)絡(luò)數(shù)據(jù)，已經(jīng)成為學(xué)術(shù)界和企業(yè)界亟待解決的關(guān)鍵科學(xué)技術(shù)問題。

很多與網(wǎng)絡(luò)緊密相關(guān)的大數(shù)據(jù)問題是具有共性的。網(wǎng)絡(luò)數(shù)據(jù)是典型的非結(jié)構(gòu)化數(shù)據(jù)，針對大型網(wǎng)絡(luò)的存儲和管理的圖數(shù)據(jù)庫設(shè)計是目前非關(guān)系型數(shù)據(jù)庫的一個重要分支。盡管有學(xué)者堅信隨著計算能力和數(shù)據(jù)采集能力的提升，處理全體數(shù)據(jù)將成為趨勢，但抽樣仍然是目前處理海量數(shù)據(jù)問題的一種常用方法，而網(wǎng)絡(luò)抽樣不同于從一堆數(shù)中抽樣去逼近原始分布，后者有明確的最優(yōu)目標(biāo)，前者則無章可循——什么樣的網(wǎng)絡(luò)抽樣才算是好的呢？應(yīng)該用什么方法抽樣呢？抽樣誤差如何估計呢？大數(shù)據(jù)之間需要通過關(guān)聯(lián)和交叉復(fù)用展現(xiàn)出1+1>2的價值，以網(wǎng)絡(luò)科學(xué)的語言來做比喻，就是希望破譯“人人網(wǎng)”里面的某A就是“中國移動手機(jī)通訊網(wǎng)絡(luò)”中的某B，并且分析兩個網(wǎng)絡(luò)之間到底存在多少結(jié)構(gòu)和功能的關(guān)聯(lián)性。另外，可視化展示能夠幫助科學(xué)家快速從大數(shù)據(jù)中驗證科學(xué)猜想并獲得新的科學(xué)發(fā)現(xiàn)，大規(guī)模網(wǎng)絡(luò)的可視化也已被認(rèn)為是一種有助于理解和分析網(wǎng)絡(luò)的有效方法。

除了上述提到的一些共性問題外，此處我們著重介紹兩個網(wǎng)絡(luò)大數(shù)據(jù)獨(dú)特的問題：一是預(yù)測問題，二是圖的快速算法問題。

預(yù)測是大數(shù)據(jù)最核心的科學(xué)問題。目前學(xué)術(shù)界主要關(guān)心兩類預(yù)測問題，一是趨勢預(yù)測，二是缺失信息預(yù)測。趨勢預(yù)測是指通過事物的一些基本屬性信息和早期的態(tài)勢分析，預(yù)測事物發(fā)展的軌跡和最終影響力[1-2]。這樣的例子很多，譬如通過分析社交網(wǎng)絡(luò)中注冊一個月的用戶的行為以及這些用戶與其他用戶的互動，預(yù)測哪些用戶將來會成為很有影響力的用戶；通過用戶–商品二部分圖中產(chǎn)品的早期表現(xiàn)，例如一首新歌或一個新歌手上線一周的情況，來預(yù)測這首歌或者這個歌手有沒有可能走紅；通過一條信息早期數(shù)小時在微博網(wǎng)絡(luò)上的傳播情況，來預(yù)測這條信息最終的影響力等等。信息傳播的趨勢預(yù)測是一個正問題，其相應(yīng)的反問題是對傳播路徑進(jìn)行還原，確定擴(kuò)散源節(jié)點(diǎn)的位置[3]。這個問題雖然不屬于典型的預(yù)測問題，但也是相關(guān)且值得關(guān)注的問題。缺失信息預(yù)測假設(shè)我們觀察到的網(wǎng)絡(luò)只是真實(shí)網(wǎng)絡(luò)的一部分，在這個基礎(chǔ)上探討如何利用當(dāng)前信息去預(yù)測缺失邊[4]。以基因調(diào)控網(wǎng)絡(luò)和蛋白質(zhì)相互作用網(wǎng)絡(luò)為例，我們已經(jīng)知道的網(wǎng)絡(luò)結(jié)構(gòu)只是完整結(jié)構(gòu)很小的一部分，這時候缺失預(yù)測方法就能夠起到很大的作用。另外，社交網(wǎng)絡(luò)朋友推薦也可以看做是缺失信息預(yù)測，因為我們推薦的基本假設(shè)是“他們應(yīng)該認(rèn)識并成為好朋友”，其方法論和缺失信息預(yù)測是完全一致的。推薦系統(tǒng)設(shè)計的核心問題，就是用戶–商品二部分圖上的缺失信息預(yù)測[5]。這和上面提到的一部分圖上的鏈路預(yù)測問題理念相近但方法技術(shù)上有所不同。

圖的快速算法問題在大數(shù)據(jù)時代尤其具有挑戰(zhàn)性。以前O(N2)或者O(N3)的算法就被認(rèn)為效率很高了，而在動輒數(shù)億節(jié)點(diǎn)的網(wǎng)絡(luò)中，O(NlogN)甚至線性算法可能都是不可接受的——快速算法和分布式計算是必然的努力方向。在這種規(guī)模的網(wǎng)絡(luò)上，即便是求取簇系數(shù)和平均距離，都是一件開銷昂貴的事情。當(dāng)然，這些畢竟還是簡單的事情，因為精確計算的復(fù)雜性也不大，而且近似算法設(shè)計也比較容易。此處主要介紹圖匹配的問題和圖社區(qū)劃分問題，因為這兩個問題本身復(fù)雜性高，而且具有特別重要的應(yīng)用價值。圖匹配最嚴(yán)格的是要求判定兩個同階圖是否同構(gòu)，較弱的定義是判定兩個圖是否是子圖同構(gòu)的，也就是是否存在頂點(diǎn)之間的一個單射關(guān)系，若圖A中兩個頂點(diǎn)相連，則其在圖B中的單射的兩個頂點(diǎn)也必須相連。注意，此時A、B兩個圖不需要同階，A的頂點(diǎn)數(shù)可以少于B。一般而言，兩個圖既不是同構(gòu)的，也不會是子圖同構(gòu)的，這個時候，可以通過尋找最大公共誘導(dǎo)子圖來描述兩個圖的相似性。這些問題在大數(shù)據(jù)時代往往沒有太大實(shí)用價值，因為計算復(fù)雜性大得驚人，這個時候?qū)ふ医频淖畲蠊沧訄D或者通過傳播算法以及譜算法快速尋找兩個圖的頂點(diǎn)對應(yīng)關(guān)系就變得重要了[6]。社區(qū)挖掘的重要性不需贅述，不僅是展開網(wǎng)絡(luò)中觀結(jié)構(gòu)從而觀察網(wǎng)絡(luò)組織規(guī)律的有力武器，也對包括推薦系統(tǒng)設(shè)計[5]在內(nèi)的很多網(wǎng)絡(luò)應(yīng)用問題的重要輔助算法。目前，表現(xiàn)良好的算法已經(jīng)可以在單機(jī)上實(shí)現(xiàn)數(shù)小時內(nèi)劃分千萬節(jié)點(diǎn)規(guī)模的簡單無向網(wǎng)絡(luò)[7]，劃分效果主要還是采用模塊化程度這一指標(biāo)，盡管這個指標(biāo)在社區(qū)規(guī)模分辨率等方面存在缺陷。社區(qū)挖掘還有一個針對超大網(wǎng)絡(luò)非常直接的應(yīng)用，就是大規(guī)模網(wǎng)絡(luò)的分布式存儲。這個時候我們希望把網(wǎng)絡(luò)的節(jié)點(diǎn)分別存在在不同機(jī)器上，并且跨機(jī)器的交叉邊越少越好，而且為了負(fù)載平衡，還要求每個機(jī)器上節(jié)點(diǎn)總數(shù)是差不多的。這就相當(dāng)于社區(qū)挖掘的時候給出了兩個限定條件，一是知道社區(qū)數(shù)目，二是要求每個社區(qū)的節(jié)點(diǎn)數(shù)幾乎相等。最近微軟亞洲研究院提出了一個可以處理十億規(guī)模的分布式算法[8]。一個大膽的猜測是，現(xiàn)在和將來優(yōu)秀的快速社團(tuán)挖掘算法，也包括求解平均距離和其他網(wǎng)絡(luò)特征的近似算法，都會越來越多地利用重整化群的理念與方法。

[1] ASUR S, HUBERMAN B A. Predicting the future with social media[C]//IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology(WI-IAT). New York: IEEE Press, 2010: 492-499.

[2] ALTSHULER Y, PAN W, PENTLAND A. Trends prediction using social diffusion models[J]. Lect Notes Comput Sci,2012(7227): 97-104.

[3] PINTO P C, THIRAN P, VETTERLI M. Locating the source of diffusion in large-scale networks[J]. Phys Rev Lett,2012(109): 068702.

[4] LüL, ZHOU T. Link prediction in complex networks: a survey[J]. Physica A, 2011(390): 1150-1170.

[5] LüL, MEDO M, YEUNG C H, et al. Recommender systems[J]. Physics Reports, 2012(519): 1-49.

[6] TIAN Y, MCEACHIN R C, SANTOS C, et al. SAGA: a subgraph matching tool for biological graphs[J].Bioinformatics, 2007(23): 232-239.

[7] BLONDEL V D, GUILLAUME J-L, LAMBIOTTE R, et al.Fast unfolding of communities in large networks[J]. J Stat Mech, 2008(10): 10008.

[8] WANG L, XIAO Y, SHAO B, et al. How to partition a billion-node graph[R]. Beijing: MSRA, 2012.