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)上可訪問到的人、機(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（InternationalDataCorporation，國(guó)際數(shù)據(jù)公司）的研究報(bào)告稱，2012年網(wǎng)絡(luò)大數(shù)據(jù)總量為2.7ZB，預(yù)計(jì)到2020年，總量將達(dá)到40ZB。
●實(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è)面臨的共同難題。通過對(duì)網(wǎng)絡(luò)大數(shù)據(jù)共性問題的分析和研究，使企業(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ǔ)共性問題的解決將是新一代???????息技術(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)鍵紐帶，通過對(duì)網(wǎng)絡(luò)數(shù)據(jù)紐帶的分析與掌握，可以降低行???????成本、促進(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)得主GrayJ在他的最后一次演講中描繪了????據(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ì)于共性問題的提煉和分???????較少，還缺乏可察覺的方法論的主線。最后，在靜態(tài)數(shù)據(jù)或離線數(shù)據(jù)上的算法測(cè)試類研究較多，在真實(shí)系統(tǒng)中的大規(guī)模實(shí)驗(yàn)較少，還缺乏可信賴的效果評(píng)估。因此，數(shù)據(jù)科學(xué)，甚至說“第四范式”，都還只是一個(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)說，本文將集中關(guān)注與網(wǎng)絡(luò)大數(shù)據(jù)有關(guān)的算法理論和應(yīng)用問題，圍繞重點(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í)候，通過分布式計(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ǔ)、快照、訪問都需要耗費(fèi)高昂的成本，此時(shí)局部性算法不再?gòu)?qiáng)調(diào)分布式，而是關(guān)注網(wǎng)絡(luò)以數(shù)據(jù)流的形式輸入，如何實(shí)時(shí)處理以及如何只訪問網(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)，這類算法稱為增量式算法。DesikanP等人[3]針對(duì)動(dòng)態(tài)網(wǎng)絡(luò)的Pagerank更新，把網(wǎng)絡(luò)中的點(diǎn)分類，使得需要重新計(jì)算的點(diǎn)數(shù)很少，該方法后來(lái)被BahmaniB等人[4]推廣到MonteCarlo的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年，WattsDJ等人[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í)序路徑????度進(jìn)行刻畫[6]。PanRK等人[7]提出對(duì)時(shí)序網(wǎng)絡(luò)中的時(shí)序路徑進(jìn)行確切的定義并給出了相應(yīng)的計(jì)算算法。
NewmanMEJ[8]的研究成果，使得復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)成為近幾年復(fù)雜網(wǎng)絡(luò)領(lǐng)域的一個(gè)研究熱點(diǎn)，并形成了復(fù)雜網(wǎng)絡(luò)中一個(gè)重要的研究方向。FortunatoS[9]在PhysicsReports上給出了社區(qū)發(fā)現(xiàn)的綜述。2004年，NewmanMEJ[10]提出了基于模塊度優(yōu)化的快速算法。隨后，研究者在NewmanMEJ等人的工作基礎(chǔ)上，提出了多種類型的基于模塊度優(yōu)化的算法。
2.3 基于網(wǎng)絡(luò)的缺失預(yù)測(cè)和趨勢(shì)預(yù)測(cè)
網(wǎng)絡(luò)中的鏈路預(yù)測(cè)是指如何通過已知的網(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ù)缺失問題，鏈路預(yù)測(cè)可以通過推斷補(bǔ)齊這些缺失連邊，從而更加準(zhǔn)確地對(duì)網(wǎng)絡(luò)進(jìn)行分析，鏈路預(yù)測(cè)已成為準(zhǔn)確分析社會(huì)網(wǎng)絡(luò)和生物網(wǎng)絡(luò)的有力輔助工具[11]。另外，社會(huì)媒體中的推薦問題，譬如Facebook上的朋友推薦和新浪微博中???????關(guān)注對(duì)象推薦，本質(zhì)上也是鏈路預(yù)測(cè)問題[12]。
推薦系統(tǒng)通常包括3個(gè)組成要素：用戶、對(duì)象和推薦方法，其中推薦方法是整個(gè)推薦系統(tǒng)的核心。筆者主要考慮基于網(wǎng)絡(luò)的推薦系統(tǒng)。在簡(jiǎn)化的情況下，推薦系統(tǒng)可視為二部分圖上的鏈路預(yù)測(cè)問題。在大數(shù)據(jù)環(huán)境下，推薦系統(tǒng)規(guī)模很大，用戶和商品數(shù)目動(dòng)輒百千萬(wàn)計(jì)，兩個(gè)用戶之間選擇的重疊非常少，使得絕大部分基于關(guān)聯(lián)分析的算法（譬如協(xié)同過濾）的計(jì)算效果都不好。事實(shí)上，網(wǎng)絡(luò)方法很早就應(yīng)用于推薦系統(tǒng)。例如，AggarwalCC等人[13]研究了基于圖（網(wǎng)絡(luò)結(jié)構(gòu)）的協(xié)同推薦算法，結(jié)果表明基于圖的協(xié)同過濾方法在計(jì)算速度、推薦精度、可擴(kuò)展性、學(xué)習(xí)時(shí)間等方面均優(yōu)于傳統(tǒng)的協(xié)同推薦算法。HuangZ等人[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ǔ)問題[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)行????測(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等人[15]提出了如下假設(shè)：網(wǎng)絡(luò)越具有某些規(guī)律性，越容易被預(yù)測(cè)。進(jìn)一步地，如果隨機(jī)從網(wǎng)絡(luò)中抽取出一小部分鏈路，網(wǎng)絡(luò)的特征向量空間受到的影響很小，就說明網(wǎng)絡(luò)是具有規(guī)律性的。LüL等人使用類似于量子力學(xué)中對(duì)哈密頓量做一階微擾的方法，假定減少或增加少量???????接所產(chǎn)生的微擾，只對(duì)特征值有影響，而對(duì)特征向量沒有影響，這樣可以觀察微擾后通過這種辦法重構(gòu)的鄰接矩陣和真實(shí)鄰接矩陣的差異。LüL等人提出了一種度量這個(gè)差異的參數(shù)—結(jié)構(gòu)一致性（structuralconsistence），被認(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)微擾法”（structuralperturbationmethod）的鏈路預(yù)測(cè)方法。這個(gè)方法在預(yù)測(cè)丟失的鏈路以及甄別網(wǎng)絡(luò)中添加的噪音邊兩方面都明顯超過了當(dāng)前主流的方法，包括知名的層次結(jié)構(gòu)法和隨機(jī)分塊法。
3.2 場(chǎng)景自適應(yīng)的跨領(lǐng)域推薦
數(shù)據(jù)稀疏是推薦系統(tǒng)面臨的一大挑戰(zhàn)?？珙I(lǐng)域推薦通過融合多個(gè)領(lǐng)域的數(shù)據(jù)來(lái)克服數(shù)據(jù)稀疏問題?，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ì)上述問題，ShenHW等人[17]提出了一種場(chǎng)景自適應(yīng)的跨領(lǐng)域推薦方法（context-adaptivematrixfactorization，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)分析里的重要問題。傳統(tǒng)的方法有兩種：一種是基于商品順序的推薦，這種方式捕獲了用戶購(gòu)物的順序行為，但是忽略了購(gòu)物推薦的個(gè)性化因素，并且缺乏用戶對(duì)商品整體興趣的描述；另一種是協(xié)同過濾，這種方式忽略了用戶交易的特征，將用戶所有購(gòu)買的商品混在一起建模。為了解決以上問題，LanYY等人[18]提出了層次化表達(dá)模型???????hierarchicalrepresentationmodel）來(lái)完成用戶的購(gòu)物推薦。參考文獻(xiàn)[18]中假設(shè)用戶的表達(dá)和商品的表達(dá)均在同一個(gè)連續(xù)的空間中，商品的表達(dá)可以通過操作符合成交易的表達(dá)，用來(lái)代表用戶購(gòu)物的順序行為，用戶的表達(dá)代表用戶的整體興趣。在模型的第二層使用操作符將兩個(gè)表達(dá)合并在一起作為用戶當(dāng)前的興趣表達(dá)來(lái)預(yù)測(cè)用戶下一步購(gòu)買的商品。在和多個(gè)baseline進(jìn)行比較的實(shí)驗(yàn)中，LanYY??人??模型在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)典的算法問題，在大數(shù)據(jù)時(shí)代依然是眾多關(guān)鍵應(yīng)用的基石，如搜索、推薦系統(tǒng)等。筆者研究了訪問受限的動(dòng)態(tài)數(shù)據(jù)模型下的排序和查找問題[19]。借鑒Anagnostopoulos等人提出的動(dòng)態(tài)數(shù)據(jù)的模型，采用Kendalltau距離作為衡量算法性能的指標(biāo)。筆者研究了Topkselection問題：在每個(gè)時(shí)刻t，找出Topk的元素并將其排序。之前Anagnostopoulos等人的工作只研究了兩個(gè)極端情況k=1和k=n。筆者的主要貢獻(xiàn)是確定了該問題的“相變點(diǎn)”——k*，即當(dāng)k=o(k*)時(shí)，該問題可以以1-o(1)的概率無(wú)差錯(cuò)地解決。同時(shí)筆者證明了當(dāng)k超過k*時(shí)，對(duì)于任何算法，所求得的順序與真實(shí)順序的Kendalltau距離都至少是k2/n，而且筆者的算法表明這個(gè)界是緊的。筆者還研究了比Topkselection弱的一個(gè)問題：Topkset問題。在這一問題中筆者只需要確認(rèn)Topk的元素???????不需要確定它們的順序，證明了對(duì)任意的k，Topkset問題都可以以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ǔ)理論研究問題，ShaoJ等人[20]提出了一個(gè)新的社團(tuán)挖掘算法：Attractor算法。該算法的基本思想是將網(wǎng)絡(luò)看作一個(gè)動(dòng)力學(xué)系統(tǒng)，每個(gè)節(jié)點(diǎn)與周圍節(jié)點(diǎn)進(jìn)行交互，提出3種直觀的交互模式，通過模擬網(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ū)挖掘問題提供了新的思路和方法。
4.3 并行秘書問題在線算法
秘書問題是20世紀(jì)60年代提出的經(jīng)典在線問題，筆者研究了這個(gè)問題的一個(gè)一般化變種，并在并行模式下考慮了這個(gè)經(jīng)典的在線優(yōu)化問題[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è)未解問題。針對(duì)兩個(gè)典型的例子，給出了算法的近似比。
5 網(wǎng)絡(luò)小世界模型與信息傳播
5.1 基于博弈論的小世界模型
小世界模型是復(fù)雜網(wǎng)絡(luò)模型中的一個(gè)重要模型。它刻畫了各種復(fù)雜網(wǎng)絡(luò)中經(jīng)常出現(xiàn)的平均距離很短而聚合度較高的現(xiàn)象。2002年KleinbergJ提出了適于通行的小世界網(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ò)的有效維度。
ChenW等人[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)的概率增加。ChenW等人在這一網(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)定。ChenW等人在理論上論證了DRB（distance-reciprocitybalanced，距離—互惠平衡）博弈僅有兩個(gè)納什均衡，而適于通行的小世界網(wǎng)絡(luò)是唯一一個(gè)穩(wěn)定的均衡，任何團(tuán)體都無(wú)法通過共謀偏離這個(gè)均衡以使得團(tuán)體的成員獲利，而且即使絕大多數(shù)節(jié)點(diǎn)都隨機(jī)擾動(dòng)，節(jié)點(diǎn)也能很快回到適?????????的小世界模型狀態(tài)。他們還通過模擬實(shí)驗(yàn)進(jìn)一步驗(yàn)證了即使節(jié)點(diǎn)不了解其他節(jié)點(diǎn)的連接偏好，也同樣會(huì)收斂到適于通行的小世界網(wǎng)絡(luò)。ChenW等人還通過人人網(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 影響力最大化問題
影響力模型和最大化研究大多數(shù)基于獨(dú)立級(jí)聯(lián)模型（independentcascade）的影響力最大化問題，主要考慮單個(gè)個(gè)體傳播或純競(jìng)爭(zhēng)性多個(gè)體傳播，傳播過程是一次性的，并且傳播結(jié)果用期望值作為度量標(biāo)準(zhǔn)。在此基礎(chǔ)上，從幾個(gè)不同的角度對(duì)問題進(jìn)行了推廣。
筆者首次提出了基于概率保證的影響力最大化問題[23]，典型的應(yīng)用是：話題或事件希望能以一定的概率保證覆蓋超過一定比例的節(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)生的影響，并基于此提出了基于概率累積的影響力最大化問題[24]。LuW等人[25]還首次提出???????一個(gè)比較獨(dú)立級(jí)聯(lián)模型（comparativeindependentcascademodel,Com-ICmodel），將雙個(gè)體在競(jìng)爭(zhēng)或互補(bǔ)情形下的傳播方式統(tǒng)一表述在一個(gè)模型下。文中研究了模型的性質(zhì)，并著重研究了在互補(bǔ)情形下的影響力最大化問題。基于此改進(jìn)了基于反向可達(dá)集合的高效算法，并提出了夾心近似策略，當(dāng)影響力函數(shù)本身不具備子模性（submodularity）時(shí)仍能給出一定的近似比。
5.3 基于資源分配的影響力節(jié)點(diǎn)發(fā)現(xiàn)算法
通過考慮鄰居節(jié)點(diǎn)的資源以及傳播率對(duì)目標(biāo)節(jié)點(diǎn)的影響，ShangMS等人[26]提出了一種改進(jìn)的迭代資源算法來(lái)識(shí)別影響力節(jié)點(diǎn)。該方法認(rèn)為目標(biāo)節(jié)點(diǎn)的重要性程度受鄰居感染情況以及傳播率的影響，鄰居的影響力資源為基本的中心性，如：度、k核、接近中心性、特征向量中心性等。通過在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)行突破。希望能通過提出新的算法復(fù)雜性理論的基本思想和算法設(shè)計(jì)的基本框架，對(duì)數(shù)據(jù)科學(xué)基礎(chǔ)理論和基本方法論的形成產(chǎn)生貢獻(xiàn)。
編輯：HERO
