基于節(jié)點(diǎn)內(nèi)聯(lián)性的傳播網(wǎng)絡(luò)推斷模型研究

徐楠楠,胡晨光,于曉輝

?

基于節(jié)點(diǎn)內(nèi)聯(lián)性的傳播網(wǎng)絡(luò)推斷模型研究

徐楠楠1,胡晨光1,于曉輝2

1. 北京電子科技職業(yè)學(xué)院 信息中心, 北京 100176 2. 北京物資學(xué)院 物流學(xué)院, 北京 101149

為了有效克服傳播網(wǎng)絡(luò)節(jié)點(diǎn)推斷時(shí)，無法準(zhǔn)確獲得感染時(shí)間信息的問題，首先通過不同節(jié)點(diǎn)感染情況間信息直接量化節(jié)點(diǎn)間的內(nèi)聯(lián)性，由此確定所有可能存在的影響關(guān)系。其次，構(gòu)造出節(jié)點(diǎn)感染傳播概率的相關(guān)對(duì)數(shù)似然函數(shù)，通過期望最大化法進(jìn)行處理，同時(shí)計(jì)算感染傳播概率。結(jié)果表明，相較當(dāng)前算法而言，該算法優(yōu)勢較為明顯，一方面能實(shí)現(xiàn)傳播網(wǎng)絡(luò)更準(zhǔn)確推斷，另一方面能減少執(zhí)行時(shí)間，進(jìn)一步保證處理效率。

傳播網(wǎng)絡(luò); 內(nèi)聯(lián)性; 推斷模型

傳播路由網(wǎng)絡(luò)推斷主要以多次傳播過程中所有節(jié)點(diǎn)被感染情況為基礎(chǔ)，進(jìn)而推斷不同節(jié)點(diǎn)間影響關(guān)系與感染傳播概率。各條間相互影響的關(guān)系均可被設(shè)定為一條有向邊（由一父節(jié)點(diǎn)至一子節(jié)點(diǎn)），代表這一父節(jié)點(diǎn)受感染后直接把感染內(nèi)容（疾病、信息等）傳播到這一子節(jié)點(diǎn)，由此改變子節(jié)點(diǎn)感染情況；感染傳播概率代表受感染父節(jié)點(diǎn)把感染內(nèi)容傳播到未感染子節(jié)點(diǎn)，后者能被感染的概率，該可量化的概率值表明傳播網(wǎng)絡(luò)內(nèi)影響關(guān)系。為明確傳播路由網(wǎng)絡(luò)內(nèi)傳播過程，必須了解上述影響關(guān)系與感染傳播概率，如此便能更準(zhǔn)確推測后期傳播行為。比如，網(wǎng)絡(luò)信息安全部門能在病毒傳播網(wǎng)絡(luò)基礎(chǔ)上面向易感節(jié)點(diǎn)實(shí)施防控布署，輿情監(jiān)控員能在輿論傳播網(wǎng)絡(luò)基礎(chǔ)上推測輿論演變勢態(tài)[1]。

從部分傳播過程來看，如在線社交媒體上輿論傳播過程，感染時(shí)間記錄、獲取比較簡單，但從現(xiàn)實(shí)世界大量傳播過程來看，如網(wǎng)絡(luò)路由傳播過程或者疾病傳播過程，通常不能準(zhǔn)確、全面、有效獲取這部分信息[2]。這是因?yàn)楝F(xiàn)實(shí)世界很難實(shí)時(shí)監(jiān)控感染情況或定期完成感染情況普查工作。除此之外，即便上述要求全部得到滿足，但在節(jié)點(diǎn)間感染潛伏期(從受感染直至癥狀發(fā)生所用時(shí)間)有所區(qū)別等因素影響下，觀測確定感染時(shí)間不一定代表節(jié)點(diǎn)準(zhǔn)確、有效感染時(shí)間。故而對(duì)現(xiàn)實(shí)世界具體應(yīng)用而言，當(dāng)前大部分算法缺乏可用性與合理性[3,4]。

