您的位置:山东大学 -> 科技期刊社 -> 《山东大学学报(工学版)》

山东大学学报 (工学版) ›› 2020, Vol. 50 ›› Issue (3): 45-50.doi: 10.6040/j.issn.1672-3961.0.2019.306

• 机器学习与数据挖掘 • 上一篇    下一篇

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

覃俊1(),李蔚栋1,易金莉1,刘晶1,马懋德2   

  1. 1. 中南民族大学计算机科学学院, 湖北 武汉 430000
    2. 南洋理工大学, 新加坡 999002
  • 收稿日期:2019-06-13 出版日期:2020-06-20 发布日期:2020-06-16
  • 作者简介:覃俊(1968—),女,湖南常德人,博士,教授,主要研究方向为复杂网络,大数据,智能推荐算法. E-mail:Qjun@mail.scuec.edu.cn
  • 基金资助:
    国家自然科学基金资助项目(61772562);湖北省自然科学基金资助项目(2017CFC886)

Ant colony optimization for solving maximization problem based ondouble heuristic information

Jun QIN1(),Weidong LI1,Jinli YI1,Jing LIU1,Maode MA2   

  1. 1. Collage of Computer Science, South-Central University for Nationalities, Wuhan 430000, Hubei, China
    2. Nanyang Technological University, Singapore 999002, Singapore
  • Received:2019-06-13 Online:2020-06-20 Published:2020-06-16
  • Supported by:
    国家自然科学基金资助项目(61772562);湖北省自然科学基金资助项目(2017CFC886)

摘要:

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

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

Abstract:

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).

Key words: social network, ant colony, influence maximization, spread of information, heuristic algorithm

中图分类号: 

  • TP30

图1

当前仅有一个激活的前驱节点"

图2

IM-ACO算法整体框架"

表1

数据集信息"

数据集 节点数 边数
NetHEPT 15 233 62 794
Wiki_vote 7 115 103 689
Slashdot 77 360 905 468

图3

针对Wiki_vote数据集算法收敛情况"

图4

激活范围对比图"

图5

针对NetHEPT的不同扩散范围的扩散步数对比"

图6

针对NetHEPT的不同初始节点个数的扩散步数对比"

