無需感染時間信息的傳播網絡快速推斷算法*

孫月明，張運加，顏 錢，陳 璐，黃 浩+，高云君

1.武漢大學 計算機學院，武漢 430072

2.奧爾堡大學 計算機科學系，丹麥 奧爾堡 DK-9220

3.浙江大學 計算機科學與技術學院，杭州 310027

1 引言

傳播網絡推斷（diffusion network inference）是根據在多次傳播過程中各個節點的受感染情況來分析推斷這些節點之間的影響關系以及感染傳播概率（transmission rates）。其中每一條影響關系是一條從某父節點到某子節點的有向邊，表示當該父節點被感染時會將其感染的內容（如傳播的疾病、觀點或信息等）傳播給該子節點，從而影響該子節點的感染狀態；而感染傳播概率則表示的是已感染父節點將其感染內容傳播給其未被感染的子節點時，造成該子節點被成功感染的概率，該概率量化地反映傳播網絡中的影響關系強度。掌握傳播網絡中的影響關系和感染傳播概率能夠幫助人們理解傳播網絡中的傳播過程，從而更好地對未來的傳播行為進行預測。例如，疾病防疫部門可以基于疾病傳播網絡對易感人群做出防控部署，輿情監控人員可基于輿論傳播網絡預測輿論的發展趨勢[1-2]。

現有的絕大多數的傳播網絡推斷算法所需要的輸入數據包括：（1）節點感染狀態觀測數據，即每次傳播過程結束后，觀測得到的目標傳播網絡中各個節點的感染狀態（通常狀態“1”表示節點被“感染”，接受了某一傳播內容；狀態“0”表示節點“未被感染”，未接受該傳播內容）。（2）各節點在各傳播過程中被感染的確切時間。在這些算法中，由于感染時間信息的存在，節點之間影響關系的推斷較為容易。一般來說，如果節點的感染時間相隔在一定時間范圍內，則認為這些節點可能存在影響關系[1,3-6]；這些節點中，先感染的節點被認為是后感染的節點的潛在的父節點（父節點對其子節點存在影響關系，子節點的感染是由于其父節點將傳播內容傳播給了該子節點）[7]。

雖然在有些傳播過程中，例如在線社交媒體中的輿論信息傳播過程，感染時間信息可以相對容易地被記錄、被獲得，但是在眾多真實世界的傳播過程中，例如疾病傳播過程，真實、確切的感染時間信息往往是缺失的[8]。這是因為實時監控感染狀態或者定期做感染狀態的全面普查在真實世界中是極為費時費力的。而且即使以上條件能夠達到，由于各節點的感染潛伏期（由被感染到表現出癥狀的時間）不同等客觀原因，所觀測得到的感染時間未必能反映各節點真實、確切的感染時間。因此，在真實世界的應用中，現有的絕大多數的傳播網絡推斷算法的可用性、準確性受到較大的限制。

為了避免現有絕大多數方法的局限性，本文旨在研究一種準確、高效且無需感染時間信息的傳播網絡推斷方法。為此，本文提出了FINITI（fast inference of diffusion networks without infection temporal information）算法，可以僅僅利用多次傳播過程結束時觀測得到各節點的感染狀態來推斷傳播網絡中節點之間的影響關系和感染傳播概率。該算法首先利用節點感染狀態之間的互信息來量化它們之間的相互關聯。由于多數節點感染狀態之間并不存在較強關聯，因此大多數互信息數值較低，從而形成內聚性。通過這種較低互信息之間的內聚性，可將有強關聯的節點與關聯較低的節點區分開來，從而找出可能的節點之間影響關系。然后，該算法構建以感染傳播概率為變量的節點感染狀態觀測數據的對數似然函數，并采用期望最大化（expectation maximization，EM）的方法最大化該對數似然函數并求解感染傳播概率。實驗結果表明，與現有方法相比，本文所提出的FINITI算法有效地提高了傳播網絡推斷的準確性，并且大幅地縮短了算法運行所需要的時間。

本文的主要貢獻包括：（1）提出了一種基于感染狀態之間互信息的節點間影響關系推斷方法，該方法不再依賴感染時間信息來確定潛在的父子節點；（2）提出了一種感染傳播概率和節點感染狀態觀測數據的匹配方法，并形式化為對數似然函數，該函數可采用EM方法快速求解。

