基于节点内联性的传播网络推断模型研究

徐楠楠,胡晨光,于晓辉



基于节点内联性的传播网络推断模型研究

徐楠楠1,胡晨光1,于晓辉2

1. 北京电子科技职业学院 信息中心, 北京 100176 2. 北京物资学院 物流学院, 北京 101149

为了有效克服传播网络节点推断时，无法准确获得感染时间信息的问题，首先通过不同节点感染情况间信息直接量化节点间的内联性，由此确定所有可能存在的影响关系。其次，构造出节点感染传播概率的相关对数似然函数，通过期望最大化法进行处理，同时计算感染传播概率。结果表明，相较当前算法而言，该算法优势较为明显，一方面能实现传播网络更准确推断，另一方面能减少执行时间，进一步保证处理效率。

传播网络; 内联性; 推断模型

传播路由网络推断主要以多次传播过程中所有节点被感染情况为基础，进而推断不同节点间影响关系与感染传播概率。各条间相互影响的关系均可被设定为一条有向边（由一父节点至一子节点），代表这一父节点受感染后直接把感染内容（疾病、信息等）传播到这一子节点，由此改变子节点感染情况；感染传播概率代表受感染父节点把感染内容传播到未感染子节点，后者能被感染的概率，该可量化的概率值表明传播网络内影响关系。为明确传播路由网络内传播过程，必须了解上述影响关系与感染传播概率，如此便能更准确推测后期传播行为。比如，网络信息安全部门能在病毒传播网络基础上面向易感节点实施防控布署，舆情监控员能在舆论传播网络基础上推测舆论演变势态[1]。

从部分传播过程来看，如在线社交媒体上舆论传播过程，感染时间记录、获取比较简单，但从现实世界大量传播过程来看，如网络路由传播过程或者疾病传播过程，通常不能准确、全面、有效获取这部分信息[2]。这是因为现实世界很难实时监控感染情况或定期完成感染情况普查工作。除此之外，即便上述要求全部得到满足，但在节点间感染潜伏期(从受感染直至症状发生所用时间)有所区别等因素影响下，观测确定感染时间不一定代表节点准确、有效感染时间。故而对现实世界具体应用而言，当前大部分算法缺乏可用性与合理性[3,4]。

为克服当前大部分算法不足之处，本次建立了只需根据若干次传播过程完成后观测所得不同节点感染情况，推测网络内不同节点间影响关系与感染传播概率。首先，通过不同节点感染情况间互信息直接量化彼此间内在关联。因为大部分节点感染情况间属于弱关联，所以很多互信息值偏小，由此产生内聚性倾向，以此为前提，可对存在强、弱关联的节点进行准确划分，发现可能的影响关系。其次，构造出节点感染情况观测结果（变量是感染传播概率）相关对数似然函数，通过期望最 大化法进行处理，同时计算出感染传播概率。

1 问题描述

面对传播路由网络进行问题推断时，通常将该网络视作一有向图(,)，={v,…,v}表示节点集合，拥有该网络内部个节点；表示节点间有向边集合，各条有向边(v,v)指代父节点v对子节点v有影响关系，同时大多以(v,v)指代v与v间感染传播概率。随着(v,v)不断增大，代表v受感染后，如果v未感染，那么v较大概率受v感染。不仅如此，各次传播过程中，被感染节点可利用有向边感染一些相邻未感染节点，如果节点成功受感染，那么状态始终固定。

本文在进行分析讨论时，针对无需感染时间的传播网络推断问题，重点是个节点次传播过程完成后各节点感染状态数据={1,…,S}已知情况下，推断节点间影响关系，换言之，需要得出有向边集合，与各条有向边对应的感染传播概率。已知情况下，S={,…,}代表第次(1≤≤)传播过程完成后节点感染状态集合。若=1、=0，分别表示第次传播过程中v被感染、没有感染。

2 本文所设计算法

下面本文首先重点描述以节点感染状态间互信息为基础的影响关系推断算法，最后明确本文算法基本步骤。

2.1 节点间影响关系推断

通常来讲，对于多次传播过程而言，假若随机两节点v、v感染状态值sÎ{0,1}与sÎ{0,1}服从等式(S=s,S=s)=(S=s)(S=s)，则S与S分别指代v、v感染状态变量，此时能够认为v、v感染状态彼此独立，没有关联关系，换言之v、v间不可能有影响关系。从信息论来看，互信息一般用于量化评价两变量间关联关系。

早期进行互信息计算时，需要注意两节点所有感染状态，也就是v与v各自两种感染状态值（含0与1）间关联关系。早期算法主要基于统计学评价不同节点间关系，没有考虑v被感染（S=1）、v被感染（S=1）事件间关联关系。为明确节点间影响关系，需要判断感染事件（S=1与S=1）之间有无关联。所以，针对感染事件之间关联程度，本文给出改进后互信息算法进行处理，详情如下：

(v,v)取值较大时，表示v与v感染事件之间存在较明显关联关系，换言之，v与v间具有影响关系的可能性较高；相反，若(v,v)取值无限趋向为0，那么v与v间由影响关系可能性也无限趋向为0。

大部分情况下，传播网络内单一节点v影响区域较小，简单来讲，当节点仅能被v轻微影响时，它和v间才会出现较大改进互信息值；不难理解，大部分节点和v间改进互信息值非常低（无限趋向为0）。所以，许多较小改进互信息取值会产生相应内聚性，由此和极大改进互信息取值得到有效分类。-均值算法、支持向量机等划分聚类算法均能得到一改进互信息阈值，借此区别较大、较小改进互信息取值。这里选择-均值算法来说明，区别改进互信息时，可采用以下步骤实现：（1）为所有节点求出它和剩余节点间改进互信息；（2）令=2，执行-均值算法，把全部互信息取值区别成两个聚类；（3）设定阈值，即从较大聚类中直接确定最小改进互信息值。

从值出发，可确定对节点存在潜在影响关系一些父节点集合F：

F={v|vÎ,v¹v,(v,v)≥}集合F代表最可能让v被感染节点，因此下面需要讨论何种节点间感染传播概率方案最大几率形成次传播过程完成后节点感染状态数据。除此之外，通过聚类算法确定互信息时，容易出现噪点，也就是关于各节点v=ÎF可能包含非真实父节点，但推断感染传播概率时可有效去除。

2.2 算法步骤

本文主要将参数调整阈值Error（其将所有节点感染状态数据与当作期望最大化算法[5]收敛条件，故综合考虑之下，这里Error取0.0001）视作输入数据，输出不同节点vÎ相关父节点集合F与所有感染传播概率。经归纳整理可知，算法包含4个阶段，具体说明如下：（1）求出全部改进互信息；（2）通过-均值求出改进互信息相关阈值；（3）为各节点vÎ求其潜在父节点集合F；（4）通过期望最大化算法迭代所有感染传播概率(v,v)，最终符合收敛条件。

3 结果与分析

这里先介绍实验相关设置，后探讨各种因素给节点间影响关系、感染传播概率推断结果、算法用时带来的影响，相关因素包括传播网络节点数量与边密度（边与节点总数之比）、初始感染节点比例等。此次实验过程中，所有算法都以Java来建立，并选择Windows 10操作系统，3.7 GHz的Intel Core i 3-6100 CPU和8 GB内存台式机。

3.1 实验设置

这里人工合成传播网络选用LFR基准图[6]，进而测试算法准确性和执行时间。从LFR网络来看，可设定各种点、边数量，由此创建各种传播网络(详情如表1所示)。除此之外，本次引入微博中真实传播网络DUNF[5]，内含750个节点(用户)以及2794条边（关注与转发量）。

表 1 LFR网络

基于这部分人工合成与实际网络结构，设定网络内部边的传播概率满足高斯分布（均值是0.3，方差是0.05），保证超过95%概率值处于0.2~0.4区间内。同时采用独立级联模型，有效模拟次爆发无时间信息情况，借此重构这部分网络。

针对传播网络推断准确性，主要通过值、均方误差（MSE）进行评价，针对算法效率，主要以执行时间进行评价。本文选择两种算法当作比较方法，其一，高性能基于感染时间的算法Net Rate[7]；其二，高效且与感染时间无关的算法LIFT[8]。

3.2 传播网络节点数量的影响

即传播网络内所有支持数据传播的节点数量，一般能够反映传播网络大小。这里共选择5个传播网络（LFR1-5，同一平均度而节点数目存在差异）进行分析，由此判断这类节点数量给真实结果带来的影响，同时选择150次传播过程中节点感染状态观测数据（=150）进行处理。结合图1来说明，图中完成了不同算法影响关系推断情况值比较。由此不难发现，当网络规模持续增大时，所有算法值逐渐减小，而从规模较小、较大的数据集来看，本文算法均表现出较为领先的优势。结合图2来说明，图中完成了Net Rate、本文算法感染传播概率推断结果均方误差比较，随着网络规模越来越大，二者均方误差明显降低，相比之下本文算法表现更低。

图 1 传播网络节点数量对F值的影响

图 2 传播网络节点数量对均方误差的影响

3.3 初始感染节点比例的影响

图 3 初始感染节点比例对F值的影响

图 4 初始感染节点比例对均方误差的影响

4 结语

本文目标在于提出更理想传播网络推断算法，既要保证准确性、高效性，又无须考虑感染时间信息，结合该目标要求，本文首先通过不同节点感染情况间互信息直接量化彼此间内在关联，由此确定所有可能存在的影响关系。其次，构造出节点感染情况观测结果（变量是感染传播概率）相关对数似然函数，通过期望最大化法进行处理，同时计算感染传播概率。结合实验分析不难发现，相较当前算法而言，该算法优势较为明显，一方面能实现传播网络更准确推断，另一方面能减少执行时间，进一步保证处理效率。

[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

国家自然科学基金项目(71801016);北京电子科技职业学院校内重点课题:基于微信企业号的移动校园服务平台搭建研究(CJGX2016-KY-YZK030)

徐楠楠(1982-),女,硕士,工程师,主要从事高校信息化建设、数据分析、网络管理研究. E-mail:xunn0828@sina.com