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

摘要

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