融合节点覆盖范围和结构洞的影响力最大化算法

doi:10.11772/j.issn.1001-9081.2021071256

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (4): 1155-1161.DOI: 10.11772/j.issn.1001-9081.2021071256

• CCF第36届中国计算机应用大会 (CCF NCCA 2021) • 上一篇

融合节点覆盖范围和结构洞的影响力最大化算法

杨杰, 张名扬, 芮晓彬(), 王志晓

中国矿业大学计算机科学与技术学院，江苏徐州 221116

收稿日期:2021-07-16 修回日期:2021-08-19 接受日期:2021-08-24 发布日期:2021-08-19 出版日期:2022-04-10
通讯作者: 芮晓彬
作者简介:杨杰（1997—），女，山东烟台人，硕士研究生，CCF会员，主要研究方向：社交网络分析、影响力最大化
张名扬（1996—），男，江苏徐州人，硕士，CCF会员，主要研究方向：社交网络分析、影响力计算
王志晓（1979—），男，河南平顶山人，教授，博士，CCF会员，主要研究方向：社交网络分析、社会计算、图理论、图数据挖掘。
基金资助:
国家自然科学基金资助项目(61876186)

Influence maximization algorithm based on node coverage and structural hole

Jie YANG, Mingyang ZHANG, Xiaobin RUI(), Zhixiao WANG

School of Computer Science and Technology，China University of Mining and Technology，Xuzhou Jiangsu 221116，China

Received:2021-07-16 Revised:2021-08-19 Accepted:2021-08-24 Online:2021-08-19 Published:2022-04-10
Contact: Xiaobin RUI
About author:YANG Jie， born in 1997， M. S. candidate. Her research interests include social network analysis， influence maximization.
ZHANG Mingyang， born in 1996， M. S. His research interests include social network analysis， influence computing.
WANG Zhixiao， born in 1979， Ph.D.， professor. His research interests include social network analysis， social computing， graph theory， graph data mining.
Supported by:
National Natural Science Foundation of China(61876186)

摘要/Abstract

摘要：

影响力最大化是社交网络分析中的一个重要问题，旨在挖掘可以使得信息在网络中传播范围最大化的一小组节点（通常称为种子节点）。基于网络拓扑结构的启发式影响力最大化算法通常仅考虑某单一的网络中心性，没有综合考虑节点特性和网络拓扑结构，导致其效果受网络结构的影响较大。为了解决上述问题，提出了一种融合覆盖范围和结构洞的影响力最大化算法NCSH。该算法首先计算所有节点的覆盖范围和网格约束系数；然后通过覆盖范围增益最大原则选择种子节点；其次，若存在多个节点增益相同，则按照网格约束系数最小原则选取；最后，重复上述步骤直至选出所有种子节点。NCSH在不同种子数量和不同传播概率条件下，在六个真实网络数据集上均保持着优异的效果，在影响力传播范围方面，比同类的基于节点覆盖范围的算法（NCA）平均提高了3.8%；在时间消耗方面，比同类的基于结构洞和度折扣的最大化算法（SHDD）减少了43%。实验结果表明，NCSH能有效解决影响力最大化问题。

关键词: 社交网络, 影响力最大化, 节点覆盖范围, 结构洞, 启发式算法

Abstract:

Influence maximization is one of the important issues in social network analysis， which aims to identify a small group of seed nodes. When these nodes act as initial spreaders， information can be spread to the remaining nodes as much as possible in the network. The existing heuristic algorithms based on network topology usually only consider one single network centrality， failing to comprehensively combine node characteristics and network topology； thus， their performance is unstable and can be easily affected by the network structure. To solve the above problem， an influence maximization algorithm based on Node Coverage and Structural Hole （NCSH） was proposed. Firstly， the coverages and grid constraint coefficients of all nodes were calculated. Then the seed was selected according to the principle of maximum coverage gain. Secondly， if there were multiple nodes with the same gain， the seed was selected according to the principle of minimum grid constraint coefficient. Finally， the above steps were performed repeatedly until all seeds were selected. The proposed NCSH maintains good performance on six real networks under different numbers of seeds and different spreading probabilities. NCSH achieves 3.8% higher node coverage than to the similar NCA （Node Coverage Algorithm） on average， and 43% lower time consumption than the similar SHDD （maximization algorithm based on Structure Hole and DegreeDiscount）. The experimental results show that the NCSH can effectively solve the problem of influence maximization.

Key words: social network, influence maximization, node coverage, structural hole, heuristic algorithm

中图分类号:

TP301.6

杨杰, 张名扬, 芮晓彬, 王志晓. 融合节点覆盖范围和结构洞的影响力最大化算法[J]. 计算机应用, 2022, 42(4): 1155-1161.

Jie YANG, Mingyang ZHANG, Xiaobin RUI, Zhixiao WANG. Influence maximization algorithm based on node coverage and structural hole[J]. Journal of Computer Applications, 2022, 42(4): 1155-1161.

图/表 7

图1 节点结构洞特性

Fig. 1 Node structure hole characteristics

图2 约束系数计算

Fig. 2 Constraint coefficient calculating

图3 NCSH执行过程

Fig. 3 Execution process of NCSH

表1 实验数据集

Tab. 1 Datasets for experiments

名称	节点数	边数	平均度	$p c$
Butterfly	832	4 153	9.98	0.07
Facebook	4 039	88 234	43.69	0.01
Power	4 941	6 594	2.67	0.25
CaGrQc	5 242	14 490	5.53	0.06
CaHepTh	9 877	25 986	5.26	0.08
NetHept	15 233	62 796	4.12	0.10

表1 实验数据集

Tab. 1 Datasets for experiments

名称	节点数	边数	平均度	$p c$
Butterfly	832	4 153	9.98	0.07
Facebook	4 039	88 234	43.69	0.01
Power	4 941	6 594	2.67	0.25
CaGrQc	5 242	14 490	5.53	0.06
CaHepTh	9 877	25 986	5.26	0.08
NetHept	15 233	62 796	4.12	0.10

图4 不同算法在六个真实网络中的影响范围

Fig. 4 Influence spread of different algorithms on six real networks

图5 不同算法在六个真实网络中不同p值下的影响范围

Fig. 5 Influence spread of different algorithms under different p values in six real-world networks

图6 不同算法在两个真实网络中的运行时间

Fig. 6 Running time of different algorithms on two real networks

参考文献 19

1	PENG S C， ZHOU Y M， CAO L H， et al. Influence analysis in social networks： a survey［J］. Journal of Network and Computer Applications， 2018， 106：17-32. 10.1016/j.jnca.2018.01.005
2	吴安彪，袁野，乔百友，等.大规模时序图影响力最大化的算法研究［J］.计算机学报，2019，42（12）：2647-2664. 10.11897/SP.J.1016.2019.02647
	WU A B， YUAN Y， QIAO B Y， et al. The influence maximization problem based on large-scale temporal graph［J］. Chinese Journal of Computers， 2019， 42（12）： 2647-2664. 10.11897/SP.J.1016.2019.02647
3	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. New York： ACM， 2001： 57–66. 10.1145/502512.502525
4	陈卫.社交网络影响力传播研究［J］.大数据，2015，1（3）：82-98.
	CHEN W. Research on the influence of social networks［J］. Big Data， 2015， 1（3）： 82-98.
5	KEMPE D， KLEINBERG J， TARDOS É. Maximizing the spread of influence through a social network［C］// Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2003： 137-146. 10.1145/956750.956769
6	LESKOVEC J， KRAUSE A， GUESTRIN C， et al. Cost-effective outbreak detection in networks［C］// Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2007： 420-429. 10.1145/1281192.1281239
7	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， 2009： 199-208. 10.1145/1557019.1557047
8	NGUYEN D， NGUYEN T， DO T， et al. Probability-based multi-hop diffusion method for influence maximization in social networks［J］. Wireless Personal Communications， 2017， 93： 903-916. 10.1007/s11277-016-3939-8
9	高菊远，王志晓，芮晓彬，等.基于节点覆盖范围的影响力最大化算法［J］.计算机工程与设计，2019，40（8）：2211-2215，2246.
	GAO J Y， WANG Z X， RUI X B， et al. Influence maximization algorithm based on node coverage［J］. Computer Engineering and Design， 2019， 40（8）： 2211-2215，2246.
10	WANG Z X， SUN C C， XI J K， et al. Influence maximization in social graphs based on community structure and node coverage gain［J］. Future Generation Computer Systems， 2021， 118： 327-338. 10.1016/j.future.2021.01.025
11	苏晓萍，宋玉蓉.利用邻域“结构洞”寻找社会网络中最具影响力节点［J］.物理学报，2015，64（2）：5-15. 10.7498/aps.64.020101
	SU X P， SONG Y R. Using neighborhood "structure holes" to find the most influential nodes in social networks［J］. Acta Physica Sinica， 2015， 64（2）： 5-15. 10.7498/aps.64.020101
