張家琳，孫曉明

中國科學院計算技術研究所，北京 100190

大數(shù)據(jù)時代的簡約計算

張家琳，孫曉明

中國科學院計算技術研究所，北京 100190

大數(shù)據(jù)存儲和分析的能力是未來創(chuàng)新型國家的核心戰(zhàn)略能力。當前關于大數(shù)據(jù)的理論研究在共性問題提煉、方法論框架和實時數(shù)據(jù)算法理論上仍存在一些不足，從大數(shù)據(jù)“海量、實時、多樣”三大特征出發(fā)，聚焦網(wǎng)絡大數(shù)據(jù)這一對象，以數(shù)據(jù)復雜性的度量和約簡作為主線，具體從網(wǎng)絡鏈路預測及推薦、動態(tài)演化網(wǎng)絡上的算法研究、網(wǎng)絡小世界模型與信息傳播3個問題出發(fā)，研究大數(shù)據(jù)在時間、空間和關聯(lián)關系上的簡約計算。

時間復雜性；空間復雜性；關系復雜性；數(shù)據(jù)復雜性

1 引言

隨著網(wǎng)絡、通信、感知等技術的迅猛發(fā)展，人類正進入大數(shù)據(jù)時代：根據(jù)國外相關機構預測，全世界數(shù)據(jù)總量以每兩年翻一番的速度增長。近年來大數(shù)據(jù)的飆升主要來源于互聯(lián)網(wǎng)服務，并且對大到國計民生小到衣食住行都產(chǎn)生了革命性的影響。因此在互聯(lián)網(wǎng)上可訪問到的人、機、物三元世界產(chǎn)生的網(wǎng)絡大數(shù)據(jù)是大家關注的焦點。

網(wǎng)絡大數(shù)據(jù)具有如下3個特點。

· 海量：網(wǎng)絡空間中數(shù)據(jù)的體量不斷擴大，IDC（International Data Corporation，國際數(shù)據(jù)公司）的研究報告稱，2012年網(wǎng)絡大數(shù)據(jù)總量為2.7 ZB，預計到2020年，總量將達到40 ZB。

· 實時：網(wǎng)絡大數(shù)據(jù)通常以流的形式動態(tài)、快速地產(chǎn)生，具有很強的時效性，甚至呈現(xiàn)脈沖式的突發(fā)涌現(xiàn)，并且這些數(shù)據(jù)需要快速處理，實時響應。

· 多樣：描述同一主題的數(shù)據(jù)往往來源多樣，關聯(lián)關系復雜，而且包含結(jié)構化、半結(jié)構化和非結(jié)構化等多種數(shù)據(jù)類型。

網(wǎng)絡大數(shù)據(jù)在經(jīng)濟、社會、政治、科學等多方面都有不可估量的價值。美國政府認為大數(shù)據(jù)是“未來的新石油”，并把大數(shù)據(jù)研究上升為國家意志，這必然會在各個領域產(chǎn)生深遠的影響。

（1）網(wǎng)絡大數(shù)據(jù)的研究對捍衛(wèi)國家網(wǎng)絡空間的數(shù)字主權、維護國家安全和社會穩(wěn)定有重要作用

信息化時代，國家層面的競爭力將部分體現(xiàn)為一國擁有網(wǎng)絡大數(shù)據(jù)的規(guī)模、活性以及對數(shù)據(jù)的解釋與運用的能力。國家在網(wǎng)絡空間的數(shù)字主權也將是繼海、陸、空、天四大空間之后的另一個大國博弈的空間。備受矚目的“棱鏡門”，深刻暴露出一些大國在有計劃、有步驟地采集各國的數(shù)字“DNA”。2012年3月，美國國家科學基金會提出要“形成一個包括數(shù)學、統(tǒng)計基礎和計算機算法的獨特學科”——大數(shù)據(jù)科學。該計劃還強調(diào)，大數(shù)據(jù)技術事關美國的國家安全，影響科學研究的步伐，還將引發(fā)教育和學習的變革。這意味著網(wǎng)絡大數(shù)據(jù)的主權已上升為國家意志，直接影響國家和社會的穩(wěn)定，事關國家的戰(zhàn)略安全。

（2）網(wǎng)絡大數(shù)據(jù)是國民經(jīng)濟核心產(chǎn)業(yè)信息化升級的重要推動力量

“人、機、物”三元世界的融合產(chǎn)生了大規(guī)模的數(shù)據(jù)，如何感知、測量、利用這些網(wǎng)絡大數(shù)據(jù)成為國民經(jīng)濟中許多行業(yè)面臨的共同難題。通過對網(wǎng)絡大數(shù)據(jù)共性問題的分析和研究，使企業(yè)能夠掌握網(wǎng)絡大數(shù)據(jù)的處理技術或者能夠承受網(wǎng)絡大數(shù)據(jù)處理的成本與代價，進而使整個行業(yè)邁入數(shù)字化與信息化的新階段。從這個意義上來看，對網(wǎng)絡大數(shù)據(jù)基礎共性問題的解決將是新一代信息技術融合應用的新焦點，是信息產(chǎn)業(yè)持續(xù)高速增長的新引擎，也是行業(yè)用戶提升競爭力的新動力。

（3）網(wǎng)絡大數(shù)據(jù)技術上的突破將催生出戰(zhàn)略性新興產(chǎn)業(yè)

網(wǎng)絡大數(shù)據(jù)技術的突破意味著人們能夠理清數(shù)據(jù)交互連接產(chǎn)生的復雜性，掌握數(shù)據(jù)冗余與缺失雙重特征引起的不確定性，駕馭數(shù)據(jù)的高速增長與交叉互連引起的涌現(xiàn)性，進而能夠根據(jù)實際需求從網(wǎng)絡數(shù)據(jù)中挖掘出其蘊含的信息、知識甚至是智慧，最終達到充分利用網(wǎng)絡數(shù)據(jù)價值的目的。網(wǎng)絡數(shù)據(jù)已成為聯(lián)系各個環(huán)節(jié)的關鍵紐帶，通過對網(wǎng)絡數(shù)據(jù)紐帶的分析與掌握，可以降低行業(yè)成本、促進行業(yè)效率、提升行業(yè)生產(chǎn)力。在網(wǎng)絡大數(shù)據(jù)技術的驅(qū)動下，行業(yè)模式的革新將可能催生出數(shù)據(jù)材料、數(shù)據(jù)制造、數(shù)據(jù)能源、數(shù)據(jù)制藥、數(shù)據(jù)金融等一系列戰(zhàn)略性的新興產(chǎn)業(yè)。

（4）大數(shù)據(jù)正在引起學術界對科學研究思維與方法的一場革命

傳統(tǒng)科學研究的范式是從現(xiàn)象中分析提煉理論假設，再利用實驗驗證相應的理論。大數(shù)據(jù)的出現(xiàn)催生了一種新的科研模式，即面對大數(shù)據(jù)，科研人員只需從數(shù)據(jù)中直接查找、分析或挖掘所需的信息和知識，這些知識表現(xiàn)為概率形態(tài)的關聯(lián)或因果關系，這種關系可能復雜到無法為人類直觀掌握，但是可以很好地解釋現(xiàn)實、預測未來。圖靈獎得主Gray J在他的最后一次演講中描繪了數(shù)據(jù)密集型科學研究的“第四范式”，把數(shù)據(jù)密集型科學從計算科學中單獨區(qū)分開來。Gray認為，要解決面臨的某些最棘手的全球性挑戰(zhàn)，“第四范式”可能是唯一系統(tǒng)性的方法。

大數(shù)據(jù)研究方興未艾，成果累累，每年僅在Nature及其子刊、Science和PNAS上發(fā)表的大數(shù)據(jù)分析相關論文就有近百篇。其中，網(wǎng)絡大數(shù)據(jù)又扮演中心的角色。從計算機科學的角度看，目前的研究主要有3方面有待進一步加強。首先，目前還缺乏專門針對海量實時流式數(shù)據(jù)的算法理論、算法設計與評估框架。其次，對于特定數(shù)據(jù)對象的研究較多，對于共性問題的提煉和分析較少，還缺乏可察覺的方法論的主線。最后，在靜態(tài)數(shù)據(jù)或離線數(shù)據(jù)上的算法測試類研究較多，在真實系統(tǒng)中的大規(guī)模實驗較少，還缺乏可信賴的效果評估。因此，數(shù)據(jù)科學，甚至說“第四范式”，都還只是一個模糊的雛形。

本文嘗試從數(shù)據(jù)復雜度的角度進行突破，針對網(wǎng)絡大數(shù)據(jù)所具備的“海量、實時、多樣”三大特征，依托國家自然科學基金重點項目“大數(shù)據(jù)結(jié)構與關系的度量與簡約計算”，圍繞大數(shù)據(jù)時間、空間、關聯(lián)復雜性的度量和約簡展開，希望探索出符合當前實時海量流式數(shù)據(jù)處理的，新的算法復雜性理論基本思想和算法設計的基本框架，尋找從時間、空間和特征關聯(lián)3方面約簡數(shù)據(jù)和處理數(shù)據(jù)的算法，從而對數(shù)據(jù)科學基礎理論和基本方法論的形成產(chǎn)生貢獻。

