王芯蕊，高 宏

（哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150001）

0 引言

隨著信息技術(shù)和互聯(lián)網(wǎng)的發(fā)展，諸如社交網(wǎng)絡(luò)、生物醫(yī)療等各個(gè)領(lǐng)域產(chǎn)生了大量的數(shù)據(jù)。作為一種常見的數(shù)據(jù)組織形式，信息網(wǎng)在真實(shí)世界中廣泛存在。信息網(wǎng)由眾多的對(duì)象以及這些對(duì)象間的聯(lián)系組成。例如，在微博等社交信息網(wǎng)中，用戶是對(duì)象，用戶之間的朋友關(guān)系是對(duì)象間的聯(lián)系。在豆瓣等影評(píng)信息網(wǎng)中，用戶、影片都是對(duì)象，一個(gè)用戶評(píng)價(jià)了一部影片，就產(chǎn)生了用戶與影片之間的聯(lián)系。在中國(guó)知網(wǎng)等文獻(xiàn)信息網(wǎng)中，作者、會(huì)議、論文都是對(duì)象，一個(gè)作者發(fā)表了一篇論文、一篇論文被一個(gè)會(huì)議收錄，都是對(duì)象之間產(chǎn)生的聯(lián)系。對(duì)信息網(wǎng)的分析研究具有重要的實(shí)際意義和廣闊的應(yīng)用前景，例如在社交信息網(wǎng)中，通過對(duì)具有共同興趣愛好的用戶進(jìn)行聚類，可以為用戶推薦新的朋友。又如在文獻(xiàn)信息網(wǎng)中，通過對(duì)作者發(fā)表的論文、論文所屬的會(huì)議等信息進(jìn)行分析，可以評(píng)估出作者的學(xué)術(shù)影響力。

在真實(shí)世界中，信息網(wǎng)上的對(duì)象和聯(lián)系常常隨著時(shí)間的推移不斷發(fā)生變化。如在社交信息網(wǎng)中，可能有新的用戶開始加入使用社交應(yīng)用，也可能有用戶選擇注銷賬戶，用戶之間的朋友關(guān)系更是不斷發(fā)展變化。又如在文獻(xiàn)信息網(wǎng)中，每年有眾多會(huì)議、期刊收錄大量論文，論文工作背后的科研團(tuán)隊(duì)也在不斷發(fā)展、更迭。這里將對(duì)象和聯(lián)系隨時(shí)間變化的信息網(wǎng)稱為動(dòng)態(tài)信息網(wǎng)。

隨著大數(shù)據(jù)時(shí)代的到來(lái)，動(dòng)態(tài)信息網(wǎng)上的對(duì)象和聯(lián)系不僅規(guī)模越來(lái)越大，其隨時(shí)間更新變化的頻率也越來(lái)越高。以社交信息網(wǎng)為例，由字節(jié)跳動(dòng)公布的數(shù)據(jù)分析報(bào)告顯示，截止2020年8月，抖音日活躍用戶數(shù)突破6億，相比于2020年1月時(shí)4億的日活躍用戶數(shù)，7個(gè)月內(nèi)漲幅高達(dá)50%，平均每秒新增約11個(gè)日活躍用戶。圖1展示了2019年TikTok每月的視頻下載量，每次下載可以認(rèn)為是TikTok用戶之間的一次互動(dòng)聯(lián)系，由圖1可以看出隨著時(shí)間的推移，TikTok用戶之間的互動(dòng)總是非常地頻繁，并且互動(dòng)數(shù)量不斷變化。

圖1 2019年TikTok每月視頻下載量Fig.1 TikTok video downloads by month in 2019

由于動(dòng)態(tài)信息網(wǎng)在各種現(xiàn)實(shí)應(yīng)用中普遍存在，近年來(lái)，動(dòng)態(tài)信息網(wǎng)受到了越來(lái)越多的關(guān)注。目前對(duì)于動(dòng)態(tài)信息網(wǎng)關(guān)鍵技術(shù)的研究主要集中在社區(qū)探測(cè)和社區(qū)搜索、離群點(diǎn)探測(cè)、影響力最大化、鏈接預(yù)測(cè)。本文詳細(xì)介紹了這些關(guān)鍵技術(shù)的概念、發(fā)展及其在動(dòng)態(tài)信息網(wǎng)上的研究進(jìn)展，然后討論了動(dòng)態(tài)信息網(wǎng)關(guān)鍵技術(shù)研究仍然面臨的挑戰(zhàn)，以及未來(lái)可能的研究方向。

