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

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

通信学报 ›› 2022, Vol. 43 ›› Issue (8): 151-163.doi: 10.11959/j.issn.1000-436x.2022152

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

王璿¹, 张瑜¹, 周军锋¹, 陈子阳¹^,²

¹ 东华大学计算机科学与技术学院，上海201620
² 上海立信会计金融学院信息管理学院，上海 201620

修回日期:2022-07-27 出版日期:2022-08-25 发布日期:2022-08-01
作者简介:王璿（1977- ），女，黑龙江齐齐哈尔人，博士，东华大学副教授，主要研究方向为数据查询、生物信息处理、分布式并行计算
张瑜（1997- ），男，江苏泰州人，东华大学硕士生，主要研究方向为社交网络
周军锋（1977- ），男，陕西西安人，博士，东华大学教授，主要研究方向为图数据的查询处理技术、推荐系统关键技术
陈子阳（1973- ），男，黑龙江五常人，博士，上海立信会计金融学院教授，主要研究方向为数据库理论与技术
基金资助:
国家自然科学基金资助项目(61873337);上海自然科学基金资助项目(20ZR1402700)

Influence maximization algorithm based on social network

Xuan WANG¹, Yu ZHANG¹, Junfeng ZHOU¹, Ziyang CHEN¹^,²

¹ School of Computer Science and Technology, Donghua University, Shanghai 201620, China
² School of Information Management, Shanghai Lixin University of Accounting and Finance, Shanghai 201620, China

Revised:2022-07-27 Online:2022-08-25 Published:2022-08-01
Supported by:
The National Natural Science Foundation of China(61873337);The Natural Science Foundation of Shanghai(20ZR1402700)

摘要/Abstract

摘要：

影响力最大化问题研究在给定传播模型下如何选取社交网络中的一组种子用户，使信息通过这些用户实现最大范围的传播。现有算法主要存在2个问题：一是由于影响范围有限、时间复杂度高，难以适用于大规模社交网络；二是仅局限于特定传播模型，只能解决单一类型社交网络下的影响力最大化问题，当使用在不同类型社交网络上时效果较差。对此，基于2个经典影响力传播模型，结合反向影响采样技术，提出一种高效的影响力最大化（MTIM）算法。为验证MTIM算法的高效性，将其与IMM、TIM和PMC等贪心算法，以及OneHop和Degree Discount等启发式算法在4个真实社交网络上进行对比实验，结果表明MTIM算法能够提供 $(1 - \frac{1}{e} - ε)$ 近似保证，显著扩大影响范围，并有效提高运行效率。

关键词: 社交网络, 影响力最大化, 种子集, 传播模型

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 $(1 - \frac{1}{e} - ε)$ approximate solution, effectively expand the expected influence and significantly improve the efficiency.

Key words: social network, influence maximization, seed set, propagation model

中图分类号:

TP393

王璿, 张瑜, 周军锋, 陈子阳. 基于社交网络的影响力最大化算法[J]. 通信学报, 2022, 43(8): 151-163.

Xuan WANG, Yu ZHANG, Junfeng ZHOU, Ziyang CHEN. Influence maximization algorithm based on social network[J]. Journal on Communications, 2022, 43(8): 151-163.

图/表 12

表1

常用符号设置"

符号	含义
G= (V,E,W)	社交网络
n ,m	$n = \| V \|, m = \| E \|$
R	反向可达集
$R$	反向可达集的集合，例如 $R = {R_{1}, R_{2}, \dots}$
$Λ_{R} (S)$	集合S 在 $R$ 中的覆盖范围
$σ (S)$	集合S 的预期影响范围
$F_{R} (S)$	集合S 对 $R$ 的覆盖率
OPT	任意k个种子的最大影响范围
$E [\cdot]$	随机变量的期望值
lv	被链接程度
In(?)	入邻居集合
Out(?)	出邻居集合

表1

图1

图2

图3

表2

表3

不同筛选比例r%下的筛选节点个数和筛选时间比较"