具體來說，本文將集中關注與網(wǎng)絡大數(shù)據(jù)有關的算法理論和應用問題，圍繞重點項目“大數(shù)據(jù)結(jié)構與關系的度量與簡約計算”實施一年多來在網(wǎng)絡鏈路預測與推薦、網(wǎng)絡小世界模型及信息傳播、動態(tài)演化網(wǎng)絡的相關算法3方面取得的一些進展進行匯報，展示對數(shù)據(jù)復雜度的認識和理解。

2 相關工作

2.1 網(wǎng)絡大數(shù)據(jù)計算

傳統(tǒng)的CPU密集型的計算，數(shù)據(jù)量不大，算法復雜度往往只要求是多項式級即可，理論研究的焦點也在于區(qū)分多項式級和非多項式級的算法。而網(wǎng)絡大數(shù)據(jù)計算動輒面臨TB乃至PB級的數(shù)據(jù)規(guī)模，計算從CPU密集型轉(zhuǎn)化為數(shù)據(jù)密集型。算法設計的關鍵是保證時間為線性甚至亞線性。另一方面，數(shù)據(jù)傳輸（無論從外存讀取還是網(wǎng)絡上傳輸）的時間開銷遠大于CPU處理時間，這使得CPU不再成為計算的瓶頸。因此，計算方法的重點變成了努力降低算法涉及的數(shù)據(jù)的移動開銷。主要思路有3類：分散化、局部化和增量化。

（1）分散化

大機群分布式計算是高效大數(shù)據(jù)處理的首選，因為單個計算節(jié)點的工作負載可以大幅度降低，特別是當數(shù)據(jù)分散存儲的時候，通過分布式計算可以減少數(shù)據(jù)的跨節(jié)點流動，降低數(shù)據(jù)移動開銷。Google（谷歌）公布的MapReduce編程模型在工業(yè)界乃至學術界產(chǎn)生了極大的影響，以至于“談大數(shù)據(jù)必談MapReduce”[1]。

（2）局部化

網(wǎng)絡局部性算法最早指的是在網(wǎng)絡分布式計算中，每個計算節(jié)點的輸出僅僅與常數(shù)跳范圍內(nèi)的鄰居節(jié)點有關，與整個網(wǎng)絡的規(guī)模無關[2]。在網(wǎng)絡大數(shù)據(jù)背景下，網(wǎng)絡規(guī)模巨大且動態(tài)演化，對整個網(wǎng)絡結(jié)構的存儲、快照、訪問都需要耗費高昂的成本，此時局部性算法不再強調(diào)分布式，而是關注網(wǎng)絡以數(shù)據(jù)流的形式輸入，如何實時處理以及如何只訪問網(wǎng)絡局部的數(shù)據(jù)就能夠獲得計算結(jié)果。局部算法在時間復雜度上具有明顯的優(yōu)勢（亞線性甚至常數(shù)時間），在復雜網(wǎng)絡的計算中越來越受到關注。

（3）增量化

在動態(tài)網(wǎng)絡中，每個時刻的網(wǎng)絡數(shù)據(jù)都可以看作在前一時刻數(shù)據(jù)基礎上作了一定的偏移（稱為增量）。如果觀察間隔較短，那么相對于整個網(wǎng)絡規(guī)模，增量一般不大。如果基于增量更新網(wǎng)絡的特定性質(zhì)，在理想情況下，更新算法的時間復雜度不依賴于整個網(wǎng)絡的規(guī)模，僅僅與增量有關，這類算法稱為增量式算法。Desikan P等人[3]針對動態(tài)網(wǎng)絡的Pagerank更新，把網(wǎng)絡中的點分類，使得需要重新計算的點數(shù)很少，該方法后來被Bahmani B等人[4]推廣到Monte Carlo的Pagerank算法。

2.2 網(wǎng)絡大數(shù)據(jù)特征刻畫和結(jié)構挖掘

復雜網(wǎng)絡的特性主要由一些統(tǒng)計值來刻畫，如度分布、最短路徑長度等，這些宏觀特征是由各個節(jié)點的動力學行為及其節(jié)點之間相互作用產(chǎn)生的集中表現(xiàn)。1998年，Watts D J等人[5]分析了網(wǎng)絡中的高聚集性和短特征路徑長度等特性，研究了網(wǎng)絡“小世界”特性產(chǎn)生的機制。對于靜態(tài)網(wǎng)絡，通常采用拓撲距離刻畫網(wǎng)絡的最短路徑長度，而對于動態(tài)變化的時序網(wǎng)絡，一般采用時序路徑長度進行刻畫[6]。Pan R K 等人[7]提出對時序網(wǎng)絡中的時序路徑進行確切的定義并給出了相應的計算算法。

