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 of KK algorithm, and our algorithm has relatively very short running time. The experimental results also show that our algorithm outperforms HPG with the same heuristic factor c.%对于社交网络影响力最大化问题,Kemple和Kleinberg提出了有较好影响范围的贪心算法,但是KK算法的复杂度非常高,并不实用,利用线性阈值模型提出了一种基于节点激活阈值的启发式算法.它综合考虑了节点之间的影响力和节点的激活阈值,根据每个节点在激活过程中动态变化的阈值来计算PIN值,启发过程中,每一次都选取PIN最大的节点作为种子节点进行激活,贪心阶段中再贪心地挑选那些具有最大影响范围增量的节点作为种子节点.通过实验表明,即使在完全不采用贪心阶段,该算法的激活范围与KK算法都非常接近,而算法的复杂度则相对非常小.实验还表明该算法相对于HPG算法在相同启发因子c的情况下具有更大的激活范围.
展开▼
