科研之友
微信
新浪微博
Facebook
分享链接
摘要
在社交网络的影响最大化（IM）问题中，近似算法通过大量的Monte-Carlo模拟计算节点集的影响范围，导致时间复杂度提高，而多数启发式算法在具有不同拓扑结构的图上存在稳定性较差的问题。提出基于K-truss的改进投票算法TrussVote。在投票阶段，通过引入K-truss的相关理论及算法定义节点的有效投票能力，用于表示节点对其不同邻居的投票倾向，同时在计算得票分数时考虑边的传播概率，提高解决IM问题的效率。在每轮投票结束后，将得票分数最高的节点选为种子节点。在更新阶段，结合节点间的相似性指标定义衰减因子，以有效区分邻居节点投票能力的弱化程度。此外，基于IC模型下的原始传播结果，提出传播差异作为传播范围的等价分析指标。在不同规模真实网络数据集上的实验结果表明，相比RNR、VoteRank++等算法，该算法不仅能有效降低时间复杂度，而且可在最短的时间内感染更多的节点，具有广泛的影响范围。
- 单位
