作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 先进计算与数据处理 • 上一篇    下一篇

时间传播网络中受影响顶点的预测

林天巧,赵雷   

  1. (苏州大学 计算机科学与技术学院,江苏 苏州 215006)
  • 收稿日期:2017-01-16 出版日期:2018-02-15 发布日期:2018-02-15
  • 作者简介:林天巧(1992—),男,硕士研究生,主研方向为数据管理与分析、社交网络;赵雷,教授。
  • 基金资助:
    国家自然科学基金(61572335);江苏省自然科学基金面上项目(BK20151223)。

Prediction of Influenced Node in Temporal Diffusion Network

LIN Tianqiao,ZHAO Lei   

  1. (School of Computer Science and Technology,Soochow University,Suzhou,Jiangsu 215006,China)
  • Received:2017-01-16 Online:2018-02-15 Published:2018-02-15

摘要: 在时间传播网络中预测受影响顶点时,验证顶点状态会耗费大量计算资源,并且计算顶点受影响概率是#P-hard问题。为此,基于路径跳数受限近似和迭代更新算法提出顶点受影响概率预测算法IPH,实现顶点受影响概率的近似计算,并选择其中概率最大的顶点进行验证。考虑到验证后剩余顶点受影响概率趋于相同,结合广度优先遍历(BFS)算法进一步提出相邻顶点受影响概率预测算法AIPH。实验结果表明,与BFS和随机游走算法相比,IPH与AIPH算法均具有较高的准确率和召回率。

关键词: 信息传播, 时间传播网络, 受影响顶点, 不确定数据, 启发式预测

Abstract: When predicting influenced nodes in Temporal Diffusion Network(TDN),it is costly to verify the states of nodes.Besides,it is #P-hard to compute the infection probability of nodes.Aiming at these problems,based on Hop Limited Approximative(HLA) and iterative update algorithm,this paper proposes IPH algorithm.It computes the infection probability of nodes approximately,verifies the state of node that has maximum infection probability in candidate set and updates candidate node set after verification.As infection probability of remain nodes are very close after verifications,this paper futher proposes AIPH algorithm based on Breath First Search(BFS) algorithm to solve this problem.Experimental results show that IPH algorithm and AIPH algorithm have better performance compared with BFS algorithm and Random Work(RW) algorithm.

Key words: information diffusion, Temporal Diffusion Network(TDN), influenced node, uncertain data, heuristic prediction

中图分类号: