基于社交网络的影响力最大化算法

王璿; 张瑜; 周军锋; 陈子阳

doi:10.11959/j.issn.1000-436x.2022152

您当前的位置：

首页 >

文章列表页 >

基于社交网络的影响力最大化算法

学术论文 | 更新时间：2024-06-05

- 基于社交网络的影响力最大化算法
- Influence maximization algorithm based on social network
- 通信学报 2022年43卷第8期页码：151-163
- 作者机构：
  
  1. 东华大学计算机科学与技术学院，上海201620
  2. 上海立信会计金融学院信息管理学院，上海 201620
- 作者简介：
  
  [ "王璿（1977- ），女，黑龙江齐齐哈尔人，博士，东华大学副教授，主要研究方向为数据查询、生物信息处理、分布式并行计算" ]
  [ "张瑜（1997- ），男，江苏泰州人，东华大学硕士生，主要研究方向为社交网络" ]
  [ "周军锋（1977- ），男，陕西西安人，博士，东华大学教授，主要研究方向为图数据的查询处理技术、推荐系统关键技术" ]
  [ "陈子阳（1973- ），男，黑龙江五常人，博士，上海立信会计金融学院教授，主要研究方向为数据库理论与技术" ]
- 基金信息：
  
  国家自然科学基金资助项目;The National Natural Science Foundation of China(61873337);上海自然科学基金资助项目;The Natural Science Foundation of Shanghai(20ZR1402700)
- DOI：10.11959/j.issn.1000-436x.2022152
  中图分类号： TP393
- 网络出版日期：2022-08，
  
  纸质出版日期：2022-08-25
- 稿件说明：
移动端阅览
王璿, 张瑜, 周军锋, 等. 基于社交网络的影响力最大化算法[J]. 通信学报, 2022,43(8):151-163.

Xuan WANG, Yu ZHANG, Junfeng ZHOU, et al. Influence maximization algorithm based on social network[J]. Journal on communications, 2022, 43(8): 151-163.
王璿, 张瑜, 周军锋, 等. 基于社交网络的影响力最大化算法[J]. 通信学报, 2022,43(8):151-163. DOI： 10.11959/j.issn.1000-436x.2022152.

Xuan WANG, Yu ZHANG, Junfeng ZHOU, et al. Influence maximization algorithm based on social network[J]. Journal on communications, 2022, 43(8): 151-163. DOI： 10.11959/j.issn.1000-436x.2022152.

摘要

影响力最大化问题研究在给定传播模型下如何选取社交网络中的一组种子用户，使信息通过这些用户实现最大范围的传播。现有算法主要存在2个问题：一是由于影响范围有限、时间复杂度高，难以适用于大规模社交网络；二是仅局限于特定传播模型，只能解决单一类型社交网络下的影响力最大化问题，当使用在不同类型社交网络上时效果较差。对此，基于2个经典影响力传播模型，结合反向影响采样技术，提出一种高效的影响力最大化（MTIM）算法。为验证MTIM算法的高效性，将其与IMM、TIM和PMC等贪心算法，以及OneHop和Degree D

iscount等启发式算法在4个真实社交网络上进行对比实验，结果表明MTIM算法能够提供

近似保证，显著扩大影响范围，并有效提高运行效率。

Abstract

The influence maximization (IM) problem asks for a group of seed users in a social network under a given propagation model

so that the information spread is maximized through these users.Existing algorithms have two main problems.Firstly

these algorithms were difficult to be applied in large-scale social networks due to limited expected influence and high time complexity.Secondly

these algorithms were limited to specific propagation models and could only solve the IM problem under a single type of social network.When they were used in different types of networks

the effect was poor.In this regard

an efficient algorithm (MTIM) based on two classic propagation models and reverse influence sampling (RIS) was proposed.To verify the effectiveness of MTIM

experiments were conducted to compare MTIM with greedy algorithms such as IMM

TIM and PMC

and heuristic algorithms such as OneHop and Degree Discount on four real social networks.The results show that MTIM can return a

approximate solution

effectively expand the expected influence and significantly improve the efficiency.

关键词

Keywords

references

KEMPE D , KLEINBERG J , TARDOS É , . Maximizing the spread of influence through a social network [C ] // Proceedings of the 9th ACM SIGKDD International Conference OnKnowledge Discovery and Data Mining . New York:ACM Press , 2003 : 137 - 146 .

