李江 劉影2) 王偉 周濤

1) (西南石油大學(xué)計(jì)算機(jī)科學(xué)學(xué)院,成都 610500)

2) (弗里堡大學(xué)物理系,弗里堡 1700)

3) (重慶醫(yī)科大學(xué)公共衛(wèi)生學(xué)院,重慶 400016)

4) (電子科技大學(xué)大數(shù)據(jù)研究中心,成都 611731)

識(shí)別網(wǎng)絡(luò)傳播中最有影響力的節(jié)點(diǎn)是控制傳播速度和范圍的重要步驟,有助于加速有益信息擴(kuò)散,抑制流行病、謠言和虛假信息的傳播等.已有研究主要基于描述點(diǎn)對交互的低階復(fù)雜網(wǎng)絡(luò).然而,現(xiàn)實(shí)中個(gè)體間的交互不僅發(fā)生在點(diǎn)對之間,也發(fā)生在3 個(gè)及以上節(jié)點(diǎn)形成的群體中.群體交互可利用高階網(wǎng)絡(luò)來刻畫,如單純復(fù)形與超圖.本文研究單純復(fù)形上最有影響力的傳播者識(shí)別方法.首先,提出單純復(fù)形上易感-感染-恢復(fù)(SIR)微觀馬爾可夫鏈方程組,定量刻畫單純復(fù)形上的疾病傳播動(dòng)力學(xué).接下來利用微觀馬爾可夫鏈方程組計(jì)算傳播動(dòng)力學(xué)中節(jié)點(diǎn)被感染的概率.基于網(wǎng)絡(luò)結(jié)構(gòu)與傳播過程,定義節(jié)點(diǎn)的傳播中心性,用于排序節(jié)點(diǎn)傳播影響力.在兩類合成單純復(fù)形與4 個(gè)真實(shí)單純復(fù)形上的仿真結(jié)果表明,相比于現(xiàn)有高階網(wǎng)絡(luò)中心性和復(fù)雜網(wǎng)絡(luò)中最優(yōu)的中心性指標(biāo),本文提出的傳播中心性能更準(zhǔn)確地識(shí)別高階網(wǎng)絡(luò)中最有影響力的傳播者.

1 引言

現(xiàn)實(shí)世界中,許多具有擴(kuò)散效應(yīng)但僅由局部相互作用驅(qū)動(dòng)的動(dòng)力學(xué)過程可以用復(fù)雜網(wǎng)絡(luò)上的傳播來描述,如社交網(wǎng)絡(luò)上的流行病與謠言傳播[1,2]、電力網(wǎng)絡(luò)上電站的級(jí)聯(lián)失效[3]、交通網(wǎng)絡(luò)上的道路阻塞[4]、計(jì)算機(jī)網(wǎng)絡(luò)上的病毒傳播[5]等.失控的傳播可能對社會(huì)經(jīng)濟(jì)及人們生活造成大范圍的負(fù)面影響,如COVID-19 大流行影響經(jīng)濟(jì)發(fā)展[6],謠言傳播引起民眾恐慌[7],電力網(wǎng)絡(luò)中部分設(shè)備故障導(dǎo)致電網(wǎng)癱瘓[8].由于網(wǎng)絡(luò)結(jié)構(gòu)的異質(zhì)性,網(wǎng)絡(luò)中節(jié)點(diǎn)的傳播影響力具有顯著的差異[9].如在Twitter與Facebook 平臺(tái)僅有少量賬戶的信息被廣泛分享[10],COVID-19 中10%最具傳染性的宿主導(dǎo)致近80%的感染[11].網(wǎng)絡(luò)傳播中影響力最大的節(jié)點(diǎn)被稱為最有影響力的傳播者.識(shí)別最有影響力的傳播者是快速、有效地控制傳播過程的關(guān)鍵步驟.節(jié)點(diǎn)中心性利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)度量節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性.如基于鄰居數(shù)目的度中心性[12]、H-index 中心性[13]、k 殼中心性[14]、集體影響中心性[15]等,基于路徑的接近中心性[16]、介數(shù)中心性[17]、子圖中心性[18]以及基于特定動(dòng)力學(xué)過程迭代穩(wěn)態(tài)的指標(biāo),如特征向量中心性[19]、PageRank[20]、非回溯中心性[21]等.隨后,大量基于中心性的方法被提出,識(shí)別網(wǎng)絡(luò)中最有影響力的傳播者的算法性能不斷提升,并從單層網(wǎng)絡(luò)推廣到多層網(wǎng)絡(luò)[22–28].

