基于阈值的社交网络影响力最大化算法  

Threshold-Based Heuristic Algorithm for Influence Maximization

作　　者：陈浩[1] 王轶彤[1] 

机构地区：[1]复旦大学计算机科学技术学院,上海201203

出　　处：《计算机研究与发展》2012年第10期2181-2188,共8页Journal of Computer Research and Development

基　　金：国家自然科学基金重点项目(61033010)

摘　　要：对于社交网络影响力最大化问题,Kemple和Kleinberg提出了有较好影响范围的贪心算法,但是KK算法的复杂度非常高,并不实用.利用线性阈值模型提出了一种基于节点激活阈值的启发式算法.它综合考虑了节点之间的影响力和节点的激活阈值,根据每个节点在激活过程中动态变化的阈值来计算PIN值,启发过程中,每一次都选取PIN最大的节点作为种子节点进行激活,贪心阶段中再贪心地挑选那些具有最大影响范围增量的节点作为种子节点.通过实验表明,即使在完全不采用贪心阶段,该算法的激活范围与KK算法都非常接近,而算法的复杂度则相对非常小.实验还表明该算法相对于HPG算法在相同启发因子c的情况下具有更大的激活范围.Influence maximization is a problem of finding a subset of nodes in a social network that can maximize the spread of influence. This optimization problem of influence maximization is proved NP- hard. Kemple and Kleinberg proposed a natural climbing-hill greedy algorithm that chooses the nodes which could provide the best marginal influence （KK algorithm）. KK algorithm has large spread of influence, but is too costly for large social network. We propose a threshold-based heuristic algorithm （TBH） for social network influence maximization based on activation threshold of nodes. The algorithm computes potential influenced nodes （PIN） according to dynamically changing activation threshold of nodes in activating process. In heuristic phase, we select the nodes with maximal PIN as seed nodes. Then, in greedy phase, we greedily select the nodes having maximal margin gain of influence as seed nodes. Our experiments demonstrate that, even without the greedy phase, the performance of our algorithm is close to that short running time. same heuristic factor c experimental results of KK algorithm, and our algorithm has relatively very also show that our algorithm outperforms HPG with the

关 键 词：社交网络 影响力最大化 启发式算法 贪心算法 TBH 

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