本文的組織結構如下：第2章介紹現有相關工作；第3章給出本文研究問題的形式化描述；第4章詳細介紹本文所提出的FINITI算法；第5章報告實驗結果與分析；第6章總結全文。

2 相關工作

現有的傳播網絡推斷方法可以被劃分為兩大類：（1）基于感染時間信息的推斷方法；（2）不依賴感染時間信息的推斷方法。

2.1 基于感染時間信息的推斷方法

現有的絕大多數傳播網絡推斷方法需要使用傳播網絡中各節點確切的感染時間作為分析推斷的依據。根據所采用的技術原理不同，這些方法可以分為基于凸優化的方法、基于目標函數子模性質（submodularity）的方法、基于嵌入空間的方法。

2.1.1 基于凸優化的方法

該類方法通過節點的感染時間信息確定各節點潛在的父節點。該類方法大多假設父子節點之間的感染傳播過程符合獨立級聯（independent cascade）模型或者線性閾值（linear threshold）模型[4,9]，并利用這些模型從潛在的父節點中推斷出最可能的傳播網絡影響關系拓撲結構，或者為潛在的父子節點對推斷出最可能的感染傳播概率方案，使得節點感染狀態觀測數據的似然度最大，即所推斷的傳播網絡影響關系拓撲結構或感染傳播概率方案最有可能產生這些節點感染狀態觀測數據。該類方法通過構造合理的目標函數（一般是凸函數），將傳播網絡推斷問題轉化為凸優化問題，并采用連續二次最優化[5]、EM算法[10]、塊坐標下降法[11]、隨機梯度法[6]、近端梯度法[12]、生存論（survival theory）[1]、稀疏恢復[13]以及將整個優化問題分解為多個可并行的子問題[14]等手段來求解或逼近目標函數的最優解。該類方法大多在類似樹形或稀疏的傳播網絡上可獲得良好的推斷結果。

2.1.2 基于目標函數子模性質的方法

該類方法與基于凸優化的方法較類似，旨在推斷出最有可能產生節點感染狀態觀測數據的潛在傳播網絡。不過，在該類方法中，因為所構造的目標函數具有子模性質，所以傳播網絡推斷問題被轉化為求子模函數（submodular function）最大值的問題。NetInf算法[4]和MultiTree算法[3]是兩種最典型的基于子模性質的方法。由于目標函數的子模性質，該類方法都采用貪婪算法來尋找目標函數最大值的近似最優解。不同的是，NetInf等算法為了追求更高的效率，在求解時只考慮最有可能的傳播樹；而MultiTree等算法為了獲得更加準確的推斷結果，在求解時考慮全部可能的傳播樹。

2.1.3 基于嵌入空間的方法

該類方法將傳播網絡中的節點投影到一個潛在的嵌入空間。在該嵌入空間中，節點之間的距離反映著它們之間影響關系強度。該類方法通常使用威布爾分布（Weibull distribution）[15]、均勻分布[16-17]或者核函數[18]來對節點間影響關系強度進行建模，并通過節點的感染時間信息和感染狀態觀測數據來學習模型參數。雖然該類方法不能像基于凸優化和子模性質的方法一樣顯式地構造出傳播網絡的圖結構，但是它們可以幫助用戶通過一個低維可視化空間更加直觀地觀察傳播網絡中各節點之間的影響關系。

以上三類傳播網絡推斷方法皆需完整和準確的感染時間信息。已有研究證明當節點感染狀態觀測數據量足夠大且對應節點感染時間信息完整、準確時，目標傳播網絡可以通過一些簡單的圖重構方法推斷出來[19]。但是，即使節點感染時間信息可以被記錄，有時也會出現部分時間信息不夠準確或者有所缺失的情況。為此，有一部分研究工作提出了針對此類情況傳播網絡推斷方法[20]。這些方法可視為對以上三類傳播網絡推斷方法的補充，但仍然屬于基于感染時間信息的傳播網絡推斷方法。

2.2 不依賴感染時間信息的推斷方法

