Influence maximization algorithm based on social network

Xuan WANG; Yu ZHANG; Junfeng ZHOU; Ziyang CHEN

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

您当前的位置：

首页 >

文章列表页 >

Influence maximization algorithm based on social network

Papers | 更新时间：2024-06-05

- Influence maximization algorithm based on social network
- Journal on Communications Vol. 43, Issue 8, Pages: 151-163(2022)
- 作者机构：
  
  1. 东华大学计算机科学与技术学院，上海201620
  2. 上海立信会计金融学院信息管理学院，上海 201620
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.1000-436x.2022152
  CLC： TP393
- Online First：2022-08，
  
  Published：25 August 2022
- 稿件说明：
移动端阅览
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：

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 .

Views

1411

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Identification of key node groups based on motif structure and degree information

Research on seed node mining algorithm in large-scale temporal graph

Social network link prediction method based on subgraph evolution and improved ant colony optimization algorithm

Differential privacy protection technology and its application in big data environment

Identifying vital nodes algorithm in social networks fusing higher-order information

Related Author

Liao ZHANG

Hailong YU

Li WANG

Yunyun YANG

Xiaohong ZOU

Chengwei XU

Jing CHEN

Biao SONG

Related Institution

School of Electrical and Power Engineering, Taiyuan University of Technology

School of Information Science and Engineering, Yanshan University

Hebei Key Laboratory of Computer Virtual Technology and System Integration

School of Management Science ＆Engineering, Zhejiang Gongshang University

Business School, University of Nottingham Ningbo

AI问答

⁰