LI Y C , FAN J , WANG Y H , et al . Influence maximization on social graphs:a survey [J ] . IEEE Transactions on Knowledge and Data Engineering , 2018 , 30 ( 10 ): 1852 - 1872 .

PENG H , HUANG K F , YANG L X , et al . Dynamic maintenance strategy for word-of-mouth marketing [J ] . IEEE Access , 2020 , 8 : 126496 - 126503 .

REN J F , LIU M T , LIU Y , et al . Optimal resource allocation with spatiotemporal transmission discovery for effective disease control [J ] . Infectious Diseases of Poverty , 2022 , 11 ( 1 ): 34 .

PAUL A , WU Z F , LIU K , et al . Personalized recommendation:from clothing to academic [J ] . Multimedia Tools and Applications , 2022 , 81 ( 10 ): 14573 - 14588 .

BINESH N , GHATEE M . Distance-aware optimization model for influential nodes identification in social networks with independent cascade diffusion [J ] . Information Sciences , 2021 , 581 : 88 - 105 .

BLESA M J , GARCÍA-RODRÍGUEZ P , SERNA M . Forward and backward linear threshold ranks [C ] // Proceedings of the 2021 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining . New York:ACM Press , 2021 : 265 - 269 .

ALI A , WANG H , KHAN A N . Mechanism to enhance team creative performance through social media:a transactive memory system approach [J ] . Computers in Human Behavior , 2018 , 91 : 115 - 126 .

BORGS C , BRAUTBAR M , CHAYES J , et al . Maximizing social influence in nearly optimal time [C ] // Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms . Philadelphia:Society for Industrial and Applied Mathematics , 2014 : 946 - 957 .

SUN L C , HUANG W R , YU P S , et al . Multi-round influence maximization [C ] // Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery ＆ Data Mining . New York:ACM Press , 2018 : 2249 - 2258 .

GUO J X , WU W L . Influence maximization:seeding based on community structure [J ] . ACM Transactions on Knowledge Discovery from Data (TKDD) , 2020 , 14 ( 6 ): 1 - 22 .

GUO Q T , WEI Z W , et al . Influence maximization revisited:efficient reverse reachable set generation with bound tightened [C ] // Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data . New York:ACM Press , 2020 : 2167 - 2181 .

ARORA A , GALHOTRA S , et al . Debunking the myths of influence maximization:an in-depth benchmarking study [C ] // Proceedings of the 2017 ACM International Conference on Management of Data . New York:ACM Press , 2017 : 651 - 666 .

TANG Y Z , XIAO X K , et al . Influence maximization:near-optimal time complexity meets practical efficiency [C ] // Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data . New York:ACM Press , 2014 : 75 - 86 .

TANG Y Z , SHI Y C , XIAO X K . Influence maximization in near-linear time:a martingale approach [C ] // Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data . New York:ACM Press , 2015 : 1539 - 1554 .

TAKAI Y , MIYAUCHI A , IKEDA M , et al . Hypergraph clustering based on PageRank [C ] // Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery ＆ Data Mining . New York:ACM Press , 2020 : 1970 - 1978 .

TANG J , TANG X Y , et al . Online processing algorithms for influence maximization [C ] // Proceedings of the 2018 International Conference on Management of Data . New York:ACM Press , 2018 : 991 - 1005 .

TANG J , TANG X Y , YUAN J S . An efficient and effective hop-based approach for influence maximization in social networks [J ] . Social Network Analysis and Mining , 2018 , 8 ( 1 ): 1 - 19 .

OHSAKA N , AKIBA T , YOSHIDA Y , et al . Fast and accurate influence maximization on large networks with pruned Monte-Carlo simulations [J ] . Proceedings of the AAAI Conference on Artificial Intelligence , 2014 , 28 ( 1 ): 138 - 144 .

CHEN W , WANG Y J , YANG S Y . Efficient influence maximization in social networks [C ] // Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . New York:ACM Press , 2009 : 199 - 208 .

浏览量

546

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于模体结构和度信息的关键节点组识别

大规模时序图中种子节点挖掘算法研究

基于子图演化与改进蚁群优化算法的社交网络链路预测方法

大数据环境下差分隐私保护技术及应用

融合高阶信息的社交网络重要节点识别算法