基于阈值的社交网络影响力最大化算法
对于社交网络影响力最大化问题,Kemple和Kleinberg提出了有较好影响范围的贪心算法,但是KK算法的复杂度非常高,并不实用。利用线性阈值模型提出了一种基于节点激活阈值的启发式算法。它综合考虑了节点之间的影响力和节点的激活阈值,根据每个节点在激活过程中动态变化的阈值来计算PIN值,启发过程中,每一次都选取PIN最大的节点作为种子节点进行激活,贪心阶段中再贪心地挑选那些具有最大影响范围增量的节点作为种子节点。通过实验表明,即使在完全不采用贪心阶段,该算法的激活范围与KK算法都非常接近,而算法的复杂度则相对非常小。实验还表明该算法相对于HPG算法在相同启发因子c的情况下具有更大的激活范围。
社交网络 影响力最大化 计算方法 复杂度
Chen Hao 陈浩 Wang Yitong 王轶彤
School of Computer Science, Fudan University, Shanghai 201203 复旦大学计算机科学技术学院 上海201203
国内会议
合肥
中文
2181-2188
2012-10-01（万方平台首次上网日期，不代表论文的发表时间）