王友國，柴 允，朱 亮

(1.南京郵電大學 理學院，江蘇 南京 210023 2.南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，人類社會已經(jīng)全面步入了Web3.0時代［1］。作為Web3.0在社交網(wǎng)絡中應用的產(chǎn)物，F(xiàn)acebook、Twitter、微博等日益普及，極大地改變了信息的傳播方式［2］。沒有物理空間的限制，個人或組織之間的互動也更加靈活多樣［3］。然而，這種信息傳播的便捷性同時也是一把雙刃劍，例如惡意的謠言和計算機病毒等也能夠通過網(wǎng)絡快速傳播。因此，對復雜網(wǎng)絡中的信息傳播相關(guān)問題的研究具有重要意義。

目前，復雜網(wǎng)絡中的信息傳播問題已經(jīng)有了大量研究工作，如分析信息傳播的機制，預測信息的流行度，尋找信息擴散的源頭等［4］。這些工作主要可以劃分為宏觀上的數(shù)據(jù)分析以及微觀上的建模分析。其中，宏觀上信息擴散的分析研究大多基于機器學習方法，側(cè)重于網(wǎng)絡結(jié)構(gòu)分析和經(jīng)驗數(shù)據(jù)挖掘。其中，利用大數(shù)據(jù)采集樣本集，通過訓練模型參數(shù)進行回歸分析，便是預測網(wǎng)絡中信息流行度的一類常用方法［5］，例如2010年提出的SH（Szabo-Huberman）模型［6］。宏觀分析的研究對象往往是整個網(wǎng)絡，通過數(shù)據(jù)挖掘方法，統(tǒng)計信息傳播過程中的各種特性，其優(yōu)勢在于僅通過現(xiàn)有的樣本信息及參數(shù)訓練，即可對流行度進行預測，或是構(gòu)建出近似的網(wǎng)絡拓撲結(jié)構(gòu)。但其本質(zhì)是一個黑箱，實際過程中的信息傳播路徑和潛在的傳播機制都是未知的。因此，從微觀角度構(gòu)建信息擴散模型，并基于擴散模型對信息傳播相關(guān)問題進行研究是必要的。本文從信息擴散模型和信息溯源方法兩方面總結(jié)了現(xiàn)有的相關(guān)研究，并從考慮隨機擾動等角度對后續(xù)的工作進行了展望。

1 信息擴散模型

本節(jié)介紹了常見的信息擴散模型及其研究現(xiàn)狀。圖1列出了3個主要的模型分類及其部分子類。

1.1 傳染病模型

1.1.1 確定性模型

由于信息擴散與病毒傳播之間存在一定的相似性，因此，基于平均場理論（Mean-Field Theory）和滲流理論（Percolation Theory）的傳染病模型被廣泛應用于社交網(wǎng)絡上的傳播動力學研究［7-9］。這類模型將網(wǎng)絡中的節(jié)點劃分為不同的狀態(tài)，根據(jù)對節(jié)點狀態(tài)的劃分，主要有SI（Susceptible-Infected）模型［10］、SIS（Susceptible-Infected-Susceptible）模 型［11］、SIR（Susceptible-Infected-Recovered）模型［12］、SIRS（Susceptible-Infected-Recovered-Susceptible）模 型［13］和SEIR（Susceptible-Exposed-Infected-Recovered）模型［14］等。

在這些模型的基礎(chǔ)上，有學者考慮節(jié)點活躍性、群組傳播、個體行為等影響，進行了擴展和補充［15-17］。此外，也有學者結(jié)合了博弈論改進傳染病模型［18-20］?？紤]到一些競爭類型的信息通常會同時在社交網(wǎng)絡中傳播，例如某個話題的正面和負面信息，或者來自不同公司的類似產(chǎn)品的營銷信息。于是一些學者通過修正傳染病模型研究競爭性雙重信息擴散的動力學［21-23］。

1.1.2 隨機性模型

