動態信息網關鍵技術的研究進展

王芯蕊，高 宏

（哈爾濱工業大學 計算機科學與技術學院，哈爾濱 150001）

0 引言

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

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

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

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

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

1 動態信息網關鍵技術研究現狀

1.1 社區探測和社區搜索

社區探測的目的在于識別網絡中所有的社區。

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

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

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

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

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

上述部分工作研究了動態網絡上的社區搜索問題。這些工作主要考慮的是如何設計在線算法及時計算出動態網絡上每個當前時刻的社區搜索結果。

1.2 離群點探測

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

由于數據類型的不同，離群點探測的方法也各有不同。例如，一種常用的離群點探測方法是基于聚類的，這種方法將離群點歸為聚類分析的附加產物，也就是說，在對所有數據點執行聚類操作后，那些不屬于任何簇的點就是離群點。其他常用的方法還有基于統計學的方法、基于神經網絡的方法等等。

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

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

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

1.3 影響力最大化

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

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

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

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

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

1.4 鏈接預測

鏈接預測是指預測未來可能出現的對象之間的新聯系。鏈接預測可以用于朋友推薦、市場分析、商業智能等多個領域。因此，近年來，鏈接預測問題得到了各方面的關注和重視。

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

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

2 挑戰與展望

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

關于未來可能的研究方向，第一，可以考慮利用壓縮、采樣、并行等方法設計出適用于真實世界中包含著數以億計的對象和聯系的大規模動態信息網的若干關鍵技術。第二，可以關注更加復雜但同樣普遍存在的動態信息網（如動態異構信息網、動態超圖信息網等）的關鍵技術研究。

3 結束語

動態信息網關鍵技術的研究已經成為近年來的研究熱點。本文對社區探測和社區搜索、離群點探測、影響力最大化、鏈接預測的概念、發展及其在動態信息網上的研究進展進行了詳細的闡述。最后，本文討論了動態信息網關鍵技術仍然面臨的挑戰，并且對未來可能的研究方向進行了展望。