已有識(shí)別最有影響力傳播者的研究主要針對描述節(jié)點(diǎn)間成對關(guān)系的簡單網(wǎng)絡(luò).簡單網(wǎng)絡(luò)用節(jié)點(diǎn)表示個(gè)體,邊表示兩個(gè)節(jié)點(diǎn)間的交互.然而現(xiàn)實(shí)中許多系統(tǒng)存在超越點(diǎn)對的成組交互,例如學(xué)術(shù)論文通常由團(tuán)隊(duì)共同完成[29],謠言與思想的傳播在小范圍群體中被加強(qiáng)[30].由3 個(gè)及以上個(gè)體組成的群體交互被定義為高階交互,單純復(fù)形和超圖是兩種描述高階交互的數(shù)學(xué)工具[31].單純復(fù)形是由一系列單純形組成的集合.一個(gè)k階單純形由k+1個(gè)節(jié)點(diǎn)組成,且這些節(jié)點(diǎn)的任意節(jié)點(diǎn)子集也構(gòu)成單純形.如在科學(xué)家合作網(wǎng)中,若4 個(gè)作者組成一個(gè)3 階單純形,自然其中任意2 個(gè)作者,任意3 個(gè)作者也具有合作關(guān)系.在超圖中,一條超邊可包含任意數(shù)量的節(jié)點(diǎn),表示這些節(jié)點(diǎn)相互影響.相比于單純復(fù)形,超圖不要求高階交互的所有子交互必須出現(xiàn)在超圖中.高階網(wǎng)絡(luò)上的傳播動(dòng)力學(xué)受到了廣泛的關(guān)注.在高階網(wǎng)絡(luò)上的社會(huì)傳播中,研究發(fā)現(xiàn)高階結(jié)構(gòu)會(huì)導(dǎo)致不連續(xù)相變與雙穩(wěn)態(tài)區(qū)域,雙穩(wěn)態(tài)區(qū)域中穩(wěn)態(tài)規(guī)模依賴初始感染種子數(shù)目[30,32].在社會(huì)傳播模型的基礎(chǔ)上,研究人員提出了高階網(wǎng)絡(luò)上的多動(dòng)力學(xué)耦合傳播模型,例如高階網(wǎng)絡(luò)上的競爭傳播與意識(shí)疾病耦合傳播等.相比于簡單圖上的競爭傳播[33],引入高階交互使兩種流行病可共存[34].意識(shí)疾病耦合傳播中,社交網(wǎng)絡(luò)中的高階交互可緩解低流行病傳播率下信息傳播不足的問題,有助于抑制流行病傳播[35].

簡單網(wǎng)絡(luò)與高階網(wǎng)絡(luò)間的傳播現(xiàn)象具有明顯差異,因此識(shí)別高階網(wǎng)絡(luò)上最有影響力傳播者的研究值得關(guān)注.度中心性、接近中心性、介數(shù)中心性和特征向量中心性等概念被擴(kuò)展至單純復(fù)形,用于識(shí)別核心蛋白[36].類似地,特征向量中心性被推廣并應(yīng)用于識(shí)別超圖中的重要節(jié)點(diǎn)與重要超邊,其主要思想為節(jié)點(diǎn)的重要性依賴于節(jié)點(diǎn)參與超邊的重要性,而超邊的重要性依賴超邊所包含節(jié)點(diǎn)的重要性[37].還有研究人員提出向量中心性以描述節(jié)點(diǎn)在不同尺寸超邊中的重要性[38].現(xiàn)有高階網(wǎng)絡(luò)中重要節(jié)點(diǎn)識(shí)別方法主要基于網(wǎng)絡(luò)結(jié)構(gòu),鮮有同時(shí)考慮網(wǎng)絡(luò)結(jié)構(gòu)與傳播過程.

已有研究表明節(jié)點(diǎn)的傳播影響力由網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與傳播過程共同決定.相比于僅使用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的方法,同時(shí)考慮傳播過程與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的方法能更準(zhǔn)確地識(shí)別網(wǎng)絡(luò)傳播中最有影響力的傳播者[39,40].本文基于網(wǎng)絡(luò)結(jié)構(gòu)與傳播過程,提出傳播中心性.首先提出單純復(fù)形上易感-感染-恢復(fù)(susceptible-infected-recovered,SIR)微觀馬爾可夫鏈方程組用于描述單純復(fù)形上的SIR 傳播動(dòng)力學(xué);接下來計(jì)算微觀馬爾可夫鏈方程組收斂時(shí)節(jié)點(diǎn)被感染的概率.節(jié)點(diǎn)被感染的概率由網(wǎng)絡(luò)結(jié)構(gòu)與傳播過程共同決定,將其定義為 “傳播中心性” (spreading centrality,SC),用于排序節(jié)點(diǎn)的傳播影響力.在兩類合成網(wǎng)絡(luò)與4 個(gè)真實(shí)網(wǎng)絡(luò)上的大規(guī)模仿真實(shí)驗(yàn)表明,傳播中心性與節(jié)點(diǎn)真實(shí)傳播影響力高度正相關(guān).相比于高階網(wǎng)絡(luò)的度中心性、特征向量中心性以及簡單網(wǎng)絡(luò)上最優(yōu)的集體影響中心性、非回溯中心性等基準(zhǔn)中心性,本文提出的傳播中心性能更為準(zhǔn)確地識(shí)別高階SIR 傳播中最有影響力的節(jié)點(diǎn),排序準(zhǔn)確性更高.

2 單純復(fù)形上的傳播模型