上述經(jīng)典的擴散模型都是確定性模型，往往用常微分方程（Ordinary Differential Equation，ODE）進行表示。然而，在信息的擴散過程中，既存在自發(fā)的、不可控制的內(nèi)部隨機擾動，如網(wǎng)絡連接性的變化、人類自身行為決策的不確定性；也存在可引導的、可控的外部隨機擾動，如有關(guān)部門發(fā)布辟謠信息、控制hub節(jié)點、封閉信源節(jié)點等措施，從而遏制信息擴散等。因此，在經(jīng)典模型的基礎(chǔ)上考慮信息擴散過程中的隨機性，構(gòu)建隨機模型將幫助更好地理解實際網(wǎng)絡中的信息傳播機制。

在生物種群網(wǎng)絡中，Mao等［24］利用隨機微分方程（Stochastic Differential Equation，SDE）對經(jīng)典Lotka-Volterra模型進行修正，研究了環(huán)境噪聲對種群繁衍滅絕的影響。而在社交網(wǎng)絡中，為了捕捉網(wǎng)絡拓撲動態(tài)變化的特性并研究其對信息傳播的影響，Liu等［25］提出了一種基于費米函數(shù)（Fermi Function）的鏈路重布線策略，并在SIR模型中表明了該重布線策略可以使信息傳播得更快更廣。之后，Ally等［26］進一步探討了重布線策略對信息擴散過程的影響。Zhao等［27］認為網(wǎng)絡的環(huán)境噪聲對用戶最佳決策的制定存在影響，該過程可描述為一個高斯隨機過程。

另外，還有學者結(jié)合模糊理論，在離散演化模型中分析觀點構(gòu)成與決策制定中的隨機擾動［28］。Zhu等［29］考慮了信息渠道的時變特性，研究了復雜網(wǎng)絡上的信息擴散過程以及信息更新機制的影響。隨后，Zhu等［30］和Chai等［31］分別將網(wǎng)絡連接和人口的隨機變化表示為信息擴散過程中的噪聲，并利用標準Brownian運動加以描述。研究發(fā)現(xiàn)，隨著噪聲強度的不斷增強，系統(tǒng)性能并非呈線性下降趨勢，具體表現(xiàn)在少量網(wǎng)絡連接噪聲的加入，將有效增大信息擴散規(guī)模并縮短其生存周期。

相關(guān)研究已初步證實在復雜網(wǎng)絡系統(tǒng)中，系統(tǒng)性能的改善與隨機擾動并非完全對立。利用SDE描繪擾動下的信息擴散動力學，研究網(wǎng)絡中擾動的形式與強度，比較準確地刻畫信息傳播特征，或是利用擾動提升系統(tǒng)性能等是本領(lǐng)域可以繼續(xù)拓展的方向。

1.1.3 時空擴散模型

目前已有的研究主要集中在信息擴散的時間方面的建模?？紤]空間擴散的物理意義，嘗試同時從時間和空間兩個維度理解信息傳播，可構(gòu)建基于偏微分方程（Partial Differential Equation，PDE）的時空擴散模型。Wang等［32］首先提出了一個基于PDE的擴散Logistic模型模擬信息擴散的時空特征。作者在一個從Digg網(wǎng)站收集的真實數(shù)據(jù)集中表明了時間和空間模式的存在，并驗證了所提模型在預測信息擴散過程中的有效性。隨后，Wang等［33］進一步探討了信息擴散的時空特征。作者同時考慮了空間人口密度和用戶對信息興趣的時間衰減的影響，并提出了一個更簡單的PDE模型。在那之后，Zhu等［34］同時考慮了度分布和距離分布的異構(gòu)性，在時空框架下建立了一個具有人類行為不確定性的PDE信息擴散模型。最近，Zhu等［35］討論了如何通過聚類定義在線社交網(wǎng)絡中的空間距離問題，然后提出了一個具有時間延遲的PDE模型，描述信息在時間和空間兩個維度上的傳播。

PDE模型為研究復雜網(wǎng)絡中的信息傳播提供了一個新的視角。然而，由于現(xiàn)有的這方面的研究工作還比較有限，因此還有許多問題需要解決。從理論的角度分析、建立或擴展基于PDE的信息擴散模型，并通過大數(shù)據(jù)對模型進行驗證，有待以后進一步的研究開展。

1.2 其他模型

除傳染病模型外，還有一些信息擴散模型用于研究復雜網(wǎng)絡中的信息傳播相關(guān)問題，其中常見的有獨立級聯(lián)（Independent Cascade，IC）模型［36］、線性閾值（Linear Threshold，LT）模型［37］以及基于博弈論的擴散模型［38-41］等。

