基于PageRank的社交网络影响最大化传播模型与算法研究

Research on Propagation Model and Algorithm for Influence Maximization in Social Network Based on PageRank

社交网络中影响最大化问题是指找出最具有影响力的k个节点,使得最终社交网络中被影响的节点最多,信息传播范围最大。针对影响最大化问题,目前已存在一些基本传播模型,但是这些模型没有考虑网络中节点的相关性和重要性,而网络中节点的相关性和重要性是衡量其影响力的一个重要指标,因此,提出了一种基于网页排名算法的信息传播模型(PageRank-based Propagation Model,PRP),然后利用贪心算法来近似求解影响最大化问题。实验结果表明,基于PageRank的传播模型解决影响最大化问题的效果比传统的线性阈值模型、加权级联模型和独立级联模型的效果更好,影响力范围更大。

The influence maximization problem in social network is to find top-k influential nodes in graph that maximize the number of influenced nodes. Some basic propagation models have been proposed to solve the influence maximization problem. But those models do not consider the relativity and importance of the node which we consider as an important measurement of influence. Thus, we propose a new PageRank-based propagation model, and employ the Greedy Algorithm to solve the influence maximization problem. The experimental results show that our proposed model is more effective than traditional Linear Threshold Model,Weighted Cascade Model and Independent Cascade Model in solving the influence maximization problem.