Newman M E J[8]的研究成果，使得復雜網(wǎng)絡中的社區(qū)發(fā)現(xiàn)成為近幾年復雜網(wǎng)絡領域的一個研究熱點，并形成了復雜網(wǎng)絡中一個重要的研究方向。Fortunato S[9]在Physics Reports上給出了社區(qū)發(fā)現(xiàn)的綜述。2004年，Newman M E J[10]提出了基于模塊度優(yōu)化的快速算法。隨后，研究者在Newman M E J等人的工作基礎上，提出了多種類型的基于模塊度優(yōu)化的算法。

2.3 基于網(wǎng)絡的缺失預測和趨勢預測

網(wǎng)絡中的鏈路預測是指如何通過已知的網(wǎng)絡結(jié)構信息來預測網(wǎng)絡中尚未產(chǎn)生連邊的兩個節(jié)點之間產(chǎn)生連接的可能性。由于實際應用中通常存在嚴重的數(shù)據(jù)缺失問題，鏈路預測可以通過推斷補齊這些缺失連邊，從而更加準確地對網(wǎng)絡進行分析，鏈路預測已成為準確分析社會網(wǎng)絡和生物網(wǎng)絡的有力輔助工具[11]。另外，社會媒體中的推薦問題，譬如Facebook上的朋友推薦和新浪微博中的關注對象推薦，本質(zhì)上也是鏈路預測問題[12]。

推薦系統(tǒng)通常包括3個組成要素：用戶、對象和推薦方法，其中推薦方法是整個推薦系統(tǒng)的核心。筆者主要考慮基于網(wǎng)絡的推薦系統(tǒng)。在簡化的情況下，推薦系統(tǒng)可視為二部分圖上的鏈路預測問題。在大數(shù)據(jù)環(huán)境下，推薦系統(tǒng)規(guī)模很大，用戶和商品數(shù)目動輒百千萬計，兩個用戶之間選擇的重疊非常少，使得絕大部分基于關聯(lián)分析的算法（譬如協(xié)同過濾）的計算效果都不好。事實上，網(wǎng)絡方法很早就應用于推薦系統(tǒng)。例如，Aggarwal C C等人[13]研究了基于圖（網(wǎng)絡結(jié)構）的協(xié)同推薦算法，結(jié)果表明基于圖的協(xié)同過濾方法在計算速度、推薦精度、可擴展性、學習時間等方面均優(yōu)于傳統(tǒng)的協(xié)同推薦算法。Huang Z等人[14]用二層圖模型刻畫客戶—產(chǎn)品推薦系統(tǒng)，討論了二部分圖的小世界效應和集聚性質(zhì)對不同推薦算法的影響。

3 網(wǎng)絡鏈路預測及推薦

3.1 “結(jié)構微擾法”鏈路預測方法

鏈路預測是網(wǎng)絡科學中一個重要的基礎問題[15]。精準的預測結(jié)果既可以指導生物學的實驗，還可以進行社交網(wǎng)絡的好友預測。好的預測算法本身還給出了很多網(wǎng)絡演化可能機制的暗示。遺憾的是，人們并不知道一個算法是否“足夠精確”。針對一個完全隨機的網(wǎng)絡，“什么都預測不到”可能已經(jīng)是最好的結(jié)果了，但針對一個非常規(guī)則的網(wǎng)絡，精心設計的方法可能能夠100%進行預測。知道了一個網(wǎng)絡的鏈路在多大程度上“能夠被預測出來”，能夠使得人們?nèi)ヅ袛嗨惴ㄊ欠褚呀?jīng)接近甚至達到預測的上界，是否還有提升的空間。

事實上，“可被預測的程度”本身也可以看作網(wǎng)絡的一種重要性質(zhì)。為了衡量網(wǎng)絡可被預測的難易程度，Lü L等人[16]提出了如下假設：網(wǎng)絡越具有某些規(guī)律性，越容易被預測。進一步地，如果隨機從網(wǎng)絡中抽取出一小部分鏈路，網(wǎng)絡的特征向量空間受到的影響很小，就說明網(wǎng)絡是具有規(guī)律性的。Lü L等人使用類似于量子力學中對哈密頓量做一階微擾的方法，假定減少或增加少量鏈接所產(chǎn)生的微擾，只對特征值有影響，而對特征向量沒有影響，這樣可以觀察微擾后通過這種辦法重構的鄰接矩陣和真實鄰接矩陣的差異。Lü L等人提出了一種度量這個差異的參數(shù)—結(jié)構一致性（structural consistence），被認為可以直接用來刻畫網(wǎng)絡的“可被預測的程度”[16]。

