计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (6): 1316-1326.DOI: 10.3778/j.issn.1673-9418.2011018
收稿日期:
2020-11-05
修回日期:
2021-01-11
出版日期:
2022-06-01
发布日期:
2021-01-28
通讯作者:
+ E-mail: yimuyunlang@sina.com作者简介:
杨书新(1978—),男,江西九江人,博士,副教授,硕士生导师,CCF会员,主要研究方向为社交网络分析、生物信息学等。基金资助:
YANG Shuxin1,+(), SONG Jianbin1, LIANG Wen2
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.Supported by:
摘要:
影响最大化问题是社交网络分析中的重要问题,社交网络结构的多样化不断给影响最大化问题注入活力,让它在近二十年里经久不衰,一直是学术界的热门问题。针对已有影响最大化问题的研究,主要关注节点的特征,较少从社交网络的连通性角度来看待影响最大化问题。而割点作为连通分量间的桥梁,是连通性的核心。为此,综合考虑社交网络的节点特征和连通性,提出了基于割点的启发式算法来求解影响最大化问题。该算法用度和连通分量评估节点的影响力,在一定程度上解决了影响力重叠的问题。基于传染病模型,在四个开源数据集上进行了相关实验。在算法对比实验中,基于割点的影响最大化算法在运行时间、影响传播范围和种子富集性指标中表现优异,验证了算法的实用性和有效性。
中图分类号:
杨书新, 宋建缤, 梁文. 基于割点的社交网络影响最大化问题[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.
| | | | | | | |
---|---|---|---|---|---|---|---|
1 | | 1 | 1 | 5 | | 6 | 3 |
2 | | 3 | 1 | 6 | | 5 | 3 |
3 | | 2 | 1 | 7 | | 4 | 3 |
4 | | 7 | 3 |
表1 图3(a)中各节点对应的 d f n和 l o w值
Table 1 dfn and low of nodes in Fig.3(a)
| | | | | | | |
---|---|---|---|---|---|---|---|
1 | | 1 | 1 | 5 | | 6 | 3 |
2 | | 3 | 1 | 6 | | 5 | 3 |
3 | | 2 | 1 | 7 | | 4 | 3 |
4 | | 7 | 3 |
数据集 | 节点数 | 边数 | 平均度 | 直径 | 聚类系数 |
---|---|---|---|---|---|
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 |
表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 |
参数 | 种子间边增加量 | 参数 | 种子间边增加量 |
---|---|---|---|
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 |
[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. |
[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. |
阅读次数 | ||||||||||||||||||||||||||||||||||||||||||||||||||
全文 95
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||
摘要 284
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||