Cut-Vertex-Based Influence Maximization Problem in Social Network

doi:10.3778/j.issn.1673-9418.2011018

Journal of Frontiers of Computer Science and Technology ›› 2022, Vol. 16 ›› Issue (6): 1316-1326.DOI: 10.3778/j.issn.1673-9418.2011018

• Network and Information Security • Previous Articles Next Articles

Cut-Vertex-Based Influence Maximization Problem in Social Network

YANG Shuxin¹^,⁺(), SONG Jianbin¹, LIANG Wen²

1. School of Information Engineering, Jiangxi University of Science and Technology, Ganzhou, Jiangxi 341000, China
2. School of Computer Science and Technology, Changchun University of Science and Technology, Changchun 130000, China

Received:2020-11-05 Revised:2021-01-11 Online:2022-06-01 Published:2021-01-28
About author:YANG Shuxin, born in 1978, Ph.D., associate professor, M.S. supervisor, member of CCF. His research interests include social network analysis, bioinformatics, etc.
SONG Jianbin, born in 1994, M.S. candidate. His research interests include social network analysis, data mining, etc.
LIANG Wen, born in 1994, Ph.D. candidate, student member of CCF. His research interests include complex network dynamics, quantum informatics, etc.
Supported by:
National Natural Science Foundation of China(61662028);Scientific Technology Research Foundation of Education Department of Jiangxi Province(GJJ170518);Special Foundation of Postgraduate Innovation of Jiangxi Province(YC2018-S331)

基于割点的社交网络影响最大化问题

杨书新¹^,⁺(), 宋建缤¹, 梁文²

1. 江西理工大学信息工程学院,江西赣州 341000
2. 长春理工大学计算机科学技术学院,长春 130000

通讯作者: + E-mail: yimuyunlang@sina.com
作者简介:杨书新（1978—）,男,江西九江人,博士,副教授,硕士生导师,CCF会员,主要研究方向为社交网络分析、生物信息学等。
宋建缤（1994—）,男,江西吉安人,硕士研究生,主要研究方向为社交网络分析、数据挖掘等。
梁文（1994—）,男,吉林梅河口人,博士研究生,CCF学生会员,主要研究方向为复杂网络动力学、量子信息学等。
基金资助:
国家自然科学基金(61662028);江西省教育厅科学技术研究项目基金(GJJ170518);江西省研究生创新专项资金项目(YC2018-S331)

Abstract

Abstract:

Influence maximization problem is an important issue in social network analysis, the diversity of social network structure has continuously injected vitality into the influence maximization problem, which has been a hot issue in academic circles for nearly two decades. The research on the existing problem of influence maximization mainly focuses on the characteristics of the node, and rarely considers the influence maximization problem from the perspective of social networks connectivity. As a bridge between connected components, the cut-vertex is the core of connectivity. To this end, this paper comprehensively considers the characteristics of node and connectivity of social networks, and proposes a heuristic algorithm based on cut-vertex to solve the influence maximization problem. The algorithm uses degree and connected components to evaluate the influence of nodes, which solves the problem of overlapping influences to a certain extent. Based on the susceptible-infected-recovered model, this paper conducts related experiments on four open source datasets. In the algorithm comparison experiment, the influence maximization algorithm based on the cut-vertex performs well in terms of the running time, influence spread range and seed enrichment, which verifies the practicality and effectiveness of the algorithm.

Key words: social networks, cut-vertex, influence maximization

摘要：

影响最大化问题是社交网络分析中的重要问题,社交网络结构的多样化不断给影响最大化问题注入活力,让它在近二十年里经久不衰,一直是学术界的热门问题。针对已有影响最大化问题的研究,主要关注节点的特征,较少从社交网络的连通性角度来看待影响最大化问题。而割点作为连通分量间的桥梁,是连通性的核心。为此,综合考虑社交网络的节点特征和连通性,提出了基于割点的启发式算法来求解影响最大化问题。该算法用度和连通分量评估节点的影响力,在一定程度上解决了影响力重叠的问题。基于传染病模型,在四个开源数据集上进行了相关实验。在算法对比实验中,基于割点的影响最大化算法在运行时间、影响传播范围和种子富集性指标中表现优异,验证了算法的实用性和有效性。

关键词: 社交网络, 割点, 影响最大化

CLC Number:

TP39