1 動(dòng)態(tài)信息網(wǎng)關(guān)鍵技術(shù)研究現(xiàn)狀

1.1 社區(qū)探測(cè)和社區(qū)搜索

社區(qū)探測(cè)的目的在于識(shí)別網(wǎng)絡(luò)中所有的社區(qū)。

在信息網(wǎng)中，傳統(tǒng)的社區(qū)定義是一些相互之間緊密聯(lián)系的對(duì)象組成的集合。根據(jù)這個(gè)定義，文獻(xiàn)［2］采用基于圖劃分的方法，自頂向下將圖劃分成多個(gè)簇，使得簇內(nèi)的頂點(diǎn)間邊數(shù)盡可能大，而簇與簇之間的頂點(diǎn)間邊數(shù)盡可能小，最終滿足劃分要求所得到的每個(gè)簇對(duì)應(yīng)了一個(gè)社區(qū)。文獻(xiàn)［3］提出了被廣泛用于圖聚類和社區(qū)探測(cè)的SCAN算法，該算法自底向上地將擁有足夠多的共同鄰居的頂點(diǎn)聚類到同一個(gè)簇，每個(gè)簇對(duì)應(yīng)一個(gè)社區(qū)，SCAN算法還可以識(shí)別出連接多個(gè)簇的中心點(diǎn)（hub）以及離群點(diǎn)。值得注意的是，在真實(shí)的信息網(wǎng)中，常常存在一個(gè)對(duì)象屬于多個(gè)社區(qū)的情形，這就產(chǎn)生了一系列發(fā)現(xiàn)重疊社區(qū)的算法。上述所有社區(qū)探測(cè)的研究工作都只考慮了靜態(tài)信息網(wǎng)。

近年來(lái)，動(dòng)態(tài)信息網(wǎng)上的社區(qū)探測(cè)問題也受到了廣泛的關(guān)注。文獻(xiàn)［5］提出了基于博弈論的方法在動(dòng)態(tài)社交網(wǎng)上進(jìn)行社區(qū)探測(cè)。文獻(xiàn)［6］利用被改進(jìn)的標(biāo)簽傳播算法在動(dòng)態(tài)社交網(wǎng)上探測(cè)有重疊的社區(qū)。一般地，動(dòng)態(tài)社區(qū)探測(cè)的主要難點(diǎn)在于，不僅需要保證每個(gè)當(dāng)前時(shí)刻網(wǎng)絡(luò)聚類結(jié)果的質(zhì)量，而且需要考慮社區(qū)隨時(shí)間的推移所發(fā)生的動(dòng)態(tài)變化（如擴(kuò)大、縮小、消亡等）。

社區(qū)探測(cè)從整個(gè)網(wǎng)絡(luò)的宏觀角度，對(duì)靜態(tài)或者動(dòng)態(tài)網(wǎng)絡(luò)中所有的頂點(diǎn)進(jìn)行劃分或者聚類等操作，找到網(wǎng)絡(luò)中所有的社區(qū)。但是，從整個(gè)網(wǎng)絡(luò)探測(cè)的所有社區(qū)的數(shù)目可能非常龐大，而且這些社區(qū)從更細(xì)致的角度看可能各不相同，具有各種不同的特點(diǎn)。為此，研究者們又提出了社區(qū)搜索問題，旨在找到網(wǎng)絡(luò)中一些符合給定查詢條件的社區(qū)，這樣一來(lái)，就可以從更細(xì)致的角度提供以用戶為中心的、個(gè)性化的社區(qū)搜索服務(wù)。

隨著社區(qū)搜索問題的產(chǎn)生，由傳統(tǒng)的社區(qū)定義擴(kuò)展出了一系列新的社區(qū)模型，如基于核（該子圖內(nèi)的每個(gè)頂點(diǎn)至少有個(gè)鄰居）的社區(qū)、基于（該子圖中的每條邊至少被包含在這個(gè)子圖的（2）個(gè)三角形中）的社區(qū)、基于準(zhǔn)團(tuán)的社區(qū)、基于加權(quán)最稠密子圖的社區(qū)、以及具有影響力的社區(qū)等。

