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

doi:10.6040/j.issn.1672-3961.0.2019.306

摘要/Abstract

摘要：

针对如何利用社会个体之间的影响力来扩大信息扩散的范围,即社会网络的影响最大化问题,提出一种新颖的基于蚁群优化算法的解决方案。利用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

覃俊,李蔚栋,易金莉,刘晶,马懋德. 基于双重启发式信息求解影响最大化问题的蚁群算法[J]. 山东大学学报 (工学版), 2020, 50(3): 45-50.

Jun QIN,Weidong LI,Jinli YI,Jing LIU,Maode MA. Ant colony optimization for solving maximization problem based ondouble heuristic information[J]. Journal of Shandong University(Engineering Science), 2020, 50(3): 45-50.

图/表 7

图1

图2

表1

图3

图4

图5

图6

参考文献 16

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.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

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

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