12	LOU T C， TANG J. Mining structural hole spanners through information diffusion in social networks［C］// Proceedings of the 22nd International Conference on World Wide Web. New York： ACM， 2013： 825-836. 10.1145/2488388.2488461
13	DONG S. Improved label propagation algorithm for overlapping community detection［J］. Computing， 2020， 102： 2185-2198. 10.1007/s00607-020-00836-3
14	MCAULEY J， LESKOVEC J. Learning to discover social circles in ego networks［C］// Proceedings of the 25th International Conference on Neural Information Processing Systems. Cambridge： MIT Press， 2012： 539-547. 10.1109/icdm.2012.110
15	WANG B， POURSHAFEIE A， ZITNIK M， et al. Network enhancement as a general method to denoise weighted biological networks［J］. Nature Communications， 2018， 9（1）：3108. 10.1038/s41467-018-05469-x
16	ROSSI R A， AHMED N K. The network data repository with interactive graph analytics and visualization ［C］// Proceedings of the 29th AAAI Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2015： 4292-4293.
17	LESKOVEC J， KLEINBERG J， FALOUTSOS C. Graph evolution： densification and shrinking diameters［J］. ACM Transactions on Knowledge Discovery from Data， 2007， 1（1）：pp 2-es. 10.1145/1217299.1217301
18	YANG J， LESKOVEC J. Defining and evaluating network communities based on ground-truth［J］. Knowledge and Information Systems， 2015， 42： 181-213. 10.1007/s10115-013-0693-z
19	李敏佳，许国艳，朱帅，等.基于结构洞和度折扣的影响力最大化算法［J］. 计算机应用， 2018， 38（12）：3419– 3424. 10.11772/j.issn.1001-9081.2018040920
	LI M J， XU G Y， ZHU S， et al. Influence maximization algorithm based on structural hole and degree discount［J］. Journal of Computer Applications， 2018， 38（12）：3419-3424. 10.11772/j.issn.1001-9081.2018040920

[1]	吴晴晴, 周丽华, 寸轩懿, 杜国王, 姜懿庭. 异质信息网络中基于有向无环图的影响力最大化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 895-903.
[2]	李美子, 米一菲, 张倩, 张波. 社交网络中基于K核分解的意见领袖识别算法[J]. 《计算机应用》唯一官方网站, 2022, 42(1): 26-35.
[3]	张萌, 李维华. 用户互动表示下的影响力最大化算法[J]. 计算机应用, 2021, 41(7): 1964-1969.
[4]	韦铭燕, 陈彧, 张亮. 针对混合变量优化问题的协同进化蚁群优化算法[J]. 计算机应用, 2021, 41(5): 1412-1418.
[5]	孙鹤立, 徐统, 何亮, 贾晓琳. 融合用户历史行为与社交关系的个性化社交事件推荐方法[J]. 计算机应用, 2021, 41(2): 324-329.
[6]	赵旭剑, 王崇伟. 基于图卷积网络的微博新闻故事线抽取方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3139-3144.
[7]	李翔锟, 贾彩燕. 融合重叠社区正则化及隐式反馈的协同过滤方法[J]. 计算机应用, 2021, 41(1): 53-59.
[8]	盛俊, 李斌, 陈崚. 基于模块度和标签传递的推荐算法[J]. 计算机应用, 2020, 40(9): 2606-2612.
[9]	李春英, 汤庸, 肖政宏, 李天送. 学术社交网络中的权威学者推荐模型[J]. 计算机应用, 2020, 40(9): 2594-2599.
[10]	杨书新, 梁文, 朱凯丽. 社交网络中对立影响最大化算法[J]. 计算机应用, 2020, 40(7): 1944-1949.
[11]	易东义, 邓根强, 董超雄, 祝苗苗, 吕周平, 朱岁松. 基于图卷积神经网络的医保欺诈检测算法[J]. 计算机应用, 2020, 40(5): 1272-1277.
[12]	冯丽萍, 韩琦, 周志刚, 白增亮. 社交网络影响的不良信息扩散建模及最优控制策略[J]. 计算机应用, 2020, 40(3): 735-739.
[13]	单晓欢, 张志国, 宋宝燕, 任成林. 事件社交网中基于有向标签图及用户反馈的活动推荐方法[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 448-453.
[14]	何昊晨, 张丹红. 基于多维社交关系嵌入的深层图神经网络推荐方法[J]. 计算机应用, 2020, 40(10): 2795-2803.
[15]	孙鹤立, 何亮, 何方, 孙苗苗, 贾晓琳. 基于网络嵌入的稀疏子图发现算法[J]. 计算机应用, 2020, 40(10): 2929-2935.

融合节点覆盖范围和结构洞的影响力最大化算法

Influence maximization algorithm based on node coverage and structural hole

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 19

相关文章 15

编辑推荐

Metrics