此外，因?yàn)楹四Ｐ椭忻總€(gè)頂點(diǎn)的核數(shù)可以用來(lái)度量用戶在社區(qū)中的參與度，所以基于核的社區(qū)模型在實(shí)際中應(yīng)用廣泛，并被進(jìn)一步擴(kuò)展定義許多新的社區(qū)模型。類似地，因?yàn)橐粋€(gè)三角形反映了3個(gè)對(duì)象間穩(wěn)定的聯(lián)系，所以的值越大，說明該子圖內(nèi)的成員間的關(guān)系越穩(wěn)定，于是，可以反映社區(qū)內(nèi)部成員間聯(lián)系的穩(wěn)定程度的社區(qū)模型也得到了廣泛使用和擴(kuò)展。

上述部分工作研究了動(dòng)態(tài)網(wǎng)絡(luò)上的社區(qū)搜索問題。這些工作主要考慮的是如何設(shè)計(jì)在線算法及時(shí)計(jì)算出動(dòng)態(tài)網(wǎng)絡(luò)上每個(gè)當(dāng)前時(shí)刻的社區(qū)搜索結(jié)果。

1.2 離群點(diǎn)探測(cè)

離群點(diǎn)作為經(jīng)典的數(shù)據(jù)挖掘問題，相關(guān)研究已經(jīng)開展了幾十年，其最基本的定義是由文獻(xiàn)［12］提出的：離群點(diǎn)是這樣一種觀察點(diǎn)，即明顯偏離于其他觀察點(diǎn)的行為，以至于認(rèn)為這些點(diǎn)與其他正常點(diǎn)是由不同機(jī)制產(chǎn)生的。

由于數(shù)據(jù)類型的不同，離群點(diǎn)探測(cè)的方法也各有不同。例如，一種常用的離群點(diǎn)探測(cè)方法是基于聚類的，這種方法將離群點(diǎn)歸為聚類分析的附加產(chǎn)物，也就是說，在對(duì)所有數(shù)據(jù)點(diǎn)執(zhí)行聚類操作后，那些不屬于任何簇的點(diǎn)就是離群點(diǎn)。其他常用的方法還有基于統(tǒng)計(jì)學(xué)的方法、基于神經(jīng)網(wǎng)絡(luò)的方法等等。

針對(duì)不同類型的數(shù)據(jù)，離群點(diǎn)的定義可能會(huì)發(fā)生一些擴(kuò)展和變化。例如，文獻(xiàn)［13］研究了圖流上的離群點(diǎn)探測(cè)，輸入的圖流是一個(gè)個(gè)圖對(duì)象（稱圖流中所有圖的頂點(diǎn)的集合為基本頂點(diǎn)域，而每個(gè)圖對(duì)象的頂點(diǎn)集是基本頂點(diǎn)域的一個(gè)子集）。圖中不尋常的關(guān)系是指在圖的各區(qū)域（即密集、連通子結(jié)構(gòu)，通過頂點(diǎn)劃分獲得）之間很少出現(xiàn)的起到橋接作用的邊，離群點(diǎn)是包含了這些不尋常的橋接邊的圖對(duì)象。

近年來(lái)，一些研究工作開始關(guān)注信息網(wǎng)上社區(qū)離群點(diǎn)的探測(cè)。文獻(xiàn)［14］進(jìn)行社區(qū)探測(cè)后，把那些不屬于任何社區(qū)的對(duì)象作為社區(qū)離群點(diǎn)。文獻(xiàn)［15］在靜態(tài)信息網(wǎng)上研究了如何探測(cè)那些與其所在社區(qū)內(nèi)的其他成員具有明顯不同的行為模式的社區(qū)離群點(diǎn)。