大量的模擬網(wǎng)絡和真實網(wǎng)絡實驗都支持了上述結(jié)論：結(jié)構一致性越強的網(wǎng)絡越容易被準確預測丟失的鏈路。Lü L等人利用結(jié)構一致性，提出了一種新的名為“結(jié)構微擾法”（structural perturbation method）的鏈路預測方法。這個方法在預測丟失的鏈路以及甄別網(wǎng)絡中添加的噪音邊兩方面都明顯超過了當前主流的方法，包括知名的層次結(jié)構法和隨機分塊法。

3.2 場景自適應的跨領域推薦

數(shù)據(jù)稀疏是推薦系統(tǒng)面臨的一大挑戰(zhàn)?？珙I域推薦通過融合多個領域的數(shù)據(jù)來克服數(shù)據(jù)稀疏問題。現(xiàn)有的跨領域推薦方法主要有兩類：第一類基于同質(zhì)性假設，即假設同一個對象在不同的領域共享同一個表達，這類方法適用于在每個領域都稀疏的對象，但不能刻畫領域?qū)ο蟮挠绊?；第二類基于異質(zhì)性假設，即假設每個領域有一個領域獨有的變換矩陣，每個對象在不同場景中的表達由該對象的全局表達和領域變換矩陣相作用得到，這類模型適用于在部分領域稀疏而在其他領域不稀疏的對象，但對于在每個領域都稀疏的對象效果很差。針對上述問題，Shen H W等人[17]提出了一種場景自適應的跨領域推薦方法（context-adaptive matrix factorization，AdaMF），對象的表達建模為其全局表達和場景相關表達的一個混合分布，采用混合系數(shù)來自適應地調(diào)節(jié)全局表達和場景相關表達的作用。在MovieLens-Netflix數(shù)據(jù)集上的實驗表明，AdaMF在稀疏—稀疏、稀疏—稠密、稠密—稠密等各個場景下都一致性地優(yōu)于現(xiàn)有的兩類代表性方法。

3.3 基于用戶行為的購物推薦

如何對用戶下一次的購物數(shù)據(jù)進行預測是市場分析里的重要問題。傳統(tǒng)的方法有兩種：一種是基于商品順序的推薦，這種方式捕獲了用戶購物的順序行為，但是忽略了購物推薦的個性化因素，并且缺乏用戶對商品整體興趣的描述；另一種是協(xié)同過濾，這種方式忽略了用戶交易的特征，將用戶所有購買的商品混在一起建模。為了解決以上問題，Lan Y Y等人[18]提出了層次化表達模型（hierarchical representation model）來完成用戶的購物推薦。參考文獻[18]中假設用戶的表達和商品的表達均在同一個連續(xù)的空間中，商品的表達可以通過操作符合成交易的表達，用來代表用戶購物的順序行為，用戶的表達代表用戶的整體興趣。在模型的第二層使用操作符將兩個表達合并在一起作為用戶當前的興趣表達來預測用戶下一步購買的商品。在和多個baseline進行比較的實驗中，Lan Y Y等人的模型在f-measure、hit-ratio以及NDCG指標上均取得了較好的性能。

4 動態(tài)演化網(wǎng)絡算法研究

4.1 動態(tài)演化網(wǎng)絡排序算法

排序作為最基本而經(jīng)典的算法問題，在大數(shù)據(jù)時代依然是眾多關鍵應用的基石，如搜索、推薦系統(tǒng)等。筆者研究了訪問受限的動態(tài)數(shù)據(jù)模型下的排序和查找問題[19]。借鑒Anagnostopoulos等人提出的動態(tài)數(shù)據(jù)的模型，采用Kendall tau距離作為衡量算法性能的指標。筆者研究了Topk selection問題：在每個時刻t，找出Topk的元素并將其排序。之前Anagnostopoulos等人的工作只研究了兩個極端情況k=1和k=n。筆者的主要貢獻是確定了該問題的“相變點”——k*，即當k=o(k*)時，該問題可以以1-o(1)的概率無差錯地解決。同時筆者證明了當k超過k*時，對于任何算法，所求得的順序與真實順序的Kendall tau距離都至少是k2/n，而且筆者的算法表明這個界是緊的。筆者還研究了比Topk selection弱的一個問題：Topk set問題。在這一問題中筆者只需要確認Topk的元素，而不需要確定它們的順序，證明了對任意的k，Topk set問題都可以以1-o(1)的概率無差錯地求解。

4.2 基于動態(tài)距離的網(wǎng)絡社區(qū)發(fā)現(xiàn)算法

