一种改进的社交网络影响力最大化算法

An improved algorithm for influence maximization in social networks

社交网络影响力最大化即是在社交网络中如何挑选包含K个节点的种子节点集,去激活整个网络,使网络中最终被激活的节点数最大化。基于IC模型研究了社交网络影响力最大化问题。Diffusion degree算法提出了节点潜在影响力的概念,即一个节点的邻居节点的影响力也可以作为当前节点的影响力的一部分。基于Diffusion degree算法做出了改进,在考虑潜在影响力的时候进一步考虑了节点潜在影响力的有效性,更加准确地判断节点的影响力,再综合了算法Single Discount中的核心思想,从而选出更加优质的种子节点。仿真结果表明,该算法在影响范围上接近KK贪婪算法的影响范围,同时在时效性上优于Diffusion degree算法,较适合大型社交网络。

Influence maximization is the problem of selecting a seed set of top k seed nodes in a social network to maximize their influence spread under certain influence propagation models. This paper focuses on the problem of influence maximization in social network based on independent cascade model. The diffusion degree algorithm proposes that the influence of the neighbors of nodel can be considered as part of influence of the nodel. It makes improvements to the diffusion degree algorithm,considering which neighbors should be used as the potential influence and combining the core idea of the algorithm Single Discount to select better quality seed node. The experimental results show that the heuristics match the influence spread with the KK greedy algorithm and have a better performance than diffusion degree in efficiency.