1.2.1 基于信息級聯(lián)的擴散模型

在IC模型和LT模型中，信息通過級聯(lián)在網(wǎng)絡中傳遞，每個節(jié)點可能的狀態(tài)為活躍態(tài)或非活躍態(tài)。其中，活躍節(jié)點為主動傳播的節(jié)點，其他則為非活躍節(jié)點，并且一旦節(jié)點處于活躍態(tài)，它就不能再變回非活躍態(tài)。IC模型本質(zhì)上是一個隨機過程，其假設每個活躍節(jié)點只有一次機會激活它的一個非活躍的鄰近節(jié)點。而LT模型則會為每條鏈路分配一個權(quán)重，表示一個節(jié)點對目標節(jié)點的影響，同時，每個節(jié)點都有一個隨機指定的閾值。當來自鄰近活躍節(jié)點的鏈路的影響權(quán)值之和超過指定的閾值后，該節(jié)點就會成為活躍節(jié)點。

IC模型和LT模型以有向圖的形式描述了信源到其他節(jié)點的信息流，而在此基礎(chǔ)上通過對網(wǎng)絡反向擴散的分析，有助于實現(xiàn)影響最大化［36-37］，預測級聯(lián)的發(fā)展［42］或信息溯源［43］等。

1.2.2 基于博弈論的擴散模型

基于博弈論的擴散模型假設一條信息的傳播或不傳播取決于成本、收益和戰(zhàn)略選擇的影響，來研究信息擴散動力學。Jiang等［38］同時考慮社交網(wǎng)絡用戶的決策、行動和社會經(jīng)濟互動，提出了一個演化博弈框架模擬社交網(wǎng)絡中的動態(tài)信息擴散過程。隨后，Wang等［39］考慮了用戶在決定是否采取特定策略時的不確定性，將社交網(wǎng)絡中的謠言擴散建模為一個協(xié)調(diào)博弈。Li等［40］和Liu等［41］分別從文本識別和阻斷謠言傳播的角度，將謠言制造者和多個傳播者之間的關(guān)系視為一個博弈，以謠言爆炸程度和源節(jié)點的信任程度作為謠言產(chǎn)生和傳播的影響因素，建立了ET（Explosion-Trust）博弈模型，尋求博弈均衡。此外，基于博弈論的擴散模型也被用于研究實現(xiàn)影響最大化［44］、混淆信息源［45］等問題。

2 溯源方法

復雜網(wǎng)絡中的信息溯源問題是信息擴散的逆向問題，經(jīng)典的溯源方法主要有基于節(jié)點屬性和基于傳播模型兩種。基于節(jié)點屬性的方法，主要通過對節(jié)點屬性（動力學重要性、源節(jié)點中心度等）進行量化、對比，從而判斷哪些節(jié)點是信源節(jié)點［46-47］。基于傳播模型的推理法則通過假定信息傳播符合某種模式，推理出信息可能的源節(jié)點。溯源問題的一個重要組成部分是在傳播過程中觀察節(jié)點的狀態(tài)，對于不同的觀察方法需要開發(fā)不同的方法。為此，Jiang等［48］列舉了3種主要的觀察類型：完全觀察（Complete Observations）、快照觀察（Snapshots Observations）和傳感器觀察（Sensor Observations）。此外，根據(jù)信源數(shù)的不同，溯源方法又可以分為單源識別方法和多源識別方法。圖2總結(jié)了部分現(xiàn)有的溯源方法并根據(jù)上述特征進行了分類。

2.1 單源識別

目前已經(jīng)有許多關(guān)于單信源溯源問題的研究。其中，Shah等［49］率先系統(tǒng)地研究了信源識別問題。作者開發(fā)了一個基于可能傳播路徑數(shù)的謠言中心（Rumor Center，RC）估計量來檢測信源，并證明了該估計量是一類樹圖的極大似然估計量（Maximum Likelihood Estimator，MLE）；然后假定信息傳播服從寬度優(yōu)先搜索（Breadth First Search，BFS），將RC推廣至一般網(wǎng)絡中。在此基礎(chǔ)上，Dong等［50］考慮部分可疑節(jié)點集先驗已知的情況，提出了一個局部謠言中心（Local Rumor Center，LRC）的信源估計方法。之后，Zhu等［51］提出了一種基于采樣路徑的方法，并且證明了對于樹狀圖，該方法的輸出是一個Jordan中心（Jordan Center，JC），即一個能夠最小化到其他節(jié)點的最大距離的節(jié)點。