此外，因?yàn)樾畔⒕W(wǎng)中的一個(gè)對(duì)象常常屬于多個(gè)社區(qū)，文獻(xiàn)［16］提出靜態(tài)信息網(wǎng)上的社區(qū)分布離群點(diǎn)探測(cè)問題，給定信息網(wǎng)上的所有社區(qū)，并且已知每個(gè)對(duì)象屬于哪些社區(qū)，先通過在各個(gè)對(duì)象的社區(qū)分布矩陣上進(jìn)行聯(lián)合非負(fù)矩陣分解以發(fā)現(xiàn)所有的頻繁社區(qū)分布模式、即社區(qū)中大多數(shù)對(duì)象普遍具有的社區(qū)分布模式，然后計(jì)算每個(gè)對(duì)象的社區(qū)分布模式到與其最近的頻繁社區(qū)分布模式的距離作為該對(duì)象的離群點(diǎn)得分，最后那些離群點(diǎn)得分最大的對(duì)象被作為社區(qū)分布離群點(diǎn)輸出。類似地，文獻(xiàn)［17-18］研究了在動(dòng)態(tài)信息網(wǎng)的2張或多張快照上，動(dòng)態(tài)社區(qū)分布模式與其所在社區(qū)內(nèi)的大部分成員有所不同的社區(qū)分布離群點(diǎn)的探測(cè)問題。另外，文獻(xiàn)［19］進(jìn)一步將少量具有影響力、可能改變社區(qū)未來(lái)構(gòu)成的重要社區(qū)分布離群點(diǎn)從所有的社區(qū)分布離群點(diǎn)中分離了出來(lái)。

1.3 影響力最大化

給定一個(gè)網(wǎng)絡(luò)，以及一個(gè)參數(shù)，影響力最大化旨在找到一個(gè)由個(gè)頂點(diǎn)構(gòu)成的種子集合，從而最大化整個(gè)網(wǎng)絡(luò)的影響力傳播，亦即最大化整個(gè)網(wǎng)絡(luò)中被種子集合所影響的所有頂點(diǎn)的總數(shù)。

影響力最大化問題是NP-難的，文獻(xiàn)［20］中將影響力最大化問題形式化為離散型最優(yōu)化問題，并且通過分析目標(biāo)函數(shù)的次模性，基于蒙特卡羅模擬方法，給出了一個(gè)具有（11）近似比的貪心算法求解影響力最大化問題。其中，是自然對(duì)數(shù)的底，≈2718。具體地，該方法進(jìn)行輪貪心選擇，每輪都尋找一個(gè)具有最大影響力的頂點(diǎn)加入種子集合。在每輪貪心選擇中，使用多次蒙特卡羅模擬來(lái)估計(jì)每個(gè)頂點(diǎn)的影響力。

現(xiàn)有的關(guān)于靜態(tài)信息網(wǎng)上影響力最大化問題的解決方法主要分為4類：基于模擬的方法、基于子圖的方法、基于概要的方法和基于啟發(fā)式的方法。文獻(xiàn)［20］是采用基于模擬的方法的典型代表。但是由于蒙特卡羅模擬需要很多的時(shí)間，所以文獻(xiàn)［20］中的貪心算法擴(kuò)展性不好，對(duì)于大規(guī)模網(wǎng)絡(luò)的適用性并不好。為此，文獻(xiàn)［21］在保證達(dá)到文獻(xiàn)［20］中貪心算法的結(jié)果質(zhì)量的情況下，采用早期終止技術(shù)CELF減少了一些不必要的模擬，但是CELF的最壞時(shí)間復(fù)雜性仍然沒有得到改善。基于子圖的方法是使用蒙特卡羅模擬生成少量原始網(wǎng)絡(luò)的子圖，然后重復(fù)利用這些子圖估計(jì)每個(gè)頂點(diǎn)的影響力?；诟乓姆椒▌t是通過蒙特卡羅模擬為選中的頂點(diǎn)建立概要，概要中包含了能達(dá)到的所有頂點(diǎn)的集合，稱為的逆可達(dá)集，最后根據(jù)建立的概要解決影響力最大化問題?？梢?，基于子圖和基于概要的方法也是以蒙特卡羅模擬為基礎(chǔ)。為了避免進(jìn)行蒙特卡羅模擬，研究者們提出了一系列基于啟發(fā)式的方法。雖然基于啟發(fā)式的方法具有更好的擴(kuò)展性，但是結(jié)果質(zhì)量卻有所削減。實(shí)際上，目前眾多求解影響力最大化問題的算法都無(wú)法同時(shí)兼顧可擴(kuò)展性和結(jié)果質(zhì)量。