社區(qū)挖掘是大規(guī)模網(wǎng)絡分析和挖掘的基礎，它在社交網(wǎng)絡、生物網(wǎng)絡、腦網(wǎng)絡等諸多方面都有重要的應用。但如何有效地挖掘大規(guī)模網(wǎng)絡中存在的社區(qū)結(jié)構仍然面臨著巨大的挑戰(zhàn)。針對這個基礎理論研究問題，Shao J等人[20]提出了一個新的社團挖掘算法：Attractor算法。該算法的基本思想是將網(wǎng)絡看作一個動力學系統(tǒng)，每個節(jié)點與周圍節(jié)點進行交互，提出3種直觀的交互模式，通過模擬網(wǎng)絡中節(jié)點間的距離變化動態(tài)地發(fā)現(xiàn)社區(qū)結(jié)構。由于社區(qū)檢測是基于網(wǎng)絡內(nèi)在的連接模式，因此該算法能找出網(wǎng)絡中不同大小的固有社團。同時由于算法的時間復雜度低，因此可以處理大規(guī)模網(wǎng)絡。大量人工數(shù)據(jù)集和真實數(shù)據(jù)集實驗都表明Attractor算法相比傳統(tǒng)算法更有優(yōu)勢。這一工作為大規(guī)模網(wǎng)絡中的社區(qū)挖掘問題提供了新的思路和方法。

4.3 并行秘書問題在線算法

秘書問題是20世紀60年代提出的經(jīng)典在線問題，筆者研究了這個問題的一個一般化變種，并在并行模式下考慮了這個經(jīng)典的在線優(yōu)化問題[21]。假設雇主計劃從n個完全隨機到來的候選人中選擇J個人。雇主對于不同的候選人有著不同的評價，想要錄取的這些人盡可能是前k好的。這里數(shù)據(jù)是以流式的方式到來的，每面試完一個候選人，面試官才知道當前候選人的價值，并且要立即決定是否錄取這個人，不可反悔。筆者在研究中提出了一個基于觀察—選擇的確定性算法。這個算法具有高效、易實現(xiàn)的特點，并且從線性規(guī)劃出發(fā)，利用互補松弛定理，可以證明該算法的最優(yōu)性。筆者的算法同樣可以用于解決當各隊列的名額是預先指定的情況，從而解決了EC2012上Feldman等人的文章中的一個未解問題。針對兩個典型的例子，給出了算法的近似比。

5 網(wǎng)絡小世界模型與信息傳播

5.1 基于博弈論的小世界模型

小世界模型是復雜網(wǎng)絡模型中的一個重要模型。它刻畫了各種復雜網(wǎng)絡中經(jīng)常出現(xiàn)的平均距離很短而聚合度較高的現(xiàn)象。2002年Kleinberg J提出了適于通行的小世界網(wǎng)絡的概率模型，指出當模型中的隨機長邊冪率分布系數(shù)r等于基準格子網(wǎng)絡的維度時，小世界網(wǎng)絡才是可通行的。之后的實證研究印證了現(xiàn)實的社交網(wǎng)絡的冪率系數(shù)r確實接近于網(wǎng)絡的有效維度。

Chen W等人[22]從博弈論的角度出發(fā)，將網(wǎng)絡中的每個節(jié)點看作一個網(wǎng)絡博弈的玩家，其長邊冪率分布系數(shù)r是其策略，r值偏大表示該節(jié)點側(cè)重于連接其附近的節(jié)點，隨著r值減小，其連接格子上較遠距離節(jié)點的概率增加。Chen W等人在這一網(wǎng)絡博弈中獨創(chuàng)性地引入了一個新的效用函數(shù)，使得每個節(jié)點的效用是其隨機長邊的平均格子距離與隨機長邊有反向邊的平均概率的乘積。前者表明，節(jié)點想連接遠處的節(jié)點以得到不同的信息，而后者表明節(jié)點傾向于連邊的互惠性（reciprocity）以使聯(lián)系更加穩(wěn)定。Chen W等人在理論上論證了DRB（distance-reciprocity balanced，距離—互惠平衡）博弈僅有兩個納什均衡，而適于通行的小世界網(wǎng)絡是唯一一個穩(wěn)定的均衡，任何團體都無法通過共謀偏離這個均衡以使得團體的成員獲利，而且即使絕大多數(shù)節(jié)點都隨機擾動，節(jié)點也能很快回到適于通行的小世界模型狀態(tài)。他們還通過模擬實驗進一步驗證了即使節(jié)點不了解其他節(jié)點的連接偏好，也同樣會收斂到適于通行的小世界網(wǎng)絡。Chen W等人還通過人人網(wǎng)和美國LiveJournal兩個實際網(wǎng)絡進行了驗證，實驗發(fā)現(xiàn)DRB博弈仍能很快收斂，而收斂后節(jié)點的連接偏好與實測結(jié)果的相關度相當高，其平均值也接近網(wǎng)絡的有效維度。