本節(jié)首先介紹單純復(fù)形的定義,再說明單純復(fù)形上的易感-感染-恢復(fù)傳播模型.單純復(fù)形定義為M=(V,C),其中,V表示節(jié)點(diǎn)集合,C表示單純形集合[30].k階單純形σ ?C表示k+1 個(gè)節(jié)點(diǎn){v0,v1,v2,···,vk}組成的高階交互.單純復(fù)形中,0 階單純形表示單個(gè)節(jié)點(diǎn),1 階單純形表示邊,2 階單純形表示“滿”三角面等.單純復(fù)形滿足以下條件,若單純形ω ?C,其所有子單純形v ?ω必須被包含在C中.如2 階單純形w={v0,v1,v2}?C,則{v0},{v1},{v2},{v0,v1},{v0,v2}和{v1,v2}?C.為了簡便,使用的單純復(fù)形中僅包含0 階單純形(節(jié)點(diǎn)),1 階單純形(邊)和2 階單純形(高階交互).

在單純復(fù)形上的SIR 傳播[41]中,個(gè)體可有3 種狀態(tài): 易感態(tài)(susceptible,S),感染態(tài)(infected,I),或恢復(fù)態(tài)(recovered,R).在每個(gè)時(shí)間步,I 態(tài)個(gè)體以一定速率將S 態(tài)鄰居感染,并以一定速率自發(fā)恢復(fù)為R 態(tài).單純復(fù)形上,沿著1 階單純形(連邊)和2 階單純形(三角面)都將發(fā)生感染事件.本模型的傳播參數(shù)為(β1,β2,μ),其中β1表示1 階單純形感染S 態(tài)成員的速率,β2表示2 階單純形感染S 態(tài)成員的速率,μ表示I 態(tài)個(gè)體的恢復(fù)速率.圖1展示單純復(fù)形上個(gè)體感染與恢復(fù)的過程,邊表示1 階單純形,“滿”三角面表示2 階單純形.圖1(a)—(j)中橙色邊表示S 態(tài)個(gè)體通過1 階單純形以速率β1被感染.圖1(h)中橙色“滿”三角面表示S 態(tài)個(gè)體通過2 階單純形以速率β2被感染.圖1(h)中,S 態(tài)個(gè)體不僅通過1 階單純形被感染,同時(shí)也通過2 階單純形被感染.注意,當(dāng)且僅當(dāng)2 階單純形中的兩個(gè)節(jié)點(diǎn)同時(shí)處于感染態(tài)時(shí),2 階單純形才能感染其第3 個(gè)成員.圖1(j)中,3 個(gè)節(jié)點(diǎn)雖形成“滿”三角面,但其中只有1 個(gè)節(jié)點(diǎn)感染,流行病無法通過2 階單純形進(jìn)行傳播.

3 傳播中心性

本節(jié)提出單純復(fù)形上的微觀馬爾可夫鏈方程組,通過微觀馬爾可夫鏈方程組計(jì)算動(dòng)力學(xué)穩(wěn)態(tài)時(shí)各節(jié)點(diǎn)被感染的概率,并將其定義為節(jié)點(diǎn)的傳播中心性.定義為t時(shí)刻節(jié)點(diǎn)i處于X狀態(tài)的概率,X ∈{S,I,R},如表示t時(shí)刻節(jié)點(diǎn)i處于S 態(tài)的概率.定義qi(t) 表示t時(shí)刻節(jié)點(diǎn)i沒有被1 階單純形感染的概率,有

其中,Γi表示包含節(jié)點(diǎn)i的1 階單純形集合.定義表示t時(shí)刻節(jié)點(diǎn)i沒有被2 階單純形感染的概率,有

其中,?i表示包含節(jié)點(diǎn)i的2 階單純形集合.節(jié)點(diǎn)i在t時(shí)刻未被感染的概率qi(t) 可定義為

節(jié)點(diǎn)i處于不同狀態(tài)概率隨時(shí)間t的演化方程組可寫為

(4)式表示節(jié)點(diǎn)i在t時(shí)刻處于S 態(tài)且未被感染,在t+1 時(shí)刻仍處于S 態(tài)的概率.(5)式右邊第1 項(xiàng)表示節(jié)點(diǎn)i在t時(shí)刻處于S 態(tài)且被感染,在t+1 時(shí)刻處于I 態(tài)的概率.右邊第2 項(xiàng)表示節(jié)點(diǎn)i在t時(shí)刻處于I 態(tài)且未恢復(fù),在t+1 時(shí)刻仍處于I 態(tài)的概率.(6)式由節(jié)點(diǎn)處于S態(tài),I 態(tài)與R 態(tài)的概率之和為1 的性質(zhì)所得.

為了求解單個(gè)節(jié)點(diǎn)作為初始傳播源時(shí),系統(tǒng)達(dá)到穩(wěn)態(tài)后各節(jié)點(diǎn)被感染的概率,初始時(shí)設(shè)置=1-1/N,=1/N,=0,N為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目.迭代(1)—(6)式至收斂,獲得各節(jié)點(diǎn)被感染概率.將其定義為傳播中心性(spreading centrality,SC).流行病通過接觸傳播,疾病將優(yōu)先到達(dá)擁有著更多接觸的個(gè)體,即表現(xiàn)出更高的被感染概率.一旦這些個(gè)體被感染,他們更有可能將流行病傳播出去,造成大規(guī)模感染.傳播中心性屬于迭代中心性,但與特征向量中心性等不考慮傳播過程的迭代中心性不同,傳播中心性加入了傳播過程,迭代過程與傳播過程一致.

