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

1.武漢大學(xué) 計算機學(xué)院，武漢 430072

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

3.浙江大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，杭州 310027

1 引言

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

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

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

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

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

本文的組織結(jié)構(gòu)如下：第2章介紹現(xiàn)有相關(guān)工作；第3章給出本文研究問題的形式化描述；第4章詳細(xì)介紹本文所提出的FINITI算法；第5章報告實驗結(jié)果與分析；第6章總結(jié)全文。

2 相關(guān)工作

現(xiàn)有的傳播網(wǎng)絡(luò)推斷方法可以被劃分為兩大類：（1）基于感染時間信息的推斷方法；（2）不依賴感染時間信息的推斷方法。

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

現(xiàn)有的絕大多數(shù)傳播網(wǎng)絡(luò)推斷方法需要使用傳播網(wǎng)絡(luò)中各節(jié)點確切的感染時間作為分析推斷的依據(jù)。根據(jù)所采用的技術(shù)原理不同，這些方法可以分為基于凸優(yōu)化的方法、基于目標(biāo)函數(shù)子模性質(zhì)（submodularity）的方法、基于嵌入空間的方法。

2.1.1 基于凸優(yōu)化的方法

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

2.1.2 基于目標(biāo)函數(shù)子模性質(zhì)的方法

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

2.1.3 基于嵌入空間的方法

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

以上三類傳播網(wǎng)絡(luò)推斷方法皆需完整和準(zhǔn)確的感染時間信息。已有研究證明當(dāng)節(jié)點感染狀態(tài)觀測數(shù)據(jù)量足夠大且對應(yīng)節(jié)點感染時間信息完整、準(zhǔn)確時，目標(biāo)傳播網(wǎng)絡(luò)可以通過一些簡單的圖重構(gòu)方法推斷出來[19]。但是，即使節(jié)點感染時間信息可以被記錄，有時也會出現(xiàn)部分時間信息不夠準(zhǔn)確或者有所缺失的情況。為此，有一部分研究工作提出了針對此類情況傳播網(wǎng)絡(luò)推斷方法[20]。這些方法可視為對以上三類傳播網(wǎng)絡(luò)推斷方法的補充，但仍然屬于基于感染時間信息的傳播網(wǎng)絡(luò)推斷方法。

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

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

2.2.1 基于路徑跟蹤的方法

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

2.2.2 基于提升效果的方法

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

3 問題描述

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

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

4 FINITI算法

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

4.1 節(jié)點間影響關(guān)系推斷

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

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

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

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

根據(jù)以上閾值τ，可找出對各節(jié)點vi∈V可能具有影響關(guān)系的潛在父節(jié)點集合Fi：

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

4.2 感染傳播概率推斷

推斷感染傳播概率的關(guān)鍵是如何匹配感染傳播概率和節(jié)點感染狀態(tài)數(shù)據(jù)S。為此，提出構(gòu)建一個以感染傳播概率為變量的節(jié)點感染狀態(tài)數(shù)據(jù)的對數(shù)似然函數(shù)，從而找出一種最有可能產(chǎn)生β感染狀態(tài)數(shù)據(jù)S的節(jié)點間感染傳播概率方案。而要考察節(jié)點感染狀態(tài)數(shù)據(jù)的似然度（likelihood）需要考慮以下三種情況。

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

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

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

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

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

根據(jù)以上三種情況，可以構(gòu)建第?次傳播過程中節(jié)點感染狀態(tài)數(shù)據(jù)S?的似然度（likelihood）函數(shù)L(S?)如下：

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

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

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

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

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

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

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

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

則有：

首先，對于

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

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

同理可對

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

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

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

4.3 算法步驟及復(fù)雜度分析

4.3.1 算法步驟

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

算法1FINITI算法

輸入：各個節(jié)點的感染狀態(tài)數(shù)據(jù)S，閾值err。

輸出：傳播網(wǎng)絡(luò)中各節(jié)點vi∈V的父節(jié)點集合Fi及對應(yīng)的各感染傳播概率p(vj,vi)(vj∈Fi)。

4.3.2 復(fù)雜度分析

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

5 實驗結(jié)果與分析

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

5.1 實驗設(shè)置

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

Table 1 LFR networks表1 LFR網(wǎng)絡(luò)

在這些人工合成和真實網(wǎng)絡(luò)結(jié)構(gòu)上，設(shè)置網(wǎng)絡(luò)中邊的傳播概率服從均值為0.3，方差為0.05的高斯分布，使得95%以上的概率值集中在0.2至0.4的范圍內(nèi)。根據(jù)獨立級聯(lián)模型，模擬了β次爆發(fā)無時間信息結(jié)果，用于重構(gòu)這些網(wǎng)絡(luò)。

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

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

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

5.2 傳播網(wǎng)絡(luò)節(jié)點數(shù)量的影響

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

Fig.1 Fvalue varies with number of nodes圖1 傳播網(wǎng)絡(luò)節(jié)點數(shù)量對F值的影響

Fig.2 MSEvaries with number of nodes圖2 傳播網(wǎng)絡(luò)節(jié)點數(shù)量對均方誤差的影響

Fig.3 Runtime varies with number of nodes圖3 傳播網(wǎng)絡(luò)節(jié)點數(shù)量對運行時間的影響

5.3 傳播網(wǎng)絡(luò)邊密度的影響

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

Fig.4 Fvalue varies with average degree圖4 傳播網(wǎng)絡(luò)平均度對F值的影響

Fig.5 MSEvaries with average degree圖5 傳播網(wǎng)絡(luò)平均度對均方誤差的影響

5.4 歷史傳播過程數(shù)量的影響

Fig.6 Runtime varies with average degree圖6 傳播網(wǎng)絡(luò)平均度對運行時間的影響

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

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

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

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

5.5 初始感染節(jié)點比例的影響

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

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

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

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

6 結(jié)束語

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