在上述工作之后，許多學者做出了改進工作，如考慮受限觀察、多次觀察或信息以異構(gòu)傳播率擴散等情況下的溯源問題［52-54］。最近，Kesavareddigari等［55］提出了一種類型中心（Types Center，TC）方法估計樹狀網(wǎng)絡上的信息源。一些方法則關(guān)注將樹狀網(wǎng)絡的約束放寬到一般網(wǎng)絡上，如Gaussian方法［56-58］、動態(tài)消息傳輸（Dynamic Message Passing，DMP）方法［59］、Bayesian方法［60］以及馬爾可夫鏈蒙特卡羅（Markov Chain Monte Carlo，MCMC）方法［61］等。另外，一些研究人員基于無向帶權(quán)網(wǎng)絡考慮單源識別問題［62-63］。

2.2 多源識別

由于信息傳播具有高度動態(tài)的特點，并且當從不同的來源開始傳播時往往呈現(xiàn)出各種各樣的模式［64］。因此，相比于單源的情況，多源識別問題更加具有挑戰(zhàn)性。

Prakash等［65-66］最先研究SI模型下的多源識別問題。作者利用最小描述長度（Minimum Description Length，MDL）方法確定源節(jié)點的數(shù)量，然后根據(jù)多個未受感染鄰居對受感染節(jié)點的免疫權(quán)確定最佳的源節(jié)點。Luo等［67］提出了一種多謠言中心（Multi-Rumor-Center，MRC）方法識別多個源，并嘗試估計每個源的感染區(qū)域。Chen等［68］擴展出了多Jordan中心（Multi-Jordan-Center，MJC）方法。隨后，Jiang等［69］提出了一種K中心（K-Center，KC）方法識別無向帶權(quán)網(wǎng)絡中的多個信源，該方法通過有效距離（Effective Distance，ED）［70］改變原始網(wǎng)絡，以便對復雜的擴散過程有一個清晰的理解，然后采用容量約束網(wǎng)絡Voronoi圖［71］對網(wǎng)絡進行劃分。考慮到多個信源可能在不同的時刻開始傳播信息的情況，Ji等［72］引入了重心（Heavy Center，HC）開發(fā)估計雙信源的框架，并將該框架推廣到多源估計。Feizi等［73］認為在一些情況下，擴散動力學的完整表征可能是不必要的，因此，作者通過創(chuàng)建一個擴散核來近似標準的擴散模型，并基于此提出了一個網(wǎng)絡注入（Network Infusion，NI）方法推斷一般網(wǎng)絡中的多個信源。Tang等［74］和Ji等［75］引入了Gromov矩陣表示未加權(quán)樹和加權(quán)樹，并提出了一種新的Gromov方法代替信源估計問題中常用的BFS生成樹啟發(fā)式方法，然后，作者證明了Gromov方法在信源估計和網(wǎng)絡推理問題中的有效性。

2.3 時變網(wǎng)絡上的源識別

雖然信源識別在過去十年中吸引了越來越多的研究人員的關(guān)注，但是大多數(shù)現(xiàn)有的溯源方法仍然只能適用于靜態(tài)網(wǎng)絡。然而，現(xiàn)實的網(wǎng)絡大多數(shù)是隨時間和空間持續(xù)變化的，結(jié)構(gòu)完全固定的網(wǎng)絡非常少見［76］。因此，基于時變網(wǎng)絡開發(fā)出有效的溯源方法在實際應用中有著重要的意義。

到目前為止，關(guān)于時變網(wǎng)絡中信源估計的研究還相對較少。Antulov-Fantulin等［77］提出了一種基于靜態(tài)網(wǎng)絡的溯源框架，并通過仿真在經(jīng)驗時間網(wǎng)絡中驗證了該框架具有一定的適用性。Jiang等［78］最先專門研究時變網(wǎng)絡中的單源估計問題，作者將時變網(wǎng)絡表示為一系列靜態(tài)快照，并采用反向傳播的方法縮小可疑節(jié)點的范圍，然后，采用微觀擴散模型從可疑節(jié)點集中尋找MLE。隨后，Hu等［79］提出了利用一組信使節(jié)點在時變網(wǎng)絡中檢測多個信源的通用框架。