4 仿真實(shí)驗(yàn)方法

為了驗(yàn)證傳播中心性識(shí)別最有影響力傳播者的準(zhǔn)確性,我們在兩類合成網(wǎng)絡(luò)(勻質(zhì)度分布網(wǎng)絡(luò)與異質(zhì)度分布網(wǎng)絡(luò))與4 個(gè)真實(shí)網(wǎng)絡(luò)上進(jìn)行大量仿真實(shí)驗(yàn).本節(jié)首先介紹合成網(wǎng)絡(luò)與4 個(gè)真實(shí)網(wǎng)絡(luò)的生成方法,然后說明4 個(gè)用于比較的基準(zhǔn)中心性及評價(jià)準(zhǔn)確性的指標(biāo).

4.1 網(wǎng)絡(luò)構(gòu)建方法

在實(shí)驗(yàn)中使用了隨機(jī)單純復(fù)形與無標(biāo)度單純復(fù)形兩種合成網(wǎng)絡(luò).隨機(jī)單純復(fù)形模型(random simplicial complex,RSC)用于生成勻質(zhì)度分布的單純復(fù)形[42].生成步驟如下: 以概率p1在任意兩節(jié)點(diǎn)間生成邊,再以概率p2在任意3 個(gè)節(jié)點(diǎn)間生成2 階單純形.p1,p2與節(jié)點(diǎn)平均關(guān)聯(lián)的1 階單純形數(shù)目〈k1〉,節(jié)點(diǎn)平均關(guān)聯(lián)的2 階單純形數(shù)目〈k2〉 之間關(guān)系如下:

無標(biāo)度單純復(fù)形模型(scale-free simplicial complex,SFSC)用于生成異質(zhì)度分布網(wǎng)絡(luò)[42].生成步驟如下: 以Barabási-Albert 模型生成無標(biāo)度網(wǎng)絡(luò),即每個(gè)新加節(jié)點(diǎn)按度偏好選擇m個(gè)舊節(jié)點(diǎn)生成連邊.然后以概率p2在任意3 個(gè)節(jié)點(diǎn)間生成2 階單純形.〈k2〉可由(8)式計(jì)算,〈k1〉 表示為

采用4 個(gè)面對面接觸數(shù)據(jù)集構(gòu)建真實(shí)單純復(fù)形[43–46].這些數(shù)據(jù)集從不同的人群接觸場所中得到,包括工作場所(InVS15)、醫(yī)院(LH10)、會(huì)議(SFHH)與高中(Thiers13).每個(gè)數(shù)據(jù)集中,記錄了以20 s 為時(shí)間間隔的個(gè)體間面對面的交互.我們以5 min 作為時(shí)間窗口聚合數(shù)據(jù).在一個(gè)時(shí)間窗口中,若兩個(gè)節(jié)點(diǎn)有面對面接觸則生成一條邊,即1 階單純形.3 個(gè)節(jié)點(diǎn)兩兩接觸則生成2 階單純形.統(tǒng)計(jì)邊與2 階單純形在所有時(shí)間窗口中出現(xiàn)的總次數(shù),最后保留50%出現(xiàn)次數(shù)最多的1 階單純形與20%出現(xiàn)次數(shù)最多的2 階單純形用于構(gòu)建真實(shí)單純復(fù)形.表1 展示了使用上述方法構(gòu)建的合成單純復(fù)形與真實(shí)單純復(fù)形的簡單統(tǒng)計(jì)特征,其中N為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目,〈k1〉 為節(jié)點(diǎn)平均關(guān)聯(lián)的1 階單純形數(shù)目,〈k2〉 為節(jié)點(diǎn)平均關(guān)聯(lián)的2 階單純形數(shù)目,是流行病爆發(fā)時(shí),1 階單純形傳播速率的閾值,通過計(jì)算機(jī)模擬所得.在后文實(shí)驗(yàn)中,將1 階單純形傳播速率設(shè)置為該模擬閾值的1—2倍,以控制傳播規(guī)模.

表1 合成與真實(shí)單純復(fù)形屬性Table 1.Properties of the synthetic and real simplicial complexes.

4.2 基準(zhǔn)中心性

為了與本文提出的傳播中心性比較,我們選擇高階網(wǎng)絡(luò)的度中心性[31]與特征向量中心性[37],簡單網(wǎng)絡(luò)上當(dāng)前最優(yōu)的集體影響中心性[15]與非回溯中心性[21]作為比較的基準(zhǔn)中心性.

高階網(wǎng)絡(luò)上的度中心性定義為節(jié)點(diǎn)直接鄰居數(shù)目或節(jié)點(diǎn)參與交互數(shù)目.本文采用節(jié)點(diǎn)交互數(shù)目的定義方式,則節(jié)點(diǎn)度中心性可寫為