1 PIGI Kouki. Resolution, recommendation, and explan-ation in richly structured social networks[D]. Santa Cruz, USA: University of California, 2018.
2 CHEN Rui , HUA Qingyi , CHANG Yanshuo , et al. A survey of collaborative filtering-based recommender systems: from traditional methods to hybrid methods based on social networks[J]. IEEE Access, 2018, 6, 64301- 64320.
doi: 10.1109/ACCESS.2018.2877208
3 KUHUNHE Alan , MD ABDUL Alim , LI Xiang , et al. Multiplex influence maximization in online social net-works with heterogeneous diffusion models[J]. IEEE Transactions on Computational Social Systems, 2018, 5 (2): 418- 429.
doi: 10.1109/TCSS.2018.2813262
4 RODRIGUES Silva, RODRIGO Ferreira Rodrigues, VINICIUS Fonseca Vieira, et al. Influence maximization in Network by genetic algorithm on linear threshold model[C]//Proceedings of the Computational Science and Its Applications-ICCSA 2018-18th International Conference. Melbourne, Australia: IEEE, 2018: 96-109.
5 KEMPE D, KLEINBERG J, TARDOSÉ. Maximizing the spread of influence through a social network[C]//Proceedings of the 9th ACM SIGKDD International Conf-erence on Knowledge Discovery and Data Mining. Washington, USA: ACM, 2003: 137-146.
6 CHEN Wei, WANG Yajun, YANG Siyu. Efficient influence maximization in social networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris, France: ACM, 2009: 199-208.
7 LESKOVEC J, KRAUSE A, GUESTRIN C, et al. Cost-effective outbreak detection in networks[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2007: 420-429.
8 GOYAL Amit, LU Wei, LAKSHMANAN Lakes. Celf++: optimizing the greedy algorithm for influence maximization in social networks[C]//Proceedings of the 20th International Conference Companion on World Wide Web. New York, USA: ACM, 2011: 47-48.
9 CHEN Wei, YUAN Yifei, ZHANG Li. Scalable influence maximization in social networks under the linear threshold model[C]//Proceedings of the 10th IEEE International Conference on Data Mining. Sydney, Australia: IEEE, 2010: 88-97.
10 LI Weihua, BAI Quan, ZHANG Minjie. Modelling multiple influences diffusion in on-line social networks[C]//Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems. Stockholm, Sweden: ACM, 2018: 1053-1061.
11 田家堂, 王轶彤, 冯小军. 一种新型的社会网络影响最大化算法[J]. 计算机学报, 2011, 34 (10): 1956- 1965.
TIAN Jiatang , WANG Yitong , FENG Xiaojun . A wew social network influence maximization algorithm[J]. Chinese Journal of Computers, 2011, 34 (10): 1956- 1965.
12 陈浩, 王轶彤. 基于阈值的社交网络影响力最大化算法[J]. 计算机研究与发展, 2012, 49 (10): 2181- 2188.
CHEN Hao , WANG Yitong . A social network influence maximization algorithm based on threshold[J]. Journal of Computer Research and Development, 2012, 49 (10): 2181- 2188.
13 SUPREET Mandala , SOUNDAR Kumara , CALYAMPUDI Rao , et al. Clustering social networks using ant colony optimization[J]. Operational Research, 2013, 13 (1): 47- 65.
14 WU Yanfei, ZHU Yanqin, YANG Zhe. Routing algorithm based on ant colony optimization for mobile social network[C]// Proceedings of the 18th International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing. Kanazawa, Japan: IEEE, 2017: 297-302.
15 YANG W , WENG S , GUESTRIN C , et al. Application of the ant colony optimization algorithm to the influence-maximization problem[J]. International Journal of Swarm Intelligence and Evolutionary Computation, 2012, 1 (1): 1- 8.
16 覃俊, 易金莉. 基于前驱后继节点的社会网络影响最大化算法[J]. 中南民族大学学报(自然科学版), 2016, 35 (4): 95- 100.
QIN Jun , YI Jinli . Social network impact maximization algorithm based on predecessor successor node[J]. Journal of South-Central University for Nationalities, 2016, 35 (4): 95- 100.
[1] 胡云,张舒,李慧,佘侃侃,施珺. 基于信任网络重构的推荐算法[J]. 山东大学学报 (工学版), 2019, 49(2): 42-46.
[2] 陈嘉杰,王金凤. 基于蚁群算法求解Choquet模糊积分模型[J]. 山东大学学报(工学版), 2018, 48(3): 81-87.
[3] 任永峰,董学育. 基于自适应流形相似性的图像显著性区域提取算法[J]. 山东大学学报(工学版), 2017, 47(3): 56-62.
[4] 王启明, 李战国, 樊爱宛. 基于博弈论的量子蚁群算法[J]. 山东大学学报(工学版), 2015, 45(2): 33-36.
[5] 韩忠明, 吴杨, 谭旭升, 刘雯, 杨伟杰. 社会网络结构洞节点度量指标比较与分析[J]. 山东大学学报(工学版), 2015, 45(1): 1-8.
[6] 卢文羊, 徐佳一, 杨育彬. 基于LDA主题模型的社会网络链接预测[J]. 山东大学学报(工学版), 2014, 44(6): 26-31.
[7] 曾华1,崔文2,付连宁1,吴耀华1*. Lin-Kernighan算法初始解的启发式构造策略[J]. 山东大学学报(工学版), 2012, 42(2): 30-35.
[8] 吴克寿,陈玉明,曾志强. 基于邻域关系的决策表约简[J]. 山东大学学报(工学版), 2012, 42(2): 7-10.
[9] 李永胜,曲良东,李熹. 自适应信息素更新蚁群算法求解QoS组播路由[J]. 山东大学学报(工学版), 2011, 41(4): 38-43.
[10] 孙海鹰 陈崚. 蚁群算法解决连续优化问题的新途径[J]. 山东大学学报(工学版), 2009, 39(6): 24-30.
[11] 梅红,王勇,赵荣齐 . 基于蚁群神经网络算法的机器人逆解[J]. 山东大学学报(工学版), 2008, 38(5): 72-76 .
[12] 张贻弓,吴耀华 . 可合流的自动分拣系统订单排序优化[J]. 山东大学学报(工学版), 2008, 38(5): 67-71 .
[13] 陈欣,杨文东,陆迅,朱金福 . 一种机场终端区飞机排序问题的蚁群算法研究[J]. 山东大学学报(工学版), 2007, 37(6): 111-117 .
[14] 杨立才,赵莉娜,吴晓晴 . 基于蚁群算法的模糊C均值聚类医学图像分割[J]. 山东大学学报(工学版), 2007, 37(3): 51-54 .
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 张永花,王安玲,刘福平 . 低频非均匀电磁波在导电界面的反射相角[J]. 山东大学学报(工学版), 2006, 36(2): 22 -25 .
[2] 李 侃 . 嵌入式相贯线焊接控制系统开发与实现[J]. 山东大学学报(工学版), 2008, 38(4): 37 -41 .
[3] 施来顺,万忠义 . 新型甜菜碱型沥青乳化剂的合成与性能测试[J]. 山东大学学报(工学版), 2008, 38(4): 112 -115 .
[4] 李梁,罗奇鸣,陈恩红. 对象级搜索中基于图的对象排序模型(英文)[J]. 山东大学学报(工学版), 2009, 39(1): 15 -21 .
[5] 王波,王宁生 . 机电装配体拆卸序列的自动生成及组合优化[J]. 山东大学学报(工学版), 2006, 36(2): 52 -57 .
[6] 李可,刘常春,李同磊 . 一种改进的最大互信息医学图像配准算法[J]. 山东大学学报(工学版), 2006, 36(2): 107 -110 .
[7] 季涛,高旭,孙同景,薛永端,徐丙垠 . 铁路10 kV自闭/贯通线路故障行波特征分析[J]. 山东大学学报(工学版), 2006, 36(2): 111 -116 .
[8] 秦通,孙丰荣*,王丽梅,王庆浩,李新彩. 基于极大圆盘引导的形状插值实现三维表面重建[J]. 山东大学学报(工学版), 2010, 40(3): 1 -5 .
[9] 刘文亮,朱维红,陈涤,张泓泉. 基于雷达图像的运动目标形态检测及跟踪技术[J]. 山东大学学报(工学版), 2010, 40(3): 31 -36 .
[10] 杨发展1 ,艾兴1 ,赵军1 ,侯建锋2 . ZrO2含量对WC基复合材料的力学性能和微观结构的影响[J]. 山东大学学报(工学版), 2009, 39(1): 92 -95 .