動態(tài)信息網(wǎng)關(guān)鍵技術(shù)的研究進展

王芯蕊，高 宏

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 離群點探測

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

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

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

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

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

1.3 影響力最大化

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

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

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

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

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

1.4 鏈接預(yù)測

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

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

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

2 挑戰(zhàn)與展望

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

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

3 結(jié)束語

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