近幾年來(lái)，動(dòng)態(tài)信息網(wǎng)上的影響力最大化問題的研究熱度仍在攀升。文獻(xiàn)［25］將動(dòng)態(tài)信息網(wǎng)刻畫成一系列靜態(tài)信息網(wǎng)的快照，并連續(xù)地為每張快照求解種子集合。文獻(xiàn)［26］設(shè)計(jì)了實(shí)時(shí)全動(dòng)態(tài)的索引數(shù)據(jù)結(jié)構(gòu)對(duì)動(dòng)態(tài)信息網(wǎng)進(jìn)行影響力分析，其方法適用于網(wǎng)絡(luò)中對(duì)象和聯(lián)系隨時(shí)間增加或減少、以及傳播概率頻繁更新的情形。文獻(xiàn)［27］采用圖壓縮技術(shù)，提出高效的算法找到一個(gè)種子集合，以最大化動(dòng)態(tài)信息網(wǎng)上一個(gè)時(shí)間窗口內(nèi)由該種子集合所影響的所有不同頂點(diǎn)的總數(shù)。

此外，與影響力最大化問題相對(duì)應(yīng)的，一些工作研究了如何限制謠言在動(dòng)態(tài)信息網(wǎng)上的傳播。具體地，通過識(shí)別一些知道真相的用戶，使得謠言傳到該用戶處就停止繼續(xù)往下傳播。文獻(xiàn)［28］給定一些謠言發(fā)起者的集合，輸出個(gè)知道真相的用戶，使得整個(gè)網(wǎng)絡(luò)中被謠言影響的用戶總數(shù)最少?？紤]到以前的工作認(rèn)為謠言開始傳播和某些用戶知道真相是同時(shí)發(fā)生的，忽略了謠言的傳播具有時(shí)間延遲性，也忽略了一些謠言的傳播是有截止時(shí)間的，超過截止時(shí)間將不再傳播，于是，文獻(xiàn)［29］研究了在存在傳播延遲的情況下，識(shí)別top個(gè)知道真相的用戶，以最小化網(wǎng)絡(luò)中在謠言傳播截止時(shí)間前被謠言影響的用戶總數(shù)的問題。

1.4 鏈接預(yù)測(cè)

鏈接預(yù)測(cè)是指預(yù)測(cè)未來(lái)可能出現(xiàn)的對(duì)象之間的新聯(lián)系。鏈接預(yù)測(cè)可以用于朋友推薦、市場(chǎng)分析、商業(yè)智能等多個(gè)領(lǐng)域。因此，近年來(lái)，鏈接預(yù)測(cè)問題得到了各方面的關(guān)注和重視。

基于頂點(diǎn)相似性度量的方法常用于鏈接預(yù)測(cè)問題，具體地，預(yù)測(cè)2個(gè)頂點(diǎn)之間可能會(huì)產(chǎn)生一條邊（或稱一個(gè)鏈接），如果這2個(gè)頂點(diǎn)足夠相似。另外，通過有監(jiān)督的學(xué)習(xí)方法對(duì)信息網(wǎng)上的邊進(jìn)行分類以及采用其它一些機(jī)器學(xué)習(xí)的方法進(jìn)行建模也可以處理鏈接預(yù)測(cè)問題。文獻(xiàn)［30］基于圖嵌入（Graph Embedding）方法，提出了知識(shí)圖譜上的鏈接預(yù)測(cè)算法，用于填補(bǔ)知識(shí)圖譜中未知的鏈接信息。文獻(xiàn)［31］利用改進(jìn)了的深度圖卷積網(wǎng)絡(luò)研究異構(gòu)信息網(wǎng)上的鏈接預(yù)測(cè)問題。此外，因?yàn)閳D卷積網(wǎng)絡(luò)只能用于簡(jiǎn)單圖上的鏈接預(yù)測(cè)，文獻(xiàn)［32］提出了神經(jīng)超鏈接預(yù)測(cè)器NHP以及相應(yīng)的2個(gè)變體NHP-U和NHP-D，用于超圖上的鏈接預(yù)測(cè)。文獻(xiàn)［33］考慮到在快速演化的圖流上，因?yàn)檫吺请S時(shí)間逐漸到達(dá)的，內(nèi)存中無(wú)法一次性維護(hù)完整的圖結(jié)構(gòu)，因而提出了動(dòng)態(tài)在線鏈接預(yù)測(cè)算法來(lái)解決圖流上的鏈接預(yù)測(cè)問題。

目前，已經(jīng)有很多工作研究了動(dòng)態(tài)信息網(wǎng)上的鏈接預(yù)測(cè)問題。文獻(xiàn)［34］通過整合時(shí)間信息、社區(qū)結(jié)構(gòu)信息和頂點(diǎn)中心性度量，給出了一個(gè)全新的動(dòng)態(tài)信息網(wǎng)上的鏈接預(yù)測(cè)模型。文獻(xiàn)［35］提出了一個(gè)時(shí)序潛在空間模型用于動(dòng)態(tài)信息網(wǎng)上的鏈接預(yù)測(cè)，該模型假設(shè)每個(gè)用戶都位于一個(gè)未被觀察到的潛在空間，并且在潛在空間表示中，相似用戶之間更有可能發(fā)生交互，該模型允許每個(gè)用戶隨著網(wǎng)絡(luò)結(jié)構(gòu)的演化而逐漸移動(dòng)其在潛在空間中的位置。

2 挑戰(zhàn)與展望

目前關(guān)于動(dòng)態(tài)信息網(wǎng)關(guān)鍵技術(shù)的研究仍然面臨著很多挑戰(zhàn)。首先，動(dòng)態(tài)信息網(wǎng)上仍然存在著大量十分重要、實(shí)用的關(guān)鍵問題，但卻被以往的研究工作所忽略，發(fā)現(xiàn)這些問題并給出合理的形式化定義是一個(gè)重要挑戰(zhàn)。其次，真實(shí)世界中的動(dòng)態(tài)信息網(wǎng)常常規(guī)模龐大、并且具有很高的數(shù)據(jù)演化速率，很多的關(guān)鍵問題都是復(fù)雜而難解的。因此，恰當(dāng)?shù)剡x取合適的數(shù)據(jù)結(jié)構(gòu)來(lái)維護(hù)動(dòng)態(tài)信息網(wǎng)上的數(shù)據(jù)，與此同時(shí)建立合理的模型有效地刻畫動(dòng)態(tài)信息網(wǎng)上對(duì)象和聯(lián)系的不同動(dòng)態(tài)行為特征是非常有必要的。此外，設(shè)計(jì)出適用于大規(guī)模、更新頻繁的動(dòng)態(tài)信息網(wǎng)的時(shí)空高效的關(guān)鍵技術(shù)，有效地解決這些問題也是很具有挑戰(zhàn)性的。

關(guān)于未來(lái)可能的研究方向，第一，可以考慮利用壓縮、采樣、并行等方法設(shè)計(jì)出適用于真實(shí)世界中包含著數(shù)以億計(jì)的對(duì)象和聯(lián)系的大規(guī)模動(dòng)態(tài)信息網(wǎng)的若干關(guān)鍵技術(shù)。第二，可以關(guān)注更加復(fù)雜但同樣普遍存在的動(dòng)態(tài)信息網(wǎng)（如動(dòng)態(tài)異構(gòu)信息網(wǎng)、動(dòng)態(tài)超圖信息網(wǎng)等）的關(guān)鍵技術(shù)研究。

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

動(dòng)態(tài)信息網(wǎng)關(guān)鍵技術(shù)的研究已經(jīng)成為近年來(lái)的研究熱點(diǎn)。本文對(duì)社區(qū)探測(cè)和社區(qū)搜索、離群點(diǎn)探測(cè)、影響力最大化、鏈接預(yù)測(cè)的概念、發(fā)展及其在動(dòng)態(tài)信息網(wǎng)上的研究進(jìn)展進(jìn)行了詳細(xì)的闡述。最后，本文討論了動(dòng)態(tài)信息網(wǎng)關(guān)鍵技術(shù)仍然面臨的挑戰(zhàn)，并且對(duì)未來(lái)可能的研究方向進(jìn)行了展望。