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

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)

• 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]. 《计算机应用》唯一官方网站, 2024, 44(6): 1855-1861.
[2]	高瑞, 陈学斌, 张祖篡. 面向部分图更新的动态社交网络隐私发布方法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3831-3838.
[3]	刘世梁, 王义, 马应龙. 考虑社区规模不平衡的非重叠社区检测[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3396-3402.
[4]	李莉, 杨春艳, 朱江文, 胡荣磊. 区块链下社交网络用户抄袭识别方案[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 242-251.
[5]	郭新明, 刘蕊, 谢飞, 林德钰. 无线视频传感器网络β-QoM目标栅栏覆盖构建算法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2877-2884.
[6]	彭诗杰, 陈红梅, 王丽珍, 肖清. 基于地理偏好排序的兴趣点混合推荐模型[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2448-2455.
[7]	孙男男, 朴春慧, 马新娜. 基于社交关系和时序信息的团购推荐方法[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1719-1729.
[8]	高智慧, 韩萌, 刘淑娟, 李昂, 穆栋梁. 基于智能优化算法的高效用项集挖掘方法综述[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1676-1686.
[9]	杨煜, 段威威. 基于谱聚类的社交网络动态社区发现算法[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3129-3135.
[10]	肖智豪, 胡志华, 朱琳. 求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2926-2935.
[11]	张新明, 温少晨, 刘尚旺. 差分扰动的堆优化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2519-2527.
[12]	杨书新, 许景峰. 基于反向影响采样的积极影响力最大化[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2609-2616.
[13]	仇丽青, 曲福帅. 基于情感分析和影响力评估的突发事件情感图谱[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1330-1338.
[14]	吴晴晴, 周丽华, 寸轩懿, 杜国王, 姜懿庭. 异质信息网络中基于有向无环图的影响力最大化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 895-903.
[15]	解伟凡, 郭岩, 匡广生, 余智华, 薛源海, 沈华伟. 基于演化模式的推特话题流行度预测方法[J]. 《计算机应用》唯一官方网站, 2022, 42(11): 3364-3370.

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

Influence maximization algorithm based on node coverage and structural hole

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 19

相关文章 15

编辑推荐

Metrics