在傳播網絡推斷中，感染時間信息可用來幫助確定各節點潛在的父節點，從而一定程度地降低推斷的難度。但是，感染時間信息在許多傳播事件中往往難以獲得。就已公開的文獻和技術資料，在如何不依賴感染時間信息的情況下來完成傳播網絡推斷的相關問題上，目前只有較少研究工作涉及這一富有挑戰性的研究課題，包括：（1）基于路徑跟蹤（path traces）的方法[21]；（2）基于提升效果（lifting effects）的方法[8]。

2.2.1 基于路徑跟蹤的方法

該方法需要的輸入為被傳播路徑串聯的節點三元組集合，其中一個節點三元組為處于同一傳播路徑上前后相連的三個節點。該方法認為具有較高頻率同時出現于不同節點三元組的任意兩個節點之間具有較高的相互影響關系。雖然該方法有較好的數學理論基礎和較高的運行效率，但是需要較為完整的被傳播路徑串聯的節點三元組集合，這個要求在現實應用中往往難以滿足。即使加上感染時間信息，要推斷出確切的被傳播路徑串聯的節點三元組集合也是較為困難的。

2.2.2 基于提升效果的方法

該方法計算傳播網絡中每一個節點u到另一個節點v的提升效果，即當u被感染時，v也被感染的概率的增加程度。該方法不斷找到當前提升效果最高的節點對，并在兩個節點間增加一條有向邊表示它們之間存在影響關系。但需要指出的是，如果該方法不知道目標傳播網絡中共有多少條影響關系，那么它便會不斷地添加有向邊，直到所有節點被有向邊連通。而像目標傳播網絡中共有多少條影響關系這樣的先驗知識在實際應用中往往較難得到。

3 問題描述

在傳播網絡推斷問題中，傳播網絡一般被認為是一個有向圖G=(V,E)，其中V={v1,v2,…,vn}是節點集合，包含該傳播網絡中n個節點；E為節點之間的有向邊的集合，每一條有向邊(vj,vi)代表父節點vj對子節點vi存在影響關系，并常用p(vj,vi)表示節點vj和vi之間的感染傳播概率。p(vj,vi)越大則表示當vj已感染時，若vi未被感染，則vi越有可能被vj感染。此外，在每一次傳播過程中，已感染節點通過有向邊對其相鄰節點中未感染者進行感染，且各節點一旦感染則狀態不變。

本文所研究的無需感染時間信息的傳播網絡推斷問題是在已知n個節點β次傳播過程結束時各個節點的感染狀態數據S={S1,S2,…,Sβ}的情況下，推斷該傳播網絡的節點間影響關系，即有向邊集合E，以及各有向邊對應的感染傳播概率。在給定的節點感染狀態數據S中，表示第?次（1≤?≤β）傳播過程結束時節點感染狀態集合。如，則節點vi在第?次傳播過程中被感染；如，則節點vi在第?次傳播過程中未被感染。

4 FINITI算法

本章首先介紹一種基于節點感染狀態之間互信息的節點間影響關系推斷方法；然后，介紹一種用于匹配感染傳播概率和節點感染狀態數據的對數似然度函數，將求解最優感染傳播概率的問題轉化為最大化該對數似然度函數的問題，并提出基于EM思想的求解方法；最后，給出整個FINITI算法完整步驟以及算法復雜度分析。

4.1 節點間影響關系推斷

一般地，如果在多次傳播過程中，任意兩個節點vi和vj的感染狀態取值si∈{0,1}和sj∈{0,1}滿足等式p(Si=si,Sj=sj)=p(Si=si)p(Sj=sj)，這里Si和Sj表示節點vi和vj的感染狀態變量，那么可以稱節點vi和vj的感染狀態之間相互獨立，不存在關聯關系，也就是說節點vi和vj之間存在影響關系的概率為0。在信息論中，互信息常被用來量化衡量兩個變量之間的關聯關系。

傳統的互信息計算中考慮了兩個節點的全部的四種感染情況，即節點vi和vj所有兩種感染狀態取值（包括0和1）之間的關聯關系。傳統的互信息計算方法是在統計學上衡量兩個節點之間的聯系，而并非節點vi被感染（Si=1）和節點vj被感染（Sj=1）這兩個事件之間的關聯關系。要考察節點之間的影響關系，關心的是兩節點感染事件（Si=1且Sj=1）之間是否存在關聯。因此，提出一種改進后的互信息計算方法來幫助計算兩節點感染事件之間的關聯程度：

Inf(vi,vj)的取值越高代表節點vi和vj感染事件之間關聯關系越高，也就是vi和vj之間存在影響關系的概率越高；反之，如Inf(vi,vj)取值趨近于0，則節點vi和vj之間存在影響關系的概率趨近于0。

通常來說，在傳播網絡中單個節點vi的影響范圍是有限的，也就是說一般只有受到vi影響的較少的節點與vi之間具有明顯較高的改進互信息值；而絕大多數節點與vi之間的改進互信息值通常很低（趨近于0）。因此，大量明顯較低改進互信息取值形成一定內聚性，使之與明顯較高的改進互信息取值區分開來。劃分聚類算法如K-均值算法和支持向量機等都可以幫助找到一個改進互信息閾值τ用來區分明顯較高和明顯較低的改進互信息取值。本文以K-均值算法為例，劃分改進互信息具體方法如下：（1）對每一個節點計算它與其余節點之間的改進互信息；（2）令K=2，運行K-均值算法來將所有互信息取值劃分為兩個聚類；（3）將改進互信息取值較大的聚類中的最小改進互信息取值設為閾值τ。

根據以上閾值τ，可找出對各節點vi∈V可能具有影響關系的潛在父節點集合Fi：

集合Fi指示出節點vi的感染最可能是由哪些節點進行感染傳播造成的，那么接下來要討論的是哪一種節點間感染傳播概率方案最有可能產生β次傳播過程結束時節點的感染狀態數據S。另外，使用聚類算法對互信息的篩選可能產生噪點，即對于每個節點vi∈V，其父節點集合Fi可能包含非真實父節點，這些非真實父節點將在推斷感染傳播概率時被去除。

4.2 感染傳播概率推斷

推斷感染傳播概率的關鍵是如何匹配感染傳播概率和節點感染狀態數據S。為此，提出構建一個以感染傳播概率為變量的節點感染狀態數據的對數似然函數，從而找出一種最有可能產生β感染狀態數據S的節點間感染傳播概率方案。而要考察節點感染狀態數據的似然度（likelihood）需要考慮以下三種情況。

首先，考慮在各個傳播過程中可能造成節點vi成功感染的情況。在第?次(1≤?≤β)傳播過程中，如果vi成功感染，即，那么可能造成vi感染的潛在父節點應該也是被感染狀態（否則無法造成感染傳播），此類潛在父節點集合可記為：

然后，考慮在各個傳播過程中不造成節點vi成功感染的情況。在第?次(1≤?≤β)傳播過程中，如果vi成功感染，即，那么vi的潛在父節點中處于未感染狀態者不能造成vi的感染，此類潛在父節點集合可記為：

則在第?次傳播過程中，節點vi的感染不由中的任一節點造成的概率為。

最后，考慮在各個傳播過程中節點vi未感染的情況。在第?次(1≤?≤β)傳播過程中，如果vi未感染，即，那么可以確定的是vi的潛在父節點中已被感染者未能成功造成vi感染（如果某一潛在父節點也處于未感染狀態則不能確定它與vi之間的感染關系，這種情況不考慮），此類潛在父節點集合可記為：

則在第?次傳播過程中，節點vi未被中任一節點感染的概率為。

根據以上三種情況，可以構建第?次傳播過程中節點感染狀態數據S?的似然度（likelihood）函數L(S?)如下：

由于各傳播過程是相互獨立進行的，全部傳播過程中節點感染狀態數據S的似然度函數L(S)為：

本文的目標是獲得所有的感染傳播概率滿足0≤p(vj,vi)≤1，使得L(S)達到最大值。顯然，L(S)是非線性非凸函數，求解最大值是比較困難和耗時的。因此，采用EM算法來近似求解使得L(S)達到最大值的最優的節點間感染傳播概率方案。這是因為大量實驗結果證明采用EM算法求解最優化問題，通常可以快速收斂局部最優解。