2.4 展望

經(jīng)典的溯源方法雖然分別從節(jié)點自身和信息傳播過程構(gòu)建溯源模型，但均沒有考慮網(wǎng)絡擾動對信息傳播的影響，其網(wǎng)絡拓撲結(jié)構(gòu)在整個傳播過程中保持固定，同時也忽略了傳播過程中的其余信息，如外部隨機擾動對其傳播造成的影響?，F(xiàn)有的少量基于時變網(wǎng)絡的溯源方法，如Jiang等提出的MLE方法則面臨每條邊的傳播概率必須已知，計算復雜度較高以及難以推廣到多信源情況等問題。而Hu等開發(fā)的框架則必須滿足一個基本前提，即信息的真實擴散時間是已知的，這在實際應用中往往也難以獲取。因此，考慮描述網(wǎng)絡拓撲結(jié)構(gòu)的動態(tài)變化或用戶行為的不確定性等內(nèi)部擾動，以及其他干預等外部擾動，對經(jīng)典的溯源方法進行改進，將其推廣到含噪的一般網(wǎng)絡中，開發(fā)更為精確、計算復雜度低且適用性更廣的溯源方法，是信息溯源領(lǐng)域需要繼續(xù)拓展的方向。

3 網(wǎng)絡數(shù)據(jù)集

在復雜網(wǎng)絡領(lǐng)域中，圖通常被用來表示各種網(wǎng)絡，例如生物網(wǎng)絡、社交網(wǎng)絡、計算機網(wǎng)絡和電力網(wǎng)絡等。本節(jié)介紹了一些復雜網(wǎng)絡中信息傳播相關(guān)問題的常用網(wǎng)絡數(shù)據(jù)集，分為合成數(shù)據(jù)集和真實數(shù)據(jù)集。

3.1 合成數(shù)據(jù)集

3.1.1 樹狀網(wǎng)絡

樹狀網(wǎng)絡中沒有回路，節(jié)點之間的路徑唯一，在計算傳播路徑數(shù)或路徑長度時比較方便。因此，一些學者在研究溯源問題時，首先關(guān)注樹狀網(wǎng)絡上的傳播過程。最常用的樹狀網(wǎng)絡為正則樹［49］和隨機樹［51］。其中，正則樹中的每個節(jié)點具有相同的度，而隨機樹的每個節(jié)點的度是隨機選擇的。圖3（a）和圖3（b）分別展示了一個2-正則樹和一個隨機樹的示例。

3.1.2 一般網(wǎng)絡

相較于拓撲結(jié)構(gòu)過于簡單的樹狀網(wǎng)絡，一般網(wǎng)絡更加貼近于現(xiàn)實中的網(wǎng)絡結(jié)構(gòu)。目前，復雜網(wǎng)絡領(lǐng)域內(nèi)3種最具代表性的合成網(wǎng)絡經(jīng)常用于研究各種信息傳播相關(guān)問題，它們分別是WS網(wǎng)絡［80］、ER網(wǎng)絡［81］和BA網(wǎng)絡［82］。WS網(wǎng)絡具有小世界特性，即網(wǎng)絡直徑小、平均路徑短，因此其中大多數(shù)節(jié)點可以在幾跳內(nèi)從另一個節(jié)點遍歷。ER網(wǎng)絡本質(zhì)上是帶有主觀度分布的隨機圖，是通過隨機關(guān)聯(lián)網(wǎng)絡中的節(jié)點構(gòu)建的，其中的每條邊都以概率p添加到圖中，并且這個過程獨立于網(wǎng)絡中的其他邊。網(wǎng)絡的無標度特性指的是網(wǎng)絡中節(jié)點的度遵循冪律分布，而BA網(wǎng)絡便是一種典型的無標度網(wǎng)絡。另外，還有一種構(gòu)建無標度網(wǎng)絡的方法是使用配置模型［83］。圖4展示了當節(jié)點數(shù)為15時，3種網(wǎng)絡對應的示例。

