社会网络中基于社群衰减的影响力最大化算法

Influence maximization algorithm on internal decay based on community structure in social network

针对现有网络传播模型忽略了信息传播过程中的信息衰减,传统影响力最大化算法无法有效利用社群结构提高影响力传播范围的问题,提出一种基于社群结构的影响力最大化算法——社群衰减的影响力最大化(IMID)算法。首先对整个社会网络进行社群结构划分,评估社群中节点影响力范围,并考虑社群之间关联点之间的关联概率,在信息传播过程中增加节点之间信息传播衰减度计算。通过实验与分析,该算法不仅降低了时间复杂度,还获得了接近贪心算法的影响力传播范围,影响覆盖率达到90%以上。因此,在核心种子节点集和连接社群之间纽带节点选取若干节点作为初始节点,会让信息以最小的代价在网络中获得广泛传播。

The existing network spread model ignores the information attenuation in the process of information spread,and the traditional influence maximization algorithm cannot effectively use the community structure to improve the influence spread range.To solve these problems,an algorithm of Influence Maximization on Internal Decay(IMID)based on community structure was proposed.Firstly,the community structure of a whole social network was divided and the influence range of nodes in the community was evaluated.Then,with spread probability of association points between the communities considered,the attenuation degree of information spread between nodes was calculated.Experimental and analysis results show that the proposed algorithm not only reduces the time complexity,but also obtains the influence transmission range near that of greedy algorithm,with influence coverage over 90%.Therefore,with several nodes selected as the initial nodes between the core seed node set and connected communities,information will be widely spread in the network at the minimum cost.