為克服當(dāng)前大部分算法不足之處，本次建立了只需根據(jù)若干次傳播過程完成后觀測所得不同節(jié)點(diǎn)感染情況，推測網(wǎng)絡(luò)內(nèi)不同節(jié)點(diǎn)間影響關(guān)系與感染傳播概率。首先，通過不同節(jié)點(diǎn)感染情況間互信息直接量化彼此間內(nèi)在關(guān)聯(lián)。因?yàn)榇蟛糠止?jié)點(diǎn)感染情況間屬于弱關(guān)聯(lián)，所以很多互信息值偏小，由此產(chǎn)生內(nèi)聚性傾向，以此為前提，可對(duì)存在強(qiáng)、弱關(guān)聯(lián)的節(jié)點(diǎn)進(jìn)行準(zhǔn)確劃分，發(fā)現(xiàn)可能的影響關(guān)系。其次，構(gòu)造出節(jié)點(diǎn)感染情況觀測結(jié)果（變量是感染傳播概率）相關(guān)對(duì)數(shù)似然函數(shù)，通過期望最 大化法進(jìn)行處理，同時(shí)計(jì)算出感染傳播概率。

1 問題描述

面對(duì)傳播路由網(wǎng)絡(luò)進(jìn)行問題推斷時(shí)，通常將該網(wǎng)絡(luò)視作一有向圖(,)，={v,…,v}表示節(jié)點(diǎn)集合，擁有該網(wǎng)絡(luò)內(nèi)部個(gè)節(jié)點(diǎn)；表示節(jié)點(diǎn)間有向邊集合，各條有向邊(v,v)指代父節(jié)點(diǎn)v對(duì)子節(jié)點(diǎn)v有影響關(guān)系，同時(shí)大多以(v,v)指代v與v間感染傳播概率。隨著(v,v)不斷增大，代表v受感染后，如果v未感染，那么v較大概率受v感染。不僅如此，各次傳播過程中，被感染節(jié)點(diǎn)可利用有向邊感染一些相鄰未感染節(jié)點(diǎn)，如果節(jié)點(diǎn)成功受感染，那么狀態(tài)始終固定。

本文在進(jìn)行分析討論時(shí)，針對(duì)無需感染時(shí)間的傳播網(wǎng)絡(luò)推斷問題，重點(diǎn)是個(gè)節(jié)點(diǎn)次傳播過程完成后各節(jié)點(diǎn)感染狀態(tài)數(shù)據(jù)={1,…,S}已知情況下，推斷節(jié)點(diǎn)間影響關(guān)系，換言之，需要得出有向邊集合，與各條有向邊對(duì)應(yīng)的感染傳播概率。已知情況下，S={,…,}代表第次(1≤≤)傳播過程完成后節(jié)點(diǎn)感染狀態(tài)集合。若=1、=0，分別表示第次傳播過程中v被感染、沒有感染。

2 本文所設(shè)計(jì)算法

下面本文首先重點(diǎn)描述以節(jié)點(diǎn)感染狀態(tài)間互信息為基礎(chǔ)的影響關(guān)系推斷算法，最后明確本文算法基本步驟。

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

通常來講，對(duì)于多次傳播過程而言，假若隨機(jī)兩節(jié)點(diǎn)v、v感染狀態(tài)值s?{0,1}與s?{0,1}服從等式(S=s,S=s)=(S=s)(S=s)，則S與S分別指代v、v感染狀態(tài)變量，此時(shí)能夠認(rèn)為v、v感染狀態(tài)彼此獨(dú)立，沒有關(guān)聯(lián)關(guān)系，換言之v、v間不可能有影響關(guān)系。從信息論來看，互信息一般用于量化評(píng)價(jià)兩變量間關(guān)聯(lián)關(guān)系。

