影响最大化问题中基于K-truss的投票改进算法

Improved Voting Algorithm Based on K-truss for Influence Maximization Problem

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

In the Influence Maximization(IM)problem of social networks,approximation algorithms are used to calculate the impact range of node sets via a significant amount of Monte-Carlo simulations,thus resulting in an increase in time complexity.Most heuristic algorithms exhibit unsatisfactory stability on graphs with different topological structures.This study proposes an improved voting algorithm,TrussVote,which is based on K-truss.In the voting stage,the effective voting ability of a node is defined by introducing the relevant theory and algorithm of K-truss,which is used to represent the voting tendency of a node to its different neighbors.Additionally,the propagation probability of edges is considered when calculating the voting score to improve the efficiency of the algorithm in solving IM problems.After each round of voting,the node with the highest voting score is selected as the seed node.In the update phase,the attenuation factor is defined based on the similarity index between nodes to effectively distinguish the weakening degree of neighboring nodes’ voting ability.In addition,based on the original propagation results under the IC model,the Diffusion Difference(DD)is proposed as an analysis index equivalent to the propagation range.Experimental results on real network datasets of different scales show that compared with RNR,VoteRank++,and other algorithms,the proposed algorithm not only effectively reduces the time complexity,but also infects more nodes in the shortest duration and has a wider range of influence.