5.2 影響力最大化問題

影響力模型和最大化研究大多數(shù)基于獨立級聯(lián)模型（independent cascade）的影響力最大化問題，主要考慮單個個體傳播或純競爭性多個體傳播，傳播過程是一次性的，并且傳播結(jié)果用期望值作為度量標準。在此基礎上，從幾個不同的角度對問題進行了推廣。

筆者首次提出了基于概率保證的影響力最大化問題[23]，典型的應用是：話題或事件希望能以一定的概率保證覆蓋超過一定比例的節(jié)點，以此來爭奪社交網(wǎng)站上的熱點事件或者十大話題等。筆者考察當對同一事件或物品的信息傳播反復多次出現(xiàn)時，其影響概率逐漸累積之后，會對節(jié)點決策產(chǎn)生的影響，并基于此提出了基于概率累積的影響力最大化問題[24]。Lu W等人[25]還首次提出了一個比較獨立級聯(lián)模型（comparative independent cascade model, Com-IC model），將雙個體在競爭或互補情形下的傳播方式統(tǒng)一表述在一個模型下。文中研究了模型的性質(zhì)，并著重研究了在互補情形下的影響力最大化問題?；诖烁倪M了基于反向可達集合的高效算法，并提出了夾心近似策略，當影響力函數(shù)本身不具備子模性（submodularity）時仍能給出一定的近似比。

5.3 基于資源分配的影響力節(jié)點發(fā)現(xiàn)算法

通過考慮鄰居節(jié)點的資源以及傳播率對目標節(jié)點的影響，Shang M S等人[26]提出了一種改進的迭代資源算法來識別影響力節(jié)點。該方法認為目標節(jié)點的重要性程度受鄰居感染情況以及傳播率的影響，鄰居的影響力資源為基本的中心性，如：度、k核、接近中心性、特征向量中心性等。通過在4個真實網(wǎng)絡中的SIR模型結(jié)果比較，該方法和原有的方法相比在沒有增加參數(shù)以及復雜度的情況下，提高了精確度。特別地，在Erdos-Renyi網(wǎng)絡里，kendall系數(shù)提高了23%左右，在Protein網(wǎng)絡里提高了24%左右，效果比較明顯。該改進的迭代資源算法考慮了網(wǎng)絡結(jié)構以及傳播屬性，可以更好地識別網(wǎng)絡中的重要性節(jié)點，結(jié)合網(wǎng)絡結(jié)構和傳播動力學機制對識別核心節(jié)點具有重要的啟示作用。

6 結(jié)束語

本文聚焦網(wǎng)絡大數(shù)據(jù)這一當前熱點領域，從網(wǎng)絡鏈路預測及推薦、動態(tài)演化網(wǎng)絡算法研究以及網(wǎng)絡小世界模型與信息傳播3個方面，展示如何從數(shù)據(jù)復雜度的角度對大數(shù)據(jù)的算法設計進行突破。希望能通過提出新的算法復雜性理論的基本思想和算法設計的基本框架，對數(shù)據(jù)科學基礎理論和基本方法論的形成產(chǎn)生貢獻。

致謝

在本文的撰寫過程中，得到了周濤教授、陳衛(wèi)研究員、陳端兵教授、沈華偉研究員、邵俊明教授等的大力支持和幫助，部分素材來源于他們的研究工作，在此一并表示真誠的感謝！

[1] DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113.

[2] SUOMELA J. Survey of local algorithms[J]. ACM Computing Surveys (CSUR), 2013, 45(2): 94-111.

[3] DESIKAN P, PATHAK N, SRIVASTAVA J, et al. Incremental page rank computation on evolving graphs[C]//The 14th International Conference on World Wide Web, May 10-14, 2005, Chiba, Japan. New York: ACM Press, 2005: 1094-1095.

[4] BAHMANI B, CHOWDHURY A, GOEL A. Fast incremental and personalized PageRank[J]. Proceedings of the VLDB Endowment, 2010, 4(3): 173-184.

[5] WATTS D J, STROGATZ S H. Collective dynamics of “small-world” networks[J]. Nature, 1998, 393(6684): 440-442.

[6] HOLME P, SARAM?KI J. Temporal networks[J]. Physics Reports, 2011, 519(3): 97-125.

[7] PAN R K, SARAM?KI J. Path lengths, correlations, and centrality in temporal networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2011, 84(1 Pt 2):1577-1589.

[8] NEWMAN M E J. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences, 2006, 103(1): 8577-8582.

[9] FORTUNATO S. Community detection in graphs[J]. Physics Reports, 2010, 486(3-5): 75-174.