早期進(jìn)行互信息計(jì)算時(shí)，需要注意兩節(jié)點(diǎn)所有感染狀態(tài)，也就是v與v各自兩種感染狀態(tài)值（含0與1）間關(guān)聯(lián)關(guān)系。早期算法主要基于統(tǒng)計(jì)學(xué)評(píng)價(jià)不同節(jié)點(diǎn)間關(guān)系，沒有考慮v被感染（S=1）、v被感染（S=1）事件間關(guān)聯(lián)關(guān)系。為明確節(jié)點(diǎn)間影響關(guān)系，需要判斷感染事件（S=1與S=1）之間有無關(guān)聯(lián)。所以，針對(duì)感染事件之間關(guān)聯(lián)程度，本文給出改進(jìn)后互信息算法進(jìn)行處理，詳情如下：

(v,v)取值較大時(shí)，表示v與v感染事件之間存在較明顯關(guān)聯(lián)關(guān)系，換言之，v與v間具有影響關(guān)系的可能性較高；相反，若(v,v)取值無限趨向?yàn)?，那么v與v間由影響關(guān)系可能性也無限趨向?yàn)?。

大部分情況下，傳播網(wǎng)絡(luò)內(nèi)單一節(jié)點(diǎn)v影響區(qū)域較小，簡單來講，當(dāng)節(jié)點(diǎn)僅能被v輕微影響時(shí)，它和v間才會(huì)出現(xiàn)較大改進(jìn)互信息值；不難理解，大部分節(jié)點(diǎn)和v間改進(jìn)互信息值非常低（無限趨向?yàn)?）。所以，許多較小改進(jìn)互信息取值會(huì)產(chǎn)生相應(yīng)內(nèi)聚性，由此和極大改進(jìn)互信息取值得到有效分類。-均值算法、支持向量機(jī)等劃分聚類算法均能得到一改進(jìn)互信息閾值，借此區(qū)別較大、較小改進(jìn)互信息取值。這里選擇-均值算法來說明，區(qū)別改進(jìn)互信息時(shí)，可采用以下步驟實(shí)現(xiàn)：（1）為所有節(jié)點(diǎn)求出它和剩余節(jié)點(diǎn)間改進(jìn)互信息；（2）令=2，執(zhí)行-均值算法，把全部互信息取值區(qū)別成兩個(gè)聚類；（3）設(shè)定閾值，即從較大聚類中直接確定最小改進(jìn)互信息值。

從值出發(fā)，可確定對(duì)節(jié)點(diǎn)存在潛在影響關(guān)系一些父節(jié)點(diǎn)集合F：

F={v|v?,v1v,(v,v)≥}集合F代表最可能讓v被感染節(jié)點(diǎn)，因此下面需要討論何種節(jié)點(diǎn)間感染傳播概率方案最大幾率形成次傳播過程完成后節(jié)點(diǎn)感染狀態(tài)數(shù)據(jù)。除此之外，通過聚類算法確定互信息時(shí)，容易出現(xiàn)噪點(diǎn)，也就是關(guān)于各節(jié)點(diǎn)v=?F可能包含非真實(shí)父節(jié)點(diǎn)，但推斷感染傳播概率時(shí)可有效去除。

2.2 算法步驟

本文主要將參數(shù)調(diào)整閾值Error（其將所有節(jié)點(diǎn)感染狀態(tài)數(shù)據(jù)與當(dāng)作期望最大化算法[5]收斂條件，故綜合考慮之下，這里Error取0.0001）視作輸入數(shù)據(jù)，輸出不同節(jié)點(diǎn)v?相關(guān)父節(jié)點(diǎn)集合F與所有感染傳播概率。經(jīng)歸納整理可知，算法包含4個(gè)階段，具體說明如下：（1）求出全部改進(jìn)互信息；（2）通過-均值求出改進(jìn)互信息相關(guān)閾值；（3）為各節(jié)點(diǎn)v?求其潛在父節(jié)點(diǎn)集合F；（4）通過期望最大化算法迭代所有感染傳播概率(v,v)，最終符合收斂條件。

3 結(jié)果與分析

