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

摘要：

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

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

分类号：TP311(计算技术、计算机技术)

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

在线出版日期：2013-12-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：41-45,51