基于双重启发式信息求解影响最大化问题的蚁群算法

针对如何利用社会个体之间的影响力来扩大信息扩散的范围,即社会网络的影响最大化问题,提出一种新颖的基于蚁群优化算法的解决方案。利用2个启发式信息来度量节点影响力:优先选择更不容易被前驱节点激活的节点;考虑后继尤其是多级后继节点对未来扩散的影响。通过节点影响力选择出能扩散最大范围的初始节点集合。试验结果表明,相较于贪心算法以及传统的蚁群算法初始节点的扩散范围增加了150个节点,效率提高了25%,本研究方法很好的改善了初始节点选择容易陷入局部最优的问题。

Ant colony optimization for solving maximization problem based ondouble heuristic information

With How to use influence of social individuals to expand the scope of information dissemination was an Influence Maximization problem, which had become an important research field. A new ant colony algorithm was propsed to solve the problem, in the initial node selection process, we introduced two heuristic information to measure node-influence: priority selected nodes that were less likely to be activated by the precursor node; considered the impact of successors, especially multi-level successors node on the influence of spread. Based on this, a new ant colony optimization algorithm was proposed. The experiments showed that our method improved the problem of initial node selection, which was easy to fall into the local optimum, the results were better than the greedy method and the traditional ant colony optimization algorithm in the efficiency(raise 25%) and range of initial node dissemination(add 150 nodes).