基于渗流模型的影响力最大化算法

多数社交网络影响力最大化算法的研究只关注于所选种子节点集合的影响力是否最优，忽略网络自身传播影响力的固有能力。本文对网络进行渗流模拟，计算渗流后网络的主连通分量随着传播概率改变的趋势，并且求得主连通分量大小增加开始变快的相变点，从而计算网络自身传播影响力的固有能力。通过相变值与种子节点集合大小的换算，求得当前网络最佳的种子节点集合大小。将种子节点集合大小限制在最佳大小范围内即可获得最佳的影响力。在kareteclub、football、highschool和socdolphins社交网络数据集上进行实验，验证了该方法的有效性。

An influence maximization algorithm based on percolation model

Most of the influence maximization algorithms in social networks only focus on whether the influence of the seed node set selected is the optimal, and ignore the inherent ability of social network’s propagating influence. Using percolation simulation, we calculate the change trend of the giant component of the network generation after percolation with propagation probability, and derive the starting point at which the size of the giant component increases fastest, that is, the phase point. The phase value shows the inherent ability of the network propagating influence. The optimal seed set size of the network can be calculated through conversion of the phase value and the size of the seed set. We can obtain the optimal influence by limiting the size of the seed set to the optimal size. We performed experiments on karate club, football, high school, and soc-dolphins, verifying the effectiveness of the algorithm.