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

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

Abstract

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

CLC Number:

TP393

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

Figures/Tables 12

符号	含义
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(?)	出邻居集合

数据集	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

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

Metrics

Recommended 0

No Suggested Reading articles found!

数据集	\|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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 20

Related Articles 15

Metrics

Recommended 0

[1]	Xiaohong ZOU, Chengwei XU, Jing CHEN, Biao SONG, Mingyue WANG. Research on seed node mining algorithm in large-scale temporal graph [J]. Journal on Communications, 2022, 43(9): 157-168.
[2]	Hongwei GUO, Ce ZHU, Xu YANG, Lei LUO. Temporal dependent rate-distortion optimization based on distortion backward propagation [J]. Journal on Communications, 2022, 43(12): 222-232.
[3]	Tao PENG, Wentao ZHONG, Guojun WANG, Entao LUO, Jinbo XIONG, Yining LIU, Wang Hao. Privacy-preserving precise profile matching in mobile social network [J]. Journal on Communications, 2022, 43(11): 90-103.
[4]	Zhen LIU,Na’na WANG,Xiaodong WANG,Yongqi SUN. Spectral clustering and embedding-enhanced POI recommendation in location-based social network [J]. Journal on Communications, 2020, 41(3): 197-206.
[5]	Qiuyang GU, Chunhua JU, Gongxing WU. Social network link prediction method based on subgraph evolution and improved ant colony optimization algorithm [J]. Journal on Communications, 2020, 41(12): 21-35.
[6]	Jing CHEN,Ziyi QI. Research on social network influence maximization algorithm based on time sequential relationship [J]. Journal on Communications, 2020, 41(10): 211-221.
[7]	Junlei BI,Zhiyuan LI. Time-variant interest community based query message routing algorithm in opportunity social network [J]. Journal on Communications, 2019, 40(9): 86-94.
[8]	Fenghua LI,Zhe SUN,Ben NIU,Jin CAO,Hui LI. Privacy-preserving photo sharing framework cross different social network [J]. Journal on Communications, 2019, 40(7): 1-13.
[9]	Haiping HUANG,Kai WANG,Xiong TANG,Dongjun ZHANG. Differential privacy protection scheme based on edge betweenness model [J]. Journal on Communications, 2019, 40(5): 88-97.
[10]	Zheng HU,Baodan CHEN,Jia REN,Yupei FAN,Lian WANG. Research on sea surface NB-IoT coverage based on improved SPM [J]. Journal on Communications, 2019, 40(4): 21-32.
[11]	Xiaomeng WANG, Binxing FANG, Hongli ZHANG, Xing WANG. TSL:predicting popularity of Facebook content based on tie strength [J]. Journal on Communications, 2019, 40(10): 1-9.
[12]	Guanghui YAN, Meng ZHANG, Hao LUO, Shikui LI, Ting LIU. Identifying vital nodes algorithm in social networks fusing higher-order information [J]. Journal on Communications, 2019, 40(10): 109-118.
[13]	Yu FU, Yihan YU, Xiaoping WU. Differential privacy protection technology and its application in big data environment [J]. Journal on Communications, 2019, 40(10): 157-168.
[14]	Yancui SHI,Yuan WANG,Qing ZHAO,Xiankun ZHANG. Research status of community detection based on local expansion [J]. Journal on Communications, 2019, 40(1): 149-162.
[15]	Lu DENG,Yan JIA,Binxing FANG,Bin ZHOU,Tao ZHANG,Xin LIU. Performance analysis of topic detection algorithms in distributed environment [J]. Journal on Communications, 2018, 39(8): 176-184.