大數(shù)據(jù)時(shí)代的簡(jiǎn)約計(jì)算

張家琳，孫曉明

中國(guó)科學(xué)院計(jì)算技術(shù)研究所，北京 100190

大數(shù)據(jù)時(shí)代的簡(jiǎn)約計(jì)算

張家琳，孫曉明

中國(guó)科學(xué)院計(jì)算技術(shù)研究所，北京 100190

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

時(shí)間復(fù)雜性；空間復(fù)雜性；關(guān)系復(fù)雜性；數(shù)據(jù)復(fù)雜性

1 引言

隨著網(wǎng)絡(luò)、通信、感知等技術(shù)的迅猛發(fā)展，人類正進(jìn)入大數(shù)據(jù)時(shí)代：根據(jù)國(guó)外相關(guān)機(jī)構(gòu)預(yù)測(cè)，全世界數(shù)據(jù)總量以每?jī)赡攴环乃俣仍鲩L(zhǎng)。近年來(lái)大數(shù)據(jù)的飆升主要來(lái)源于互聯(lián)網(wǎng)服務(wù)，并且對(duì)大到國(guó)計(jì)民生小到衣食住行都產(chǎn)生了革命性的影響。因此在互聯(lián)網(wǎng)上可訪問(wèn)到的人、機(jī)、物三元世界產(chǎn)生的網(wǎng)絡(luò)大數(shù)據(jù)是大家關(guān)注的焦點(diǎn)。

網(wǎng)絡(luò)大數(shù)據(jù)具有如下3個(gè)特點(diǎn)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

（1）分散化

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

（2）局部化

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

（3）增量化

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

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

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

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

2.3 基于網(wǎng)絡(luò)的缺失預(yù)測(cè)和趨勢(shì)預(yù)測(cè)

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

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

3 網(wǎng)絡(luò)鏈路預(yù)測(cè)及推薦

3.1 “結(jié)構(gòu)微擾法”鏈路預(yù)測(cè)方法

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

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

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

3.2 場(chǎng)景自適應(yīng)的跨領(lǐng)域推薦

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

3.3 基于用戶行為的購(gòu)物推薦

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

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

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

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

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

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

4.3 并行秘書問(wèn)題在線算法

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

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

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

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

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

5.2 影響力最大化問(wèn)題

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

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

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

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

6 結(jié)束語(yǔ)

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

致謝

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

[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-），中國(guó)科學(xué)院計(jì)算技術(shù)研究所副研究員，主要研究方向?yàn)樵诰€算法、近似算法、社交網(wǎng)絡(luò)、算法博弈論等。

孫曉明（1978-），中國(guó)科學(xué)院計(jì)算技術(shù)研究所研究員，主要研究方向?yàn)樗惴ㄅc計(jì)算復(fù)雜性、量子計(jì)算等。

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

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61222202, No.61433014, No.61502449）；中組部萬(wàn)人計(jì)劃青年拔尖人才項(xiàng)目

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