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

doi:10.3778/j.issn.1673-9418.2011018

计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (6): 1316-1326.DOI: 10.3778/j.issn.1673-9418.2011018

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

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

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

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

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)

摘要/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

中图分类号:

TP39

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

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.

图/表 11

图1 图的连通性示例

Fig.1 Example of graph connectivity

图2 信息传播对比（假设传播概率为1）

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

图3 CVIM流程图

Fig.3 Flow chart of CVIM

图4 割点求解实例

图4 Instance of getting cut-vertex

表1 图3（a）中各节点对应的 d f n和 l o w值

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

表1 图3（a）中各节点对应的 d f n和 l o w值

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

表2 实验数据集的基本信息

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

图5 参数 α对比

Fig.5 Comparison of parameter α

表3 anybeat数据集影响力重叠分析

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

表3 anybeat数据集影响力重叠分析

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

图6 运行时间对比

Fig.6 Comparison of running time

图7 影响传播范围对比

Fig.7 Comparison of influence spreading

图8 种子富集性对比

Fig.8 Comparison of seed enrichment

参考文献 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

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 20

相关文章 15

编辑推荐

Metrics

[1]	陈江美, 张文德. 基于位置社交网络的兴趣点推荐系统研究综述[J]. 计算机科学与探索, 2022, 16(7): 1462-1478.
[2]	端祥宇, 袁冠, 孟凡荣. 动态社区发现方法研究综述[J]. 计算机科学与探索, 2021, 15(4): 612-630.
[3]	高昂, 梁英, 谢小杰, 王梓森, 李锦涛. 支持隐私保护的社交网络信息传播方法[J]. 计算机科学与探索, 2021, 15(2): 233-248.
[4]	郭奕，徐亮，熊雪军. 社交网络中意见领袖挖掘方法综述[J]. 计算机科学与探索, 2021, 15(11): 2077-2092.
[5]	李娜，朱怀杰，刘威，印鉴. 基于位置的稀疏群体查询[J]. 计算机科学与探索, 2021, 15(11): 2151-2160.
[6]	李想，申德荣，冯朔，寇月，聂铁铮. 结合全局种子最优局部扩展的跨网络用户识别[J]. 计算机科学与探索, 2020, 14(6): 928-938.
[7]	张卜聆，王兴伟，李婕，易波，黄敏. 基于朋友圈和节点感知的内容中心MSN路由机制[J]. 计算机科学与探索, 2020, 14(1): 51-58.
[8]	王瑶，寇月，申德荣，聂铁铮，于戈. 元路径选择和矩阵分解的跨社交网络链路预测[J]. 计算机科学与探索, 2019, 13(9): 1459-1470.
[9]	江淼淼，孙更新，宾晟. 多关系社交网络中社团结构发现算法[J]. 计算机科学与探索, 2019, 13(7): 1134-1144.
[10]	寇晓宇，吕天舒，张岩. 结合深度学习的网络邻居结构研究及应用[J]. 计算机科学与探索, 2019, 13(2): 239-250.
[11]	宋雨萌，陈默，于戈. 时序地理社交网络中基于动态偏好的组查询[J]. 计算机科学与探索, 2019, 13(11): 1813-1828.
[12]	马宇红，赵媛媛，强亚蓉. 社交网络谣言传播的破窗效应和责任分散效应[J]. 计算机科学与探索, 2019, 13(10): 1702-1709.
[13]	时久超，刘冠峰，李直旭，刘安，郑凯. 社交网络中基于强社交图的可信任服务商选择[J]. 计算机科学与探索, 2018, 12(9): 1383-1396.
[14]	任思禹，申德荣，寇月，聂铁铮，于戈. 话题感知下的跨社交网络影响力最大化分析[J]. 计算机科学与探索, 2018, 12(5): 741-752.
[15]	郭宁宁，王宝亮，侯永宏，常鹏. 融合社交网络特征的协同过滤推荐算法[J]. 计算机科学与探索, 2018, 12(2): 208-217.