摘要： 现有近似求解影响最大化算法的时间复杂度较高，为此，提出一种扩展的线性阈值模型及其概率转移矩阵，给出该模型的传播过程及规则，设计基于概率转移矩阵的影响最大化算法，并利用贪心方法寻找到k个最具影响的节点。该算法通过矩阵乘积的方法得到T时刻节点之间的影响概率，无需在每个时刻计算所有非活跃节点的边际效益，从而在较短时间内提高运行时的效率，使得在规模较大的社会网络中被影响的节点最多且信息传播范围最广。仿真实验结果表明，在大规模社会网络中，该算法对社会网络节点的影响范围广且时间复杂度低。

关键词: 社会网络, 线性阈值模型, 信息传播, 影响最大化, 概率转移矩阵, 贪心算法

Abstract: Aiming at the high time complexity of some algorithms which solve the influence maximization problem, this paper proposes an extended linear threshold propagation model and the probability transfer matrix. The propagation process and rules of the model are proposed. It designs the influence maximization algorithm based on probability transfer matrix and utilizes the greedy method to find the top-k nodes with more influence power. The algorithm computes the probability effect of T instant by probability transfer matrix product. It need not compute the marginal benefit of inactive nodes at each moment. It can improve the efficiency of running in shorter time, and it can maximize the number of influenced nodes and can widen the range of information propagation in large-scale social network. Experimental results demonstrate the effectiveness and efficiency of the approach. The algorithm has wide influence range for social network nodes and has low time complexity in large social network.

Key words: social network, Linear Threshold(LT) model, information propagation, influence maximization, probability transfer matrix, greedy algorithm

中图分类号: 

• TP311