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

Ant colony optimization for solving maximization problem based on double heuristic information

作　　者：覃俊[1] 李蔚栋 易金莉[1] 刘晶[1] 马懋德[2] QIN Jun;LI Weidong;YI Jinli;LIU Jing;MA Maode(Collage of Computer Science,South-Central University for Nationalities,Wuhan 430000,Hubei,China;Nanyang Technological University,Singapore 999002,Singapore)

机构地区：[1]中南民族大学计算机科学学院,湖北武汉430000 [2]南洋理工大学,新加坡999002

出　　处：《山东大学学报（工学版）》2020年第3期45-50,共6页Journal of Shandong University（Engineering Science）

基　　金：国家自然科学基金资助项目(61772562);湖北省自然科学基金资助项目(2017CFC886)。

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

关 键 词：社会网络 蚁群算法 影响最大化 信息扩散 启发式算法 

分 类 号：TP30[自动化与计算机技术—计算机系统结构]