计算机科学与探索 ›› 2019, Vol. 13 ›› Issue (4): 541-553.DOI: 10.3778/j.issn.1673-9418.1807046

• 学术研究 • 上一篇    下一篇

无需感染时间信息的传播网络快速推断算法

孙月明1,张运加1,颜  钱1,陈  璐2,黄  浩1+,高云君3   

  1. 1. 武汉大学 计算机学院,武汉 430072
    2. 奥尔堡大学 计算机科学系,丹麦 奥尔堡 DK-9220
    3. 浙江大学 计算机科学与技术学院,杭州 310027
  • 出版日期:2019-04-01 发布日期:2019-04-10

Fast Inference Algorithm of Diffusion Networks Without Infection Temporal Information

SUN Yueming1, ZHANG Yunjia1, YAN Qian1, CHEN Lu2, HUANG Hao1+, GAO Yunjun3   

  1. 1. School of Computer Science, Wuhan University, Wuhan 430072, China
    2. Department of Computer Science, Aalborg University, Aalborg DK-9220, Denmark
    3. College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China
  • Online:2019-04-01 Published:2019-04-10

摘要: 现有的大多数传播网络推断方法需要节点的感染时间信息,但是在许多现实传播过程中,准确的感染时间信息往往是难以获得的。以准确、高效且无需感染时间信息的传播网络推断方法为目标,研究了如何仅利用多次传播过程结束时观测到的各节点的感染状态来推断节点间的影响关系和感染传播概率。为此,该方法首先利用节点感染状态间的互信息来量化它们之间的相互关联,找出可能的节点间影响关系。然后,构建以感染传播概率为变量的节点感染状态观测数据的对数似然函数,并采用期望最大化的方法最大化该对数似然函数并求解感染传播概率。实验结果表明,相较现有方法,该方法有效提高了传播网络推断的准确性,并且大幅缩短了算法运行所需时间。

关键词: 传播网络推断, 影响关系, 感染传播概率, 感染时间信息

Abstract: Most existing approaches to diffusion network inference require the infection temporal information of nodes. But in many real-world diffusion processes, the exact infection temporal information is often unavailable. This paper aims at an effective, efficient and infection temporal information-free approach for diffusion network inference, and studies how to infer the influence relationships and transmission rates between the nodes based on only the final infection statuses of the nodes observed in a number of diffusion processes. To this end, the approach proposed in this paper first utilizes the mutual information of infection statuses among the nodes to quantify the correlation of the infections and reveal the underlying influence relationships between the nodes. Then, the proposed approach constructs the log-likelihood function of the observed infection statuses with transmission rates as the variables, and adopts the expectation-maximization algorithm to maximize the function and approximate the optimal transmission rates. Extensive experimental results demonstrate that compared against the existing approaches, the proposed approach has a reasonably better accuracy performance on diffusion network inference, and significantly reduces runtime.

Key words: diffusion network inference, influence relationships, transmission rates, infection temporal information