[10] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physics Review, 2004, E 69, 066133.

[11] SCHAFER L, GRAHAM J W. Missing data: our view of the state of the art[J]. Psychological Methods, 2002, 7(2): 147-177.

[12] ZHANG Q M, Lü L, WANG W Q, et al. Potential theory for directed networks[J]. Plos One, 2013, 8(2): e55437.

[13] AGGARWAL C C, WOLF J L, WU K L, et al. Horting hatches an egg: a new graph-theoretic approach to collaborative filtering[C]//The Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 15-18, 1999, San Diego, CA, USA. New York: ACM Press, 1999: 201-212.

[14] HUANG Z, ZENG D, CHEN H. Analyzing consumer-product graphs: empirical findings and applications inrecommender systems[J]. Management science, 2007, 53(7):1146-1164.

[15] Lü L, ZHOU T. Link prediction in complex networks: a survey[J]. Physica A Statistical Mechanics & Its Applications, 2011, 390(6):1150-1170.

[16] Lü L, PAN L, ZHOU T, et al. Toward link predictability of complex networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2015, 112(8): 2325-2330.

[17] MAN T, SHEN H W, HUANG J M, et al. Context-adaptive matrix factorization for multi-context recommendation[C]// The 24th ACM International Conference on Information and Knowledge Management(CIKM), October 19-23, 2015, Melbourne, Australia. New York: ACM Press, 2015: 901-910.

[18] WANG P F, GUO J F, LAN Y Y, et al. Learning hierarchical representation model for next basket recommendation[C]//The 38th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2015), August 9-13, 2015, Santiago, Chile. New York: ACM Press, 2015: 403-412.

[19] SUN X M, ZHANG J, ZHANG J L. Solving multi-choice secretary problem in parallel: an optimal observation-selection protocol[C]//The 25th International Symposium on Algorithms and Computation (ISAAC 2014), December 15-17, 2014, Jeonju, Korea. [S.l.]: Springer International Publishing, 2014: 661-673.

[20] SHAO J, HAN Z, YANG Q, et al. Community detection based on distance dynamics[C]// The 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 10-13, 2015, Sydney, Australia. New York: ACM Press, 2015:1075-1084.

[21] HUANG Q, LIU X W, SUN X M, et al. How to select the top-k elements from evolving data? [C]// The 26th International Symposium on Algorithms and Computation (ISAAC 2015), August 3-8, 2015, Macao, China. New York: ACM Press, 2015: 60-70.

[22] YANG Z, CHEN W. A game theoretic model for the formation of navigable small-world networks[C]//The 4th International World Wide Web Conference (WWW’2015), May 18-22, 2015, Florence, Italy. [S.l.:s.n.], 2015.

[23] ZHANG P, CHEN W, SUN X M, et al. Minimizing seed set selection with probabilistic coverage guarantee in a social network[C]//The 20th ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining, August 24-27, 2014, New York, USA. New York: ACM Press, 2014: 1306-1315.

[24] SHAN X H, CHEN W, LI Q, et al. Cumulative activation in social networks[J]. 2016, arXiv:1605.04635.

[25] LU W, CHEN W, LAKSHMANAN L V S. From competition to complementarity: comparative influence diffusion and maximization[C]//The 42nd International Conference on Very Large Data Bases (VLDB’2016), September 5-9, 2016, New Delhi, India. New York: ACM Press, 2015: 60-71.

[26] ZHONG L F, LIU J G, SHANG M S. Iterative resource allocation based on propagation feature of node for identifying the influential nodes[J]. Physics Letters A, 2015, 379(38): 2272-2276.

張家琳（1983-），中國科學院計算技術研究所副研究員，主要研究方向為在線算法、近似算法、社交網(wǎng)絡、算法博弈論等。

孫曉明（1978-），中國科學院計算技術研究所研究員，主要研究方向為算法與計算復雜性、量子計算等。

On the measurements of algorithms in big data era

ZHANG Jialin, SUN Xiaoming
Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China

The ability to store and analyze big data is a crucial capability of a powerful country in the new century. The current research of big data contains weakness on common scientific questions, general methodology, and theoretical analysis of real-time algorithm. It started from three key features about big data: volume, variety, and velocity, and the measurement and simplification of time complexity, space complexity, and relationship complexity for big data were focused.

time complexity, space complexity, relationship complexity, data complexity

TP3-0

A

10.11959/j.issn.2096-0271.2016037

2016-06-20

國家自然科學基金資助項目（No.61222202, No.61433014, No.61502449）；中組部萬人計劃青年拔尖人才項目

Foundation Items:The National Natural Science Foundation of China (No. 61222202, No.61433014, No.61502449), The China National Program for Support of Top-notch Young Professionals