中文摘要：

社会网络中影响最大化问题是对于给定k值,寻找k个具有最大影响范围的节点集.这是一个优化问题并且是NP-完全的.Kemple和Kleinberg提出具有较好影响范围的贪心算法,但其时间复杂度很高,不能适用在大型社会网络中,并且不能保证最好的影响范围.文中利用线性阈值模型的＂影响力积累＂特性,提出了一个该模型下影响最大化算法的框架,并在此框架基础上给出一个新的算法HPG.HPG综合考虑网络的结构特性和传播特性,首先启发式选择PI值最大的节点,然后寻找最具影响力的节点.实验结果显示HPG在最终影响范围和运行时间上都获得比贪心算法更好的效果.

英文摘要：

Influence maximization is a problem of finding a small subset of nodes（target set） in a social network that could maximize the spread of influence.This optimization problem of influence maximization is NP-hard under several most widely studied diffusion models and is even challenging for current online social networks which contain both positive and negative relations.Kemple and Kleinberg proposed a natural climbing-hill greedy algorithm that chooses the nodes which could provide a good marginal influence.This greedy algorithm has large spread of influence,but is very costly and cannot be applied to large social networks.Also,greedy algorithm could not guarantee the best influence spread.In this paper,we propose a framework on the linear threshold model and a hybrid potential-influence greedy algorithm（HPG） which can make good use of the ＂influence accumulation＂ property of the linear threshold model.Considering the network structure and propagation characteristics,HPG algorithm first heuristically choose half of the initial seeds with the biggest potential influence（PI） and then greedily choose the other half initial seeds with the most influence.Experiments are conducted comprehensively on different real datasets（including weighted social networks,directed social networks and signed social networks）.Experimental results demonstrate that HPG algorithm significantly outperforms the local-optimal greedy algorithm and could achieve reduced running time.