其中,ki表示節(jié)點(diǎn)i參與1 階單純形的數(shù)目,表示節(jié)點(diǎn)i參與2 階單純形的數(shù)目.

超圖中節(jié)點(diǎn)與超邊的特征向量中心性(EVH)認(rèn)為節(jié)點(diǎn)重要性依賴于節(jié)點(diǎn)所在的超邊,超邊重要性依賴于超邊所包含的節(jié)點(diǎn),其數(shù)學(xué)定義為

式中,λ 和μ是比例常數(shù).x,y是向量,xi表示節(jié)點(diǎn)i的特征向量中心性值,ye表示超邊e的特征向量中心性值.B是超圖的關(guān)聯(lián)矩陣,超邊e包含節(jié)點(diǎn)i,則Bie=1,反之Bie=0 .g,f,ψ,φ 是4 個(gè)映射函數(shù),用于實(shí)現(xiàn)不同的依賴關(guān)系.本文中設(shè)定:

集體影響中心性(collective influence,CI)與非回溯中心性(nonbacktracking,NB)是簡單網(wǎng)絡(luò)上的最優(yōu)中心性算法.集體影響中心性基于最優(yōu)滲流,推導(dǎo)得出節(jié)點(diǎn)i的CI 中心性定義為

式中，ki表示節(jié)點(diǎn)i的度,?Ball(i,l) 表示與節(jié)點(diǎn)i距離為l的節(jié)點(diǎn)集合.本文計(jì)算集體影響中心性時(shí)設(shè)置l=2 .

非回溯中心性與標(biāo)準(zhǔn)特征向量中心性類似,但通過非回溯矩陣避免標(biāo)準(zhǔn)特征向量中心性的局部化問題.節(jié)點(diǎn)j的非回溯中心性定義為

其中,A表示簡單圖的鄰接矩陣,vi→j是簡單圖的非回溯矩陣的主特征向量中邊ei→j對應(yīng)的分量.將簡單圖上的集體影響中心性與非回溯中心性算法用于單純復(fù)形時(shí),我們不考慮單純復(fù)形中的高階交互(即“滿”三角面)的影響,即僅考慮網(wǎng)絡(luò)中的節(jié)點(diǎn)與連邊.

4.3 評價(jià)指標(biāo)

為了評估不同中心性識(shí)別最有影響力傳播者的準(zhǔn)確性,我們使用不準(zhǔn)確函數(shù)[14]、肯德爾相關(guān)系數(shù)與Top-K準(zhǔn)確率作為評價(jià)指標(biāo).不準(zhǔn)確函數(shù)ξ(p)度量中心性識(shí)別最有影響力傳播者的不準(zhǔn)確性,定義為

其中p是計(jì)算節(jié)點(diǎn)的比例(0 ≤p≤1).M(p) 表示規(guī)模為N的網(wǎng)絡(luò)中,中心性排序在前的pN個(gè)節(jié)點(diǎn)的平均傳播影響力,Meff(p) 表示真實(shí)傳播影響力排序在前的pN個(gè)節(jié)點(diǎn)的平均傳播影響力.ξ(p) 量化了實(shí)際最有傳播影響力的傳播者與中心性最高的傳播者間平均傳播影響力的接近程度.ξ(p) 越小,中心性在識(shí)別最有影響力的傳播者時(shí)越準(zhǔn)確.

肯德爾相關(guān)系數(shù)用于度量兩個(gè)排序序列的相關(guān)性,定義為

Top-K準(zhǔn)確率用于度量中心性對最有傳播影響力的前K個(gè)節(jié)點(diǎn)的識(shí)別準(zhǔn)確性,定義為

其中,SK表示中心性值在前K的節(jié)點(diǎn)集合,表示真實(shí)傳播影響力在前K的節(jié)點(diǎn)集合,|SK| 表示集合SK中的元素?cái)?shù)目.Top-K準(zhǔn)確率越高表示中心性識(shí)別最有傳播影響力的節(jié)點(diǎn)越準(zhǔn)確.

5 實(shí)驗(yàn)結(jié)果

我們在合成網(wǎng)絡(luò)與真實(shí)網(wǎng)絡(luò)上度量傳播中心性SC 排序節(jié)點(diǎn)影響力的性能.首先,分析了節(jié)點(diǎn)傳播中心性與傳播影響力的相關(guān)性,如圖2 所示.結(jié)果表明,節(jié)點(diǎn)傳播中心性與傳播影響力高度正相關(guān).當(dāng)β1=時(shí),RSC 網(wǎng)絡(luò)上節(jié)點(diǎn)傳播中心性與傳播影響力的皮爾遜相關(guān)系數(shù)為0.9691;當(dāng)β1=時(shí),皮爾遜相關(guān)系數(shù)分別為0.9887 與0.9910.其他網(wǎng)絡(luò)上,結(jié)果與RSC 網(wǎng)絡(luò)中類似.實(shí)驗(yàn)中,為了獲得單個(gè)節(jié)點(diǎn)的傳播影響力,對單純復(fù)形上的SIR 傳播模型進(jìn)行大規(guī)模的蒙特卡羅模擬.初始時(shí),將節(jié)點(diǎn)i設(shè)置為感染態(tài),其余節(jié)點(diǎn)設(shè)置為易感態(tài),統(tǒng)計(jì)傳播達(dá)到穩(wěn)態(tài)時(shí)網(wǎng)絡(luò)的感染規(guī)模,即恢復(fù)態(tài)占比.獨(dú)立重復(fù)上述模擬 103次,將感染規(guī)模的均值作為對節(jié)點(diǎn)i的真實(shí)傳播影響力Si的估計(jì).當(dāng)系統(tǒng)初始狀態(tài)確定時(shí),微觀馬爾可夫鏈方程組的收斂狀態(tài)是固定的,不具備隨機(jī)性.我們設(shè)置(t=0)=1-1/N,(t=0)=1/N,(t=0)=0,通過迭代微觀馬爾可夫鏈方程組計(jì)算傳播中心性.在實(shí)驗(yàn)中,固定恢復(fù)速率μ=1,通過改變傳播速率β1與β2設(shè)定不同的有效傳播速率.μ的取值僅影響傳播的時(shí)間演化尺度,不影響實(shí)驗(yàn)結(jié)果.

圖2 節(jié)點(diǎn)傳播中心性與傳播影響力的散點(diǎn)圖.SC與S 分別表示歸一化后的節(jié)點(diǎn)傳播中心性與傳播影響力(a) RSC;(b) SFSC;(c) InVS15;(d) LH10;(e) SFHH;(f) Thiers13Fig.2.Scatter plots of the spreaing centrality and spreaing influence of nodes.SC and S represent the normalized spreading centrality and spreading influence of nodes: (a) RSC;(b) SFSC;(c) InVS15;(d) LH10;(e) SFHH;(f) Thiers13.

為了考察提出的傳播中心性SC 排序節(jié)點(diǎn)傳播影響力的準(zhǔn)確性,采用不準(zhǔn)確函數(shù)作為評價(jià)指標(biāo).不準(zhǔn)確函數(shù)值越低,該中心性識(shí)別最有影響力的傳播者越準(zhǔn)確.如圖3 所示,傳播中心性能準(zhǔn)確有效地識(shí)別最有影響力的傳播者.在所有網(wǎng)絡(luò)上,傳播中心性的不準(zhǔn)確函數(shù)低于0.02,傳播中心性多數(shù)情況下優(yōu)于其他基準(zhǔn)中心性.在SFSC 與Thiers13網(wǎng)絡(luò)中,傳播中心性明顯優(yōu)于所有基準(zhǔn)中心性.在RSC 網(wǎng)絡(luò)上,傳播中心性略優(yōu)于集體影響中心性、特征向量中心性與非回溯中心性,明顯優(yōu)于度中心性.在InVS15 網(wǎng)絡(luò)中,當(dāng)0

圖3 各中心性的不準(zhǔn)確函數(shù)(a) RSC;(b) SFSC;(c) InVS15;(d) LH10;(e) SFHH;(f) Thiers13 Fig.3.Imprecisions of the centralities: (a) RSC;(b) SFSC;(c) InVS15;(d) LH10;(e) SFHH;(f) Thiers13.

為了考察傳播參數(shù)改變時(shí),提出的傳播中心性的性能,對比了不同1 階單純形傳播速率下各中心性與節(jié)點(diǎn)傳播影響力的相關(guān)性,如圖4 所示.結(jié)果表明,在所有網(wǎng)絡(luò)中,所提的傳播中心性與傳播影響力的肯德爾相關(guān)系數(shù)大于基準(zhǔn)中心性與傳播影響力的肯德爾相關(guān)系數(shù).合成網(wǎng)絡(luò)中傳播中心性的肯德爾相關(guān)系數(shù)隨1 階單純形傳播速率的增大而增大.在RSC 網(wǎng)絡(luò)中,傳播中心性在1 ≤α≤1.4時(shí)略優(yōu)于特征向量中心性、非回溯中心性和集體影響中心性,明顯優(yōu)于度中心性.當(dāng)1.4<α≤2 時(shí)略優(yōu)于集體影響中心性,明顯優(yōu)于其余中心性.SFSC網(wǎng)絡(luò)中,傳播中心性明顯優(yōu)于其他基準(zhǔn)中心性.真實(shí)網(wǎng)絡(luò)中結(jié)果與合成網(wǎng)絡(luò)結(jié)果類似.在InVS15 與Thiers13 網(wǎng)絡(luò)中,傳播中心性明顯優(yōu)于其他基準(zhǔn)中心性.在LH10 與SFHH 網(wǎng)絡(luò)中,傳播中心性略優(yōu)于非回溯中心性,明顯優(yōu)于集體影響中心性,特征向量中心性與度中心性等基準(zhǔn)中心性.其余傳播參數(shù)設(shè)置如下: 恢復(fù)速率μ=1,1 階單純形傳播速率β1=.2 階單純形傳播速率設(shè)定為β2=0.1 .實(shí)驗(yàn)中設(shè)置1 階單純形傳播速率β1∈.當(dāng)β1<時(shí),流行病不能爆發(fā),所有節(jié)點(diǎn)的傳播影響力接近于0;當(dāng)β1>時(shí),傳播速率過大,所有節(jié)點(diǎn)都會(huì)導(dǎo)致較高的流行病爆發(fā)規(guī)模.傳播速率過小或過大都無法充分地體現(xiàn)節(jié)點(diǎn)間傳播影響力的差異.基本再生數(shù)度量感染節(jié)點(diǎn)感染下一代節(jié)點(diǎn)的能力,是傳播中的一個(gè)重要參量.復(fù)雜網(wǎng)絡(luò)SIR 傳播模型基本再生數(shù)定義為R0=(k+s2/k)β/μ,其中β 是傳播速率,μ是恢復(fù)速率,k是平均度,s是度分布的標(biāo)準(zhǔn)差.實(shí)驗(yàn)中,設(shè)置1 階單純形傳播速率β1∈,此時(shí)各網(wǎng)絡(luò)的基本再生數(shù)取值范圍為: RSC [0.98,1.96];SFSC [1.06,2.12];InVS15[0.97,1.94];LH10 [0.97,1.94];SFHH [0.99,1.98];Thiers13 [1.05,2.10].由于流行病主要通過邊進(jìn)行傳播,高階作用僅起強(qiáng)化作用,我們計(jì)算R0時(shí)未考慮高階作用.

圖4 不同1 階單純形傳播速率 β1=下,節(jié)點(diǎn)各中心性與傳播影響力的肯德爾相關(guān)系數(shù)(a) RSC;(b) SFSC;(c) InVS15;(d) LH10;(e) SFHH;(f) Thiers13Fig.4.Kendall’s tau correlation of the centralities and the spreading influence of nodes under different 1-simplex spreading rates β1=: (a) RSC;(b) SFSC;(c) InVS15;(d) LH10;(e) SFHH;(f) Thiers13.

在高階網(wǎng)絡(luò)傳播中,2 階單純形傳播速率會(huì)影響節(jié)點(diǎn)的傳播影響力.我們改變2 階單純形傳播速率β2,考察中心性與節(jié)點(diǎn)傳播影響力的相關(guān)性.如圖5 所示,在合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)中,多數(shù)情況下傳播中心性SC 與節(jié)點(diǎn)傳播影響力的相關(guān)性最高.在合成網(wǎng)絡(luò)RSC 與SFSC中,傳播中心性的肯德爾相關(guān)系數(shù)基本不隨β2變化且優(yōu)于基準(zhǔn)中心性.在真實(shí)網(wǎng)絡(luò)InVS15,LH10 與SFHH中,傳播中心性的肯德爾相關(guān)系數(shù)隨β2的增大呈現(xiàn)下降趨勢.在Thiers13 中傳播中心性的肯德爾相關(guān)系數(shù)變化趨勢平坦.與基準(zhǔn)中心性相比,InVS15 與Thiers13網(wǎng)絡(luò)中傳播中心性完全優(yōu)于其他基準(zhǔn)中心性.在LH10 網(wǎng)絡(luò)中,當(dāng)0 ≤β2≤0.1時(shí),傳播中心性優(yōu)于所有基準(zhǔn)中心性,當(dāng)0.1<β2≤0.2 時(shí)傳播中心性略差于非回溯中心性但優(yōu)于其他基準(zhǔn)中心性.SFHH網(wǎng)絡(luò)結(jié)果與LH10 類似,當(dāng)0≤β2<0.15 時(shí)傳播中心性優(yōu)于所有基準(zhǔn)中心性,而當(dāng)0.15≤β2≤0.2 時(shí)傳播中心性略差于非回溯中心性但優(yōu)于其他基準(zhǔn)中心性.當(dāng)β2=0時(shí),2 階單純形不再傳播流行病,高階網(wǎng)絡(luò)上的傳播退回到普通網(wǎng)絡(luò)上的SIR傳播模型.此時(shí),節(jié)點(diǎn)的傳播中心性與傳播影響力間的肯德爾系數(shù)接近或高于0.9,明顯優(yōu)于普通網(wǎng)絡(luò)上性能最優(yōu)的集體影響中心性與非回溯中心性.隨著2 階單純形傳播速率β2增大,傳播中心性與傳播影響力間的相關(guān)性呈現(xiàn)出小幅降低的現(xiàn)象.當(dāng)傳播發(fā)生在2 階單純形上時(shí),節(jié)點(diǎn)感染與被感染過程是非對稱的.若2 階單純形中僅有一個(gè)節(jié)點(diǎn)處于感染態(tài),該單純形無法傳播流行病,即一個(gè)節(jié)點(diǎn)容易通過2 階單純形被感染不代表它容易通過2 階單純形傳播流行病.隨著2 階傳播速率β2增大,這種非對稱性帶來的負(fù)面效果將會(huì)升高,傳播中心性與傳播影響力間的相關(guān)性將小幅降低.在圖5 的實(shí)驗(yàn)中,其余傳播參數(shù)設(shè)置為:β1=,μ=1 .