此外，Python語言軟件包NetworkX能夠創(chuàng)建合成網(wǎng)絡，并可以用于研究復雜網(wǎng)絡的形成、動力學或功能［84］。還有一些其他的專門生成合成網(wǎng)絡的方法，如R-Mat、Darwini和Datasynth等［85］。

3.2 真實數(shù)據(jù)集

3.2.1 靜態(tài)網(wǎng)絡

復雜網(wǎng)絡領(lǐng)域內(nèi)的學者已經(jīng)共享了許多網(wǎng)絡數(shù)據(jù)集。例如，Power Grid（PG）數(shù)據(jù)集［80］收集了美國西部各州的電網(wǎng)數(shù)據(jù)，代表了無向、無權(quán)的網(wǎng)絡拓撲結(jié)構(gòu)。Astrophysics Collaborations（AC）數(shù)據(jù)集［86］收集了1995年1月1日至1999年12月31日期間，科學家在天體物理學電子打印檔案中發(fā)布預印本的加權(quán)合作網(wǎng)絡。包括上述兩個數(shù)據(jù)集在內(nèi)的多個數(shù)據(jù)集以及相關(guān)網(wǎng)絡分析工具可以在Newman的個人網(wǎng)站［87］或Chen的個人網(wǎng)站［88］上自由獲取。

斯坦福大學的網(wǎng)絡分析項目［89］共享了許多包括Facebook、Google+、Twitter等［90］大型社交網(wǎng)絡在內(nèi)的真實網(wǎng)絡數(shù)據(jù)集。表1列舉了從這些開源網(wǎng)站中獲取的部分靜態(tài)網(wǎng)絡的統(tǒng)計特征。

表1 部分靜態(tài)網(wǎng)絡的統(tǒng)計特性

3.2.2 時變網(wǎng)絡

時變網(wǎng)絡對應的時間數(shù)據(jù)集一般包括節(jié)點和持續(xù)時間內(nèi)對應的時間鏈路。Sigcomm09［91］數(shù)據(jù)集包含了在西班牙巴塞羅那SIGCOMM 2009會議期間76個藍牙設備的連接痕跡。每臺設備每120±10.24 s定期搜尋一次附近的藍牙設備。MIT［92］數(shù)據(jù)集則收集了2004—2005學年期間麻省理工學院97個學科的交流情況。

HT09和SGinfectious數(shù)據(jù)集［93］來自SocioPatterns項目［94］，通過在徽章中嵌入主動射頻識別裝置檢測人與人之間面對面的對話。其中，HT09數(shù)據(jù)集是在2009年ACM超文本會議上收集的，該會議由科學交流基金會在意大利都靈舉辦，時間從2009年6月29日至7月1日。而SGInfectious數(shù)據(jù)集是在2009年4月17日至7月17日在愛爾蘭都柏林科學畫廊舉辦的“INFECTIOUS：STAY AWAY”藝術(shù)科學展覽期間收集的。

斯坦福大學的網(wǎng)絡分析項目［89］還囊括了許多真實的時變網(wǎng)絡數(shù)據(jù)集，例如，用一家大型歐洲研究機構(gòu)的電子郵件數(shù)據(jù)生成的Email-Eu數(shù)據(jù)集；而Math，Ask，Super和Stack這4個數(shù)據(jù)集則通過收集Stack Exchange問答網(wǎng)站上不同站點的數(shù)據(jù)生成：分別是Math Overflow，Ask Ubuntu，Super User和Stack Overflow。表2列出了部分時間數(shù)據(jù)集的統(tǒng)計結(jié)果。

表2 部分時間數(shù)據(jù)集的統(tǒng)計結(jié)果

4 結(jié)束語

研究復雜網(wǎng)絡中的信息擴散機制以及溯源方法是兩個同時具備基礎(chǔ)性和挑戰(zhàn)性的課題，擁有著廣泛的應用前景。本文總結(jié)了信息擴散模型和溯源方法的研究現(xiàn)狀，介紹了不同模型與方法的優(yōu)缺點，并對后續(xù)的相關(guān)研究進行了展望。列舉的一些公開常用的網(wǎng)絡數(shù)據(jù)集可以方便學者進行后續(xù)研究?？梢灶A見，信息傳播相關(guān)問題的研究進展將會是非常迅速的。