這里先介紹實(shí)驗(yàn)相關(guān)設(shè)置，后探討各種因素給節(jié)點(diǎn)間影響關(guān)系、感染傳播概率推斷結(jié)果、算法用時(shí)帶來的影響，相關(guān)因素包括傳播網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量與邊密度（邊與節(jié)點(diǎn)總數(shù)之比）、初始感染節(jié)點(diǎn)比例等。此次實(shí)驗(yàn)過程中，所有算法都以Java來建立，并選擇Windows 10操作系統(tǒng)，3.7 GHz的Intel Core i 3-6100 CPU和8 GB內(nèi)存臺(tái)式機(jī)。

3.1 實(shí)驗(yàn)設(shè)置

這里人工合成傳播網(wǎng)絡(luò)選用LFR基準(zhǔn)圖[6]，進(jìn)而測試算法準(zhǔn)確性和執(zhí)行時(shí)間。從LFR網(wǎng)絡(luò)來看，可設(shè)定各種點(diǎn)、邊數(shù)量，由此創(chuàng)建各種傳播網(wǎng)絡(luò)(詳情如表1所示)。除此之外，本次引入微博中真實(shí)傳播網(wǎng)絡(luò)DUNF[5]，內(nèi)含750個(gè)節(jié)點(diǎn)(用戶)以及2794條邊（關(guān)注與轉(zhuǎn)發(fā)量）。

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

基于這部分人工合成與實(shí)際網(wǎng)絡(luò)結(jié)構(gòu)，設(shè)定網(wǎng)絡(luò)內(nèi)部邊的傳播概率滿足高斯分布（均值是0.3，方差是0.05），保證超過95%概率值處于0.2~0.4區(qū)間內(nèi)。同時(shí)采用獨(dú)立級(jí)聯(lián)模型，有效模擬次爆發(fā)無時(shí)間信息情況，借此重構(gòu)這部分網(wǎng)絡(luò)。

針對(duì)傳播網(wǎng)絡(luò)推斷準(zhǔn)確性，主要通過值、均方誤差（MSE）進(jìn)行評(píng)價(jià)，針對(duì)算法效率，主要以執(zhí)行時(shí)間進(jìn)行評(píng)價(jià)。本文選擇兩種算法當(dāng)作比較方法，其一，高性能基于感染時(shí)間的算法Net Rate[7]；其二，高效且與感染時(shí)間無關(guān)的算法LIFT[8]。

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

即傳播網(wǎng)絡(luò)內(nèi)所有支持?jǐn)?shù)據(jù)傳播的節(jié)點(diǎn)數(shù)量，一般能夠反映傳播網(wǎng)絡(luò)大小。這里共選擇5個(gè)傳播網(wǎng)絡(luò)（LFR1-5，同一平均度而節(jié)點(diǎn)數(shù)目存在差異）進(jìn)行分析，由此判斷這類節(jié)點(diǎn)數(shù)量給真實(shí)結(jié)果帶來的影響，同時(shí)選擇150次傳播過程中節(jié)點(diǎn)感染狀態(tài)觀測數(shù)據(jù)（=150）進(jìn)行處理。結(jié)合圖1來說明，圖中完成了不同算法影響關(guān)系推斷情況值比較。由此不難發(fā)現(xiàn)，當(dāng)網(wǎng)絡(luò)規(guī)模持續(xù)增大時(shí)，所有算法值逐漸減小，而從規(guī)模較小、較大的數(shù)據(jù)集來看，本文算法均表現(xiàn)出較為領(lǐng)先的優(yōu)勢。結(jié)合圖2來說明，圖中完成了Net Rate、本文算法感染傳播概率推斷結(jié)果均方誤差比較，隨著網(wǎng)絡(luò)規(guī)模越來越大，二者均方誤差明顯降低，相比之下本文算法表現(xiàn)更低。

圖 1 傳播網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量對(duì)F值的影響

圖 2 傳播網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量對(duì)均方誤差的影響

3.3 初始感染節(jié)點(diǎn)比例的影響

圖 3 初始感染節(jié)點(diǎn)比例對(duì)F值的影響

圖 4 初始感染節(jié)點(diǎn)比例對(duì)均方誤差的影響

4 結(jié)語

本文目標(biāo)在于提出更理想傳播網(wǎng)絡(luò)推斷算法，既要保證準(zhǔn)確性、高效性，又無須考慮感染時(shí)間信息，結(jié)合該目標(biāo)要求，本文首先通過不同節(jié)點(diǎn)感染情況間互信息直接量化彼此間內(nèi)在關(guān)聯(lián)，由此確定所有可能存在的影響關(guān)系。其次，構(gòu)造出節(jié)點(diǎn)感染情況觀測結(jié)果（變量是感染傳播概率）相關(guān)對(duì)數(shù)似然函數(shù)，通過期望最大化法進(jìn)行處理，同時(shí)計(jì)算感染傳播概率。結(jié)合實(shí)驗(yàn)分析不難發(fā)現(xiàn)，相較當(dāng)前算法而言，該算法優(yōu)勢較為明顯，一方面能實(shí)現(xiàn)傳播網(wǎng)絡(luò)更準(zhǔn)確推斷，另一方面能減少執(zhí)行時(shí)間，進(jìn)一步保證處理效率。

[1] Gomez-Rodriguez M, Leskovec J, Sch?lkopf B. Modeling information propagation with survival theory[C]. Atlanta, Georgia, USA: Proceedings of the 30thInternational Conference on Machine Learning, 2013

[2] Amin K, Heidari H, Kearns M. Learning from contagion (without timestamps)[C]. Beijing, China: Proceedings of the 31stInternational Conference on Machine Learning, 2014

[3] Gomez-Rodriguez M, Sch?lkopf B. Submodular inference of diffusion networks from multiple trees[C]. Edinburgh, Scotland, UK: Proceedings of the 29thInternational Conference on Machine Learning, 2012

[4] Mehmood Y, Barbieri N, Bonchi F,. CSI: Community-level social influence analysis[C]. Prague, Czech Republic: Proceedings, Part II, of the European Conference on Machine Learning and Knowledge Discovery in Databases, 2013

[5] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E, 2008,78(4):046110

[6] Wang S, Hu X, Yu PS,. MM Rate: Inferring multiaspect diffusion networks with multi-pattern cascades[C]. New York, USA: Proceedings of the 20thACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2014

[7] Gomez-Rodrigue M, Balduzzi D, Sch?lkopf B. Uncovering the temporal dynamics of diffusion networks[C]. Bellevue, Washington, USA: Proceedings of the 28th International Conference on Machine Learning, 2011

[8] Amin K, Heidari H, Kearns M. Learning from contagion(without timestamps)[C]. Beijing, China: Proceedings of the 31st International Conference on Machine Learning, 2014

Study on The Inference Model of Communication Network Based on Node Inconsistency

XU Nan-nan1, HU Chen-guang1, YU Xiao-hui2

1.100176,2.101149,

In order to overcome the communication network node inference cannot be obtained accurately infection time information, firstly the inconsistency between nodes is quantified by infection information between different nodes to determine all the possible influence relationship. Secondly, the logarithmic likelihood function of node infection transmission probability is constructed and calculated by expectation maximization method. The results showed this algorithm was better than current one, on the one hand, it could achieve a more accurate inference for a communication network, on the other hand, it could reduce the execution time and further ensure the processing efficiency.

Communication network; inconsistency; inference model

TP391

A

1000-2324(2019)01-0159-04

10.3969/j.issn.1000-2324.2019.01.036

2018-01-12

2018-03-03

國家自然科學(xué)基金項(xiàng)目(71801016);北京電子科技職業(yè)學(xué)院校內(nèi)重點(diǎn)課題:基于微信企業(yè)號(hào)的移動(dòng)校園服務(wù)平臺(tái)搭建研究(CJGX2016-KY-YZK030)

徐楠楠(1982-),女,碩士,工程師,主要從事高校信息化建設(shè)、數(shù)據(jù)分析、網(wǎng)絡(luò)管理研究. E-mail:xunn0828@sina.com