山东大学学报 (工学版) ›› 2020, Vol. 50 ›› Issue (3): 45-50.doi: 10.6040/j.issn.1672-3961.0.2019.306
Jun QIN1(),Weidong LI1,Jinli YI1,Jing LIU1,Maode MA2
摘要:
针对如何利用社会个体之间的影响力来扩大信息扩散的范围,即社会网络的影响最大化问题,提出一种新颖的基于蚁群优化算法的解决方案。利用2个启发式信息来度量节点影响力:优先选择更不容易被前驱节点激活的节点;考虑后继尤其是多级后继节点对未来扩散的影响。通过节点影响力选择出能扩散最大范围的初始节点集合。试验结果表明,相较于贪心算法以及传统的蚁群算法初始节点的扩散范围增加了150个节点,效率提高了25%,本研究方法很好的改善了初始节点选择容易陷入局部最优的问题。
中图分类号:
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 . |
|