YANG Shuxin, SONG Jianbin, LIANG Wen. Cut-Vertex-Based Influence Maximization Problem in Social Network[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(6): 1316-1326.

杨书新, 宋建缤, 梁文. 基于割点的社交网络影响最大化问题[J]. 计算机科学与探索, 2022, 16(6): 1316-1326.

Figures/Tables 11

Fig.1 Example of graph connectivity

Fig.2 Comparison of information spreading (Suppose probability of propagation is 1)

Fig.3 Flow chart of CVIM

图4 Instance of getting cut-vertex

Table 1 dfn and low of nodes in Fig.3(a)

$i$	$v e r t e x$	$d f n [i]$	$l o w [i]$	$i$	$v e r t e x$	$d f n [i]$	$l o w [i]$
1	$v 1$	1	1	5	$v 5$	6	3
2	$v 2$	3	1	6	$v 6$	5	3
3	$v 3$	2	1	7	$v 7$	4	3
4	$v 4$	7	3

Table 1 dfn and low of nodes in Fig.3(a)

$i$	$v e r t e x$	$d f n [i]$	$l o w [i]$	$i$	$v e r t e x$	$d f n [i]$	$l o w [i]$
1	$v 1$	1	1	5	$v 5$	6	3
2	$v 2$	3	1	6	$v 6$	5	3
3	$v 3$	2	1	7	$v 7$	4	3
4	$v 4$	7	3

Table 2 Basic information about experimental datasets

数据集	节点数	边数	平均度	直径	聚类系数
anybeat	12 645	67 053	10	3	0.227 469
brightkite	56 739	212 945	7	5	0.173 379
epinions	26 588	100 120	7	5	0.135 164
HepPh	11 204	117 619	19	4	0.611 483

Fig.5 Comparison of parameter α

Table 3 Influence overlap analysis of anybeat dataset

参数 $α$	种子间边增加量	参数 $α$	种子间边增加量
0.1	0	0.6	384
0.2	44	0.7	274
0.3	92	0.8	276
0.4	206	0.9	314
0.5	382	1.0	368

Table 3 Influence overlap analysis of anybeat dataset

参数 $α$	种子间边增加量	参数 $α$	种子间边增加量
0.1	0	0.6	384
0.2	44	0.7	274
0.3	92	0.8	276
0.4	206	0.9	314
0.5	382	1.0	368

Fig.6 Comparison of running time

Fig.7 Comparison of influence spreading

Fig.8 Comparison of seed enrichment

References 20

[1]	We Are Social, Hootsuite Inc. Digital 2020 global overview reports[EB/OL]. (2020-01-30) [2020-12-25]. https://wearesocial.com/blog/2020/01/digital-2020-3-8-billion-people-use-social-media .
[2]	郭静, 张鹏, 方滨兴, 等. 基于LT模型的个性化关键传播用户挖掘[J]. 计算机学报, 2014, 37(4): 809-818.
	GUO J, ZHANG P, FANG B X, et al. Personalized key propagating users mining based on LT model[J]. Chinese Journal of Computers, 2014, 37(4): 809-818.
[3]	杨书新, 王希, 彭秋英. 基于影响路径的个性化影响最大化算法[J]. 计算机工程与科学, 2016, 38(6): 1128-1134.
	YANG S X, WANG X, PENG Q Y. A personalized influence maximization algorithm based on influence path[J]. Computer Engineering and Science, 2016, 38(6): 1128-1134.
[4]	杨喜艳, 吴亚豪, 张家军. 多层网络中谣言传播的动态控制策略分析[J]. 电子科技大学学报, 2020, 49(4): 511-518.
	YANG X Y, WU Y H, ZHANG J J. Analysis of rumor spreading with a temporal control strategy in multiplex networks[J]. Journal of University of Electronic Science and Technology of China, 2020, 49(4): 511-518.
[5]	陈东明, 袁泽枝, 黄新宇, 等. 时态网络节点相似性度量及链路预测算法[J]. 东北大学学报(自然科学版), 2020, 41(1): 29-34.
	CHEN D M, YUAN Z Z, HUANG X Y, et al. Node similarity measurement and link prediction algorithm in temporal networks[J]. Journal of Northeastern University (Natural Science), 2020, 41(1): 29-34.
[6]	KEMPE D, KLEINBERG J, TARDOS É. Maximizing the spread of influence through a social network[C]// Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, Aug 24-27, 2003. New York: ACM, 2003: 137-146.
[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 Know- ledge Discovery and Data Mining, San Jose, Aug 12-15, 2007. New York: ACM, 2007: 420-429.
[8]	GOYAL A, LU W, LAKSHMANAN L V S. Celf++: optimizing the greedy algorithm for influence maximization in social networks[C]// Proceedings of the 20th International Conference Companion on World Wide Web, Hyderabad, Mar 28-Apr 1, 2011. New York: ACM, 2011: 47-48.
[9]	CHEN W, WANG Y, YANG S. Efficient influence maximization in social networks[C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, Jun 28-Jul 1, 2009. New York: ACM, 2009: 199-208.
[10]	CHEN W, WANG C, WANG Y. Scalable influence maxi-mization for prevalent viral marketing in large-scale social networks[C]// Proceedings of the 16th ACM SIGKDD Inter-national Conference on Knowledge Discovery and Data Mining, Washington, Jul 24-28, 2010. New York: ACM, 2010: 1029-1038.
[11]	IBNOULOUAFI A, EL HAZITI M. Density centrality: identifying influential nodes based on area density formula[J]. Chaos, Solitons & Fractals, 2018, 114: 69-80. DOI URL
[12]	DOMINGOS P, RICHARDSON M. Mining the network value of customers[C]// Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, Aug 26-29, 2001. New York: ACM, 2001: 57-66.
[13]	曹玖新, 闵绘宇, 徐顺, 等. 基于启发式和贪心策略的社交网络影响最大化算法[J]. 东南大学学报(自然科学版), 2016, 46(5): 950-956.
	CAO J X, MIN H Y, XU S, et al. Mixed heuristic and greedy strategies based algorithm for influence maximization in social networks[J]. Journal of Southeast University (Natural Science Edition), 2016, 46(5): 950-956.
[14]	ZAREIE A, SHEIKHAHMADI A, KHAMFOROOSH K. Influence maximization in social networks based on TOPSIS[J]. Expert Systems with Applications, 2018, 108: 96-107. DOI URL
[15]	YANG Y, YU L, WANG X, et al. A novel method to evaluate node importance in complex networks[J]. Physica A: Statistical Mechanics and Its Applications, 2019, 526: 121118. DOI URL
[16]	TIAN L, BASHAN A, SHI D N, et al. Articulation points in complex networks[J]. Nature Communications, 2017, 8: 14223. DOI URL
[17]	王立夫, 赵云康, 段乐, 等. 割点失效对复杂网络可控性的影响[J]. 控制与决策, 2019, 34(11): 2310-2316.
	WANG L F, ZHAO Y K, DUAN L, et al. Effect of cut vertexes-removal on controllability of complex networks[J]. Control and Decision, 2019, 34(11): 2310-2316.
[18]	CHEN D, LV L, SHANG M S, et al. Identifying influential nodes in complex networks[J]. Physica A: Statistical Mechanics and Its Applications, 2012, 391(4): 1777-1787. DOI URL
[19]	ZHOU S, MONDRAGON R J. The rich-club phenomenon in the internet topology[J]. IEEE Communications Letters, 2004, 8(3): 180-182. DOI URL
[20]	KHALIL E B, DILKINA B, SONG L. Scalable diffusion aware optimization of network topology[C]// Proceedings of the 20th ACM SIGKDD International Conference on Know-ledge Discovery and Data Mining, New York, Aug 24-27, 2014. New York: ACM, 2014: 1226-1235.

Cut-Vertex-Based Influence Maximization Problem in Social Network

基于割点的社交网络影响最大化问题

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 20

Related Articles 15

Recommended Articles

Metrics

[1]	CHEN Jiangmei, ZHANG Wende. Review of Point of Interest Recommendation Systems in Location-Based Social Networks [J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(7): 1462-1478.
[2]	GAO Ang, LIANG Ying, XIE Xiaojie, WANG Zisen, LI Jintao. Social Network Information Diffusion Method with Support of Privacy Protection [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(2): 233-248.
[3]	QIAN Fulan, XU Tao, ZHAO Shu, ZHANG Yanping. Local Probability Solution Based Immune Genetic Influence Maximization Algorithm [J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(5): 783-791.
[4]	WANG Yao, KOU Yue, SHEN Derong, NIE Tiezheng, YU Ge. Link Prediction Using Meta-Path Selection and Matrix Factorization Across Social Networks [J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(9): 1459-1470.
[5]	KOU Xiaoyu, LV Tianshu, ZHANG Yan. Research and Application of Network Neighborhood Structure Combined with Deep Learning [J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(2): 239-250.
[6]	LI Chunying, TANG Zhikang, TANG Yong, ZHAO Jiandong, HUANG Yonghang. Community Detection Algorithm with Local-First Approach in Social Networks [J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(8): 1263-1277.
[7]	REN Siyu, SHEN Derong, KOU Yue, NIE Tiezheng, YU Ge. Topic-Aware Influence Maximization Across Social Networks [J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(5): 741-752.
[8]	ZHANG Yunfei, LI Jin, YUE Kun, LUO Zhihao, LIU Weiyi. Influence Maximization Methods of Correlated Information Propagation [J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(12): 1891-1902.
[9]	HU Min, SUN Xinran, HUANG Hongcheng. Edge-Cover Algorithm for Influence Maximization in Social Network [J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(5): 720-731.
[10]	LIAN Xubao, LIN Hongfei, XU Bo, LIN Yuan. Rank-Oriented Social Recommendation Algorithm with Item Tag Information [J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(3): 373-381.
[11]	SONG Xiaoyu, WEI Haiyan, SUN Huanliang, XU Hongfei. Local Distributed Group Travel Route Search Based on Check-in Data [J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(5): 635-645.
[12]	XIE Shengnan, LIU Yong, ZHU Jinghua, TAN Long. Research on Topic-Based Local Influence Maximization Algorithm in Social Network [J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(5): 646-656.
[13]	ZHANG Ende, GAO Kening, ZHANG Yu, LI Feng. Community Discovery Algorithm Based on Combination of Users Generated Contents and Link Relationships [J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(2): 194-200.
[14]	YUAN Chengzhe, ZENG Biqing, TANG Yong, WANG Dahao, ZENG Huimin. Multi-Faceted Team Recommendation Model for Academic Social Networks [J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(2): 201-209.
[15]	ZHANG Caiping, ZHOU Lihua, CHEN Hongmei, RUAN Huifeng. Relation Context Oriented Approach to Predict Hiding Location of Criminals [J]. Journal of Frontiers of Computer Science and Technology, 2015, 9(8): 945-953.