数据集	r=60		r=70		r=80		r=90
数据集	$\| C \|$	时间/s	$\| C \|$	时间/s	$\| C \|$	时间/s	$\| C \|$	时间/s
Slashdot	59 755	4.029	69 105	4.404	75 860	5.097	77 315	10.751
soc-LiveMocha	81 506	5.299	89 459	5.549	96 683	6.253	103 164	9.368
Web-BerkStan	590 801	14.121	632 038	14.642	650 509	15.757	668 825	20.728
soc-pokec	1 178 735	30.886	1 301 817	32.184	1 476 290	37.013	1 632 804	49.413

表3

图4

图5

图6

图7

图8

图9

参考文献 20

[1]	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.
[2]	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.
[3]	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.
[4]	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.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	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.
[12]	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.
[13]	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.
[14]	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.
[15]	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.
[16]	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.
[17]	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.
[18]	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.
[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.
[20]	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.

数据集	\|V\|	\|E\|	Avg.deg
Slashdot	77 360	905 468	11.7
soc-LiveMocha	104 103	2 193 083	21.7
Web-BerkStan	685 230	7 600 595	11.1
soc-pokec	1 632 804	22 301 964	13.7

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

Influence maximization algorithm based on social network

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 20

相关文章 15

Metrics

推荐阅读 0

[1]	邹晓红, 许成伟, 陈晶, 宋彪, 王明月. 大规模时序图中种子节点挖掘算法研究[J]. 通信学报, 2022, 43(9): 157-168.
[2]	郭红伟, 朱策, 杨栩, 罗雷. 基于失真反向传播的时域依赖率失真优化[J]. 通信学报, 2022, 43(12): 222-232.
[3]	彭滔, 钟文韬, 王国军, 罗恩韬, 熊金波, 刘忆宁, Hao Wang. 移动社交网络中面向隐私保护的精确好友匹配[J]. 通信学报, 2022, 43(11): 90-103.
[4]	顾秋阳, 吴宝, 孙兆洋, 池仁勇. 基于改进灰狼优化的复杂网络重要节点识别算法[J]. 通信学报, 2021, 42(6): 72-83.
[5]	刘真,王娜娜,王晓东,孙永奇. 位置社交网络中谱嵌入增强的兴趣点推荐算法[J]. 通信学报, 2020, 41(3): 197-206.
[6]	顾秋阳, 琚春华, 吴功兴. 基于子图演化与改进蚁群优化算法的社交网络链路预测方法[J]. 通信学报, 2020, 41(12): 21-35.
[7]	陈晶,祁子怡. 基于时序关系的社交网络影响最大化算法研究[J]. 通信学报, 2020, 41(10): 211-221.
[8]	毕俊蕾,李致远. 机会社交网络中基于时变兴趣社区的查询消息路由算法[J]. 通信学报, 2019, 40(9): 86-94.
[9]	李凤华,孙哲,牛犇,曹进,李晖. 跨社交网络的隐私图片分享框架[J]. 通信学报, 2019, 40(7): 1-13.
[10]	黄海平,王凯,汤雄,张东军. 基于边介数模型的差分隐私保护方案[J]. 通信学报, 2019, 40(5): 88-97.
[11]	胡正,陈褒丹,任佳,樊雨沛,汪炼. 基于改进SPM的海上NB-IoT覆盖研究[J]. 通信学报, 2019, 40(4): 21-32.
[12]	王晓萌, 方滨兴, 张宏莉, 王星. TSL：基于连接强度的Facebook消息流行度预测模型[J]. 通信学报, 2019, 40(10): 1-9.
[13]	闫光辉, 张萌, 罗浩, 李世魁, 刘婷. 融合高阶信息的社交网络重要节点识别算法[J]. 通信学报, 2019, 40(10): 109-118.
[14]	付钰, 俞艺涵, 吴晓平. 大数据环境下差分隐私保护技术及应用[J]. 通信学报, 2019, 40(10): 157-168.
[15]	邓璐,贾焰,方滨兴,周斌,张涛,刘心. 分布式环境下话题发现算法性能分析[J]. 通信学报, 2018, 39(8): 176-184.