基于概率转移矩阵的社会网络影响最大化算法  

Influence Maximization Algorithm in Social Network Based on Probability Transfer Matrix

作　　者：张佩云[1,2] 宫秀文[1] 

机构地区：[1]安徽师范大学数学计算机科学学院,安徽芜湖241003 [2]中国科学技术大学计算机科学与技术学院,合肥230026

出　　处：《计算机工程》2013年第11期41-45,51,共6页Computer Engineering

基　　金：国家自然科学基金资助项目(61201252);安徽省自然科学基金资助项目(1308085MF100);博士后科学基金资助项目(2013M531528);安徽省高校省级自然科学研究基金资助重点项目(KJ2011A128);安徽省科技厅软科学研究计划基金资助项目(11020503009)

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

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]