EM算法首先要對目標函數L(S)求一階導數。由于非線性函數一階導數仍然難求，首先可將似然度函數L(S)轉換為對數似然度函數lnL(S)：

同時，對于每組影響關系(vj,vi)，若節點vi在第?次傳播過程中被感染，并且vj是vi的潛在父節點之一，即，則在vi被感染的條件下，vi的感染是由某一潛在父節點vj造成的條件概率K(?,j,i)可以表示為：

為了使得目標函數Q(S)最大化，可通過求解來估計p(v,v)。ij

定理1對p(vj,vi)進行估計如式（2）所示：

其中，S+指所有傳播過程中滿足的傳播過程?的集合；同樣，S-指所有傳播過程中滿足vj∈的傳播過程?的集合，|S-|為集合S-的元素數量。

證明為優化Q(S)，使用計算p(v,v)ij的估計表達式。Q(S)為三項相加的形式，故可對Q(S)的三項分別求導后相加，即若有：

則有：

首先，對于

求偏導。顯然，Q1(S)的偏導如下所示：

為了方便表示，定義S+表示所有傳播過程中滿足的傳播過程的集合。故上式可表示為：

同理可對

分別求偏導數。由于Q2和Q3形式上完全相同，故用如下公式表示：

其中，S-表示所有傳播過程中，滿足或的傳播過程的集合，|S-|表示集合S-的元素個數。

綜上，EM算法迭代運行以下兩步：E步使用式（1），利用感染傳播概率對進行估計；M步使用式（2），最大化感染狀態數據的似然度。經過若干次迭代，EM算法可收斂至p(vj,vi)的局部最優解。

4.3 算法步驟及復雜度分析

4.3.1 算法步驟

算法1為FINITI算法的偽代碼。該算法以各個節點的感染狀態數據S和作為EM算法收斂條件的參數變化閾值err（本文中err取0.000 1）為輸入數據，輸出各個節點vi∈V的父節點集合Fi，以及對應的各個感染傳播概率p(vj,vi)(vj∈Fi)。算法共分為4個主要階段：（1）計算所有的改進互信息（2～6行）；（2）利用K-均值計算改進互信息的閾值τ（7行）；（3）對每個節點vi∈V計算其潛在父節點集合Fi（8～14行）；（4）利用EM算法迭代更新各個感染傳播概率p(vj,vi)直至達到收斂條件（15～30行）。

算法1FINITI算法

輸入：各個節點的感染狀態數據S，閾值err。

輸出：傳播網絡中各節點vi∈V的父節點集合Fi及對應的各感染傳播概率p(vj,vi)(vj∈Fi)。

4.3.2 復雜度分析

FINITI算法在推斷影響關系時，計算互信息需要花費時間為O(n2)，其中n為節點總數。K均值算法中需要對n2個互信息數據進行m次調整中心，故K均值步驟需要O(mn2)。故FINITI算法第一步，生成父節點集合Fi的時間復雜度為O(mn2+n2)。然后，算法第二環節通過EM算法不斷更新K?(?,j,i)和p(vj,vi)，使p(vj,vi)趨于穩定。更新K?(?,j,i)的時間復雜度為O(βn2)，更新p(vj,vi)時，由于需要對每組影響關系進行計算，時間復雜度為O(n2)。設EM算法共需要循環t次，那么第二步EM算法的時間復雜度為O(tβn2+tn2)。綜上，FINITI算法的時間復雜度為O((m+1+tβ+t)n2)。

5 實驗結果與分析

本章首先介紹實驗設置，然后分別討論傳播網絡節點數量、傳播網絡邊密度（邊總數/節點總數）、傳播過程數量、初始感染節點比例等因素對于節點間影響關系以及感染傳播概率推斷準確性及算法運行時間的影響。實驗中所有算法均用Java實現，實驗環境為配置Windows 8操作系統，3.70 GHz的Intel Core i3-6100 CPU以及8 GB內存的臺式電腦。

5.1 實驗設置

采用LFR（Lancichinetti-Fortunato-Radicchi benchmark）基準圖[22]作為人工合成的傳播網絡，測試算法的準確性和運行時間。在LFR網絡中，設置不同的點數量和邊數量生成不同的傳播網絡（見表1）。另外，還采用搜集于微博的真實傳播網絡DUNF[10]，其中含有750個節點（代表微博用戶）和2 794條邊（代表關注和轉發）。

Table 1 LFR networks表1 LFR網絡

在這些人工合成和真實網絡結構上，設置網絡中邊的傳播概率服從均值為0.3，方差為0.05的高斯分布，使得95%以上的概率值集中在0.2至0.4的范圍內。根據獨立級聯模型，模擬了β次爆發無時間信息結果，用于重構這些網絡。

傳播網絡推斷準確性的評價標準主要有F值、均方誤差（mean squared error，MSE），算法效率的評價標準是運行時間。在本實驗中，F值反映的是所推斷出的有向邊（即影響關系）的求全率和求準率的調和平均值，用于評價算法對于影響傳播網絡影響關系的推斷的準確性。均方誤差（MSE）反映的是參數估計值與參數真值之差平方的期望值，用于描述推斷的感染傳播概率的準確性，其計算如下：

其中，p*(vj,vi)為通過FINITI算法估計的傳播概率，而p(vj,vi)為真實傳播概率，n為節點總數。

為進行對比分析，選用一種高性能的基于感染時間信息的算法NetRate[5]和一種高效的不依賴感染時間信息的方法LIFT[8]作為對比方法。其中NetRate算法是采用凸優化的方法，大量實驗證明其結果的準確性常優于基于目標函數子模性質的方法（如MultiTree[3]等）[5]。但要指出的是，由于NetRate算法的輸出為完全圖和兩兩節點間感染傳播概率，故在進行影響關系推斷的準確性比較時，給NetRate算法如下優惠：后驗地找到一個感染傳播概率θ，使得p(vj,vi)≥θ的有向邊(vj,vi)集合的F值達到最大，并將該F值作為NetRate算法進行影響關系推斷的準確性比較時的最終結果。此外，由于LIFT算法只能推斷影響關系而不能推斷感染傳播概率，故該算法參與影響關系推斷的準確性比較，但不參與感染傳播概率推斷的準確性比較。此外，需要指出的是LIFT算法僅推斷節點之間的影響關系而不推斷感染傳播概率。因此為公平比較，也報告了FINITI算法中用于推斷影響關系（即算法1中1至14行）的運行時間，記為FINITI（for edges），用于與LIFT算法的運行時間進行對比。

5.2 傳播網絡節點數量的影響

傳播網絡的節點數量是指在傳播網絡中所包含的可供信息傳播的節點數量，通常用來表示傳播網絡的大小。使用LFR1～5這5個平均度相同但節點數量不一的傳播網絡來研究傳播網絡節點數量對實際結果的影響，并采用150次傳播過程的節點感染狀態觀測數據（β=150）。圖1比較了各對比算法的影響關系推斷結果的F值。可見，隨著網絡規模擴大，各算法的F值大體呈下降趨勢，但FINITI算法的F值無論在規模較小的數據集上還是在規模較大的數據集上均有明顯優勢。圖2體現了NetRate算法和FINITI算法的感染傳播概率推斷結果均方誤差（MSE）的對比，隨著網絡規模的擴大，兩算法的均方誤差顯著下降，但FINITI算法的均方誤差明顯更低。圖3為算法運行時間對比。由對比結果可見：在僅推斷影響關系時，FINITI（for edges）的運行時間低于LIFT算法；在同時推斷影響關系和感染傳播概率時，相比于NetRate算法，FINITI算法的運行時間明顯較低，具有數量級上的優勢。因此，提出的FINITI算法在推斷影響關系和感染傳播概率時體現出更好的時間效率。

Fig.1 Fvalue varies with number of nodes圖1 傳播網絡節點數量對F值的影響

Fig.2 MSEvaries with number of nodes圖2 傳播網絡節點數量對均方誤差的影響

Fig.3 Runtime varies with number of nodes圖3 傳播網絡節點數量對運行時間的影響

5.3 傳播網絡邊密度的影響

傳播網絡邊密度影響需推斷的影響關系和感染傳播概率的數量。平均度（即邊總數/節點總數）常用來表示邊的密度。本實驗采用LFR6～10這5個節點數量相同但平均度不同的網絡，并用150次傳播過程的節點感染狀態觀測數據（β=150）。圖4顯示，FINITI的F值明顯較高；FINITI和LIFT的F值隨平均度的增加有所下降。NetRate在平均度由2升至5時有增加是由于其在低平均度上求準率過低，致其F值較小。平均度達到5后，NetRate的F值也隨平均度的上升而減小。由圖5可見，FINITI有明顯更低的均方誤差；各算法的均方誤差隨平均度增加有所上升。由圖6可見，FINITI（for edges）和完整的FINITI算法在運行時間上有優勢。

Fig.4 Fvalue varies with average degree圖4 傳播網絡平均度對F值的影響

Fig.5 MSEvaries with average degree圖5 傳播網絡平均度對均方誤差的影響

5.4 歷史傳播過程數量的影響

Fig.6 Runtime varies with average degree圖6 傳播網絡平均度對運行時間的影響

傳播網絡推斷是根據在多次傳播過程中節點的感染狀態來進行的。通常，所用傳播過程數量越多，可用信息就越多，推斷結果也越趨于準確。本實驗采用真實傳播網絡DUNF，將模擬發生的傳播過程數量β從50變化至250。圖7和圖8分別報告了各算法的影響關系推斷結果的F值和感染傳播概率推斷結果均方誤差的對比。可見，隨著使用的傳播過程數量上升，各算法都有F值提升和均方誤差降低，FINITI算法的F值提升和均方誤差降低的幅度最大。由圖9可見，FINITI（for edges）和完整的FINITI算法所需運行時間也相對更短。

Fig.7 Fvalue varies with number of infections圖7 傳播過程數量對F值的影響

Fig.8 MSEvaries with number of infections圖8 傳播過程數量對均方誤差的影響

Fig.9 Runtime varies with number of infections圖9 傳播過程數量對運行時間的影響

5.5 初始感染節點比例的影響

初始節點感染比例可能影響各傳播過程中的最終被感染的節點的總數量（通常，初始感染節點比例越大，最終被感染節點總數量越多)。為研究初始感染節點比例對算法的影響，使用真實傳播網絡DUNF，選用5種不同的初始感染概率，分別為5%、10%、15%、20%和25%（模擬發生的傳播過程數量皆為150次）。圖10和圖11分別報告了各算法的影響關系推斷結果的F值和感染傳播概率推斷結果均方誤差的對比。由圖可見，隨初始感染節點比例的上升，特別是感染比例超過0.10之后，各算法的F值有一定下降趨勢，同時，其均方誤差呈一定上升趨勢。這是因為，當初始感染節點比例較高時，最終感染節點比例通常會上升；且由于傳播網絡大小有限，傳播網絡中多數節點可能會在較少的間隔內被感染，使得對于任意第?次傳播過程中點vi∈V的潛在父節點多集中于，從而使算法要推斷還原的影響關系數量過多，還原準確性有所下降。然而，本文的FINITI算法在這種情況下仍可保持較高的F值和較低的均方誤差。由圖12可見，FINITI（for edges）和完整的FINITI算法在運行時間上有優勢。

Fig.10 Fvalue varies with proportion of seeds圖10 初始感染節點比例對F值的影響

Fig.11 MSEvaries with proportion of seeds圖11 初始感染節點比例對均方誤差的影響

Fig.12 Runtime varies with proportion of seeds圖12 初始感染節點比例對運行時間的影響

6 結束語

本文以準確、高效且無需感染時間信息的傳播網絡推斷方法為目標，研究了如何僅僅利用多次傳播過程結束時觀測得到各節點的感染狀態來推斷傳播網絡中節點之間的影響關系和感染傳播概率。為此，本文方法首先利用節點感染狀態之間的互信息來量化它們之間的相互關聯，從而找出可能的節點之間影響關系。然后，構建以感染傳播概率為變量的節點感染狀態觀測數據的對數似然函數，并采用期望最大化的方法最大化該對數似然函數并求解感染傳播概率。實驗結果表明，與現有方法相比，本文方法有效地提高了傳播網絡推斷的準確性，并且大幅地縮短了算法運行所需要的時間。