圖5 不同2 階單純形傳播速率 β2下,節(jié)點(diǎn)各中心性與傳播影響力的肯德爾相關(guān)系數(shù)(a) RSC;(b) SFSC;(c) InVS15;(d) LH10;(e) SFHH;(f) Thiers13Fig.5.Kendall’s tau correlation of the centralities and the spreading influence of nodes under different 2-simplex spreading rates β2 : (a) RSC;(b) SFSC;(c) InVS15;(d) LH10;(e) SFHH;(f) Thiers13.

最后,通過Top-K準(zhǔn)確率表征各中心性對前K個(gè)最有傳播影響力節(jié)點(diǎn)的識(shí)別準(zhǔn)確率.表2 展示了各中心性的Top-10,Top-20 與Top-30 準(zhǔn)確率.綜合來講,傳播中心性多數(shù)情況下能較為準(zhǔn)確地識(shí)別前K個(gè)最有影響力的傳播者.當(dāng)K=10時(shí),在RSC,InVS15,SFHH 與Thiers13 網(wǎng)絡(luò)中,傳播中心性有著最高的Top-10 準(zhǔn)確率,即在識(shí)別前10 個(gè)影響力最大的節(jié)點(diǎn)時(shí),傳播中心性SC 準(zhǔn)確率最高.當(dāng)K=20時(shí),在除SFSC 網(wǎng)絡(luò)外的其他網(wǎng)絡(luò)中,傳播中心性有著最高的Top-20 識(shí)別準(zhǔn)確率.當(dāng)K=30時(shí),傳播中心性在SFSC,LH10 與Thiers13網(wǎng)絡(luò)中有著最高的Top-30 識(shí)別準(zhǔn)確率.Thiers13網(wǎng)絡(luò)中,傳播中心性有著最高的Top-K準(zhǔn)確率,且明顯高于所有基準(zhǔn)中心性的Top-K準(zhǔn)確率.傳播參數(shù)設(shè)置如下:β1=,β2=0.1,μ=1 .

表2 各中心性的Top-K 準(zhǔn)確率Table 2.Top-K accuracy of centralities.

6 結(jié)論

識(shí)別網(wǎng)絡(luò)傳播中最有影響力的傳播者是控制傳播過程的關(guān)鍵步驟之一.本文研究高階網(wǎng)絡(luò)上SIR 傳播過程中最有影響力傳播者的識(shí)別方法.我們提出單純復(fù)形上SIR 微觀馬爾可夫鏈方程組,用于描述SIR 傳播動(dòng)力學(xué)過程.利用微觀馬爾可夫鏈方程組,計(jì)算單源傳播時(shí)各節(jié)點(diǎn)被感染的概率,定義度量節(jié)點(diǎn)傳播影響力的指標(biāo),傳播中心性.大量仿真實(shí)驗(yàn)表明,傳播中心性與節(jié)點(diǎn)真實(shí)傳播影響力高度正相關(guān).相比于4 種基準(zhǔn)中心性,即高階網(wǎng)絡(luò)上的度中心性、特征向量中心性等僅考慮網(wǎng)絡(luò)結(jié)構(gòu)的中心性與復(fù)雜網(wǎng)絡(luò)上最優(yōu)的集體影響中心性、非回溯中心性,本文提出的傳播中心性在兩類合成網(wǎng)絡(luò)中識(shí)別傳播重要節(jié)點(diǎn)時(shí)比基準(zhǔn)中心性更準(zhǔn)確,在真實(shí)網(wǎng)絡(luò)中多數(shù)情況下優(yōu)于基準(zhǔn)中心性.傳播中心性方法可以擴(kuò)展到超圖上.對于超圖上的傳播,可以類似地寫出描述傳播動(dòng)力學(xué)的微觀馬爾可夫鏈方程組,再利用該方程組計(jì)算節(jié)點(diǎn)的傳播中心性.

傳播中心性具有一定局限性.通過節(jié)點(diǎn)被感染概率預(yù)測節(jié)點(diǎn)的真實(shí)傳播影響力時(shí),假設(shè)越容易被感染的個(gè)體越容易感染鄰居,即感染與被感染是對稱的.考慮感染與被感染的方向性,當(dāng)傳播發(fā)生在1 階單純形上時(shí),感染與被感染是對稱的;當(dāng)傳播發(fā)生在2 階單純形上時(shí),2 階單純形中單個(gè)感染態(tài)節(jié)點(diǎn)并不能通過該2 階單純形傳播流行病,感染與被感染是非對稱的.感染與被感染的非對稱性會(huì)降低傳播中心性的排序準(zhǔn)確性,考慮2 階單純形上的非對稱性可以進(jìn)一步提升傳播中心性的準(zhǔn)確性.當(dāng)感染與被感染的對稱性受到嚴(yán)重破壞時(shí),傳播中心性可能不再適用.例如傳播在有向網(wǎng)絡(luò)上發(fā)生時(shí),傳播中心性可能不再準(zhǔn)確.因此,未來需要進(jìn)一步探索如何在有向網(wǎng)絡(luò)上識(shí)別最有影響力的傳播者.