Journal of Shandong University(Engineering Science) ›› 2020, Vol. 50 ›› Issue (3): 45-50.doi: 10.6040/j.issn.1672-3961.0.2019.306

• Machine Learning & Data Mining • Previous Articles     Next Articles

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)

RichHTML

7

PDF (PC)

364

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

CLC Number: 

  • TP30

Fig.1

Only one active precursor node"

Fig.2

IM-ACO algorithmic overall framework"

Table 1

Dataset information"

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

Fig.3

Convergence for the wiki_vote dataset algorithm"

Fig.4

Activation range comparison chart"

Fig.5

Comparison of diffusion steps for different diffusion ranges of NetHEPT"

Fig.6

Comparison of diffusion steps for different diffusion initial nodes of 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] Yun HU,Shu ZHANG,Hui LI,Kankan SHE,Jun SHI. Recommendation algorithm based on trust network reconfiguration [J]. Journal of Shandong University(Engineering Science), 2019, 49(2): 42-46.
[2] Yijiang HE,Junping DU,Feifei KOU,Meiyu LIANG,Wei WANG,Ang LUO. Images auto-encoding algorithm based on deep convolution neural network [J]. Journal of Shandong University(Engineering Science), 2019, 49(2): 61-66.
[3] CHEN Jiajie, WANG Jinfeng. Method for solving Choquet integral model based on ant colony algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 81-87.
[4] DU Xixi, LIU Huafeng, JING Liping. An additive co-clustering for recommendation of integrating social network [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 96-102.
[5] LI Shuo, SHI Yuliang. The method of spot cluster recommendation in location-based social networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(3): 44-50.
[6] WANG Qiming, LI Zhanguo, FAN Aiwan. Quantum ant colony algorithm based on the game theory [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(2): 33-36.
[7] HAN Zhongming, WU Yang, TAN Xusheng, LIU Wen, YANG Weijie. Comparison and analysis on measure indexes for structural hole nodes in social network [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(1): 1-8.
[8] LU Wenyang, XU Jiayi, YANG Yubin. LDA-based link prediction in social network [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(6): 26-31.
[9] ZENG Hua1, CUI Wen2, FU Lian-ning1, WU Yao-hua1*. Heuristic construction method for the initial tour of the Lin-Kernighan algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(2): 30-35.
[10] WU Ke-shou, CHEN Yu-ming, ZENG Zhi-qiang. Decision table reduction based on neighborhood relation [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(2): 7-10.
[11] CAI Rong-ying, WANG Li-jin, WU Chao, ZHONG Yi-wen*. A kind of iterative improvement based ant colony optimization algorithm for the traveling salesman problem [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(1): 6-11.
[12] LI Yu-jian, MENG Dong-xia*, GUI Zhi-ming. Fast computation of characteristic boundary points for improving geometric ensembles [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2011, 41(4): 56-60.
[13] LI Yong-sheng, QU Liang-dong, LI Xi. Adaptive pheromone updating ant colony algorithms for solving QoS multicast routing problems [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2011, 41(4): 38-43.
[14] XIA Hui1, WANG Hua1, CHEN Xi2. A kind of ant colony parameter adaptive optimization algorithm  based on particle swarm optimization thought [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(3): 26-30.
[15] SHA Lu1,2, BAO Pei-ming1,2*, LI Ni-ge1,2. The research of a clustering algorithm based on the ant colony system [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(3): 13-18.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] ZHANG Yong-hua,WANG An-ling,LIU Fu-ping . The reflected phase angle of low frequent inhomogeneous[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 22 -25 .
[2] LI Kan . Empolder and implement of the embedded weld control system[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(4): 37 -41 .
[3] SHI Lai-shun,WAN Zhong-yi . Synthesis and performance evaluation of a novel betaine-type asphalt emulsifier[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(4): 112 -115 .
[4] LI Liang, LUO Qiming, CHEN Enhong. Graph-based ranking model for object-level search
[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 15 -21 .
[5] WANG Bo,WANG Ning-sheng . Automatic generation and combinatory optimization of disassembly sequence for mechanical-electric assembly[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 52 -57 .
[6] LI Ke,LIU Chang-chun,LI Tong-lei . Medical registration approach using improved maximization of mutual information[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 107 -110 .
[7] JI Tao,GAO Xu/sup>,SUN Tong-jing,XUE Yong-duan/sup>,XU Bing-yin/sup> . Characteristic analysis of fault generated traveling waves in 10 Kv automatic blocking and continuous power transmission lines[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 111 -116 .
[8] QIN Tong, SUN Fengrong*, WANG Limei, WANG Qinghao, LI Xincai. 3D surface reconstruction using the shape based interpolation guided by maximal discs[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(3): 1 -5 .
[9] LIU Wen-liang, ZHU Wei-hong, CHEN Di, ZHANG Hong-quan. Detection and tracking of moving targets using the morphology match in radar images[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(3): 31 -36 .
[10] . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 92 -95 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd