Weighted Network Structural Hole Node Discovery Algorithm for Multi-Dimensional Attribute Fusion

doi:10.3969/j.issn.1671-1122.2024.08.012

Abstract

Abstract:

In large-scale complex network spaces, quickly identifying structural hole nodes is of great significance for controlling the spread of viruses and public opinion. Aiming at the problem that the existing methods for identifying structural hole nodes have low recognition accuracy when the network structure changes, this paper proposed a structural hole node recognition algorithm. The algorithm combined adjacency information entropy and adjacency centrality based on multi-dimensional attribute mapping and fusion. The algorithm used weighted adjacency information entropy as the amount of information of neighbor nodes, used adjacency centrality to measure the importance of a node in propagating information about its neighbor nodes, and identified key structural hole nodes in the network by representing the local attributes of structural hole nodes as the ability of nodes to propagate information. Experimental results show that, compared with existing methods, under datasets with different network scales and network structures, the total scores of the three evaluation indicators of ξ, τ and network average information entropy are 0.470, 1.679, and 4.027, respectively, which are all optimal. It shows that the algorithm has more superior and stable performance. Moreover, the algorithm still has a low time cost when applied to large-scale networks.

Key words: structural hole, multi-dimensional attribute fusion, information dissemination capabilities, adjacency information entropy, adjacency centrality

CLC Number:

TP309

WANG Wentao, LIU Yanfei, MAO Bowen, YU Chengbo. Weighted Network Structural Hole Node Discovery Algorithm for Multi-Dimensional Attribute Fusion[J]. Netinfo Security, 2024, 24(8): 1265-1276.

Figures/Tables 13

References 25

[1]	ZHOU Jianlin, ZENG An, FAN Ying, et al. Identifying Important Scholars via Directed Scientific Collaboration Networks[J]. Scientometrics, 2018, 114: 1327-1343.
[2]	TIAN Zhao, JIA Limin, DONG Honghui, et al. Analysis of Urban Road Traffic Network Based on Complex Network[J]. Procedia Engineering, 2016, 137: 537-546.
[3]	AL-TARAWNEH A, AL-SARAIREH J. Efficient Detection of Hacker Community Based on Twitter Data Using Complex Networks and Machine Learning Algorithm[J]. Journal of Intelligent & Fuzzy Systems, 2021, 40(6): 12321-12337.
[4]	TIAN Jiyang. Research on Detection of Suspicious Money Laundering Based on Complex Transaction Network[D]. Heifei: Heifei University of Technology, 2022.
	田继阳. 基于复杂交易网络的可疑洗钱行为识别方法研究[D]. 合肥: 合肥工业大学, 2022.
[5]	DUAN Pinsheng, ZHOU Jianliang, GOH Y M. Spatial-Temporal Analysis of Safety Risks in Trajectories of Construction Workers Based on Complex Network Theory[EB/OL]. [2024-02-10]. https://www.sciencedirect.com/science/article/abs/pii/S1474034623001180?via%3Dihub.
[6]	LI Ning, HUANG Qian, GE Xiaoyu, et al. A Review of the Research Progress of Social Network Structure[J]. Complexity, 2021(1): 1-14.
[7]	BURT R S. Structural Holes: The Social Structure of Competition[M]. Cambridge: Harvard University Press, 2009.
[8]	ZHU Jiang, BAO Chongming, WANG Chongyun, et al. Discovery Algorithm for Top-k Structure Holes Based on Graph Structure Feature Analysis[J]. Computer Engineering, 2020, 46(5): 94-101, 108. doi: 10.19678/j.issn.1000-3428.0054340
	朱江, 包崇明, 王崇云, 等. 基于图结构特征分析的Top-k结构洞发现算法[J]. 计算机工程, 2020, 46(5): 94-101,108. doi: 10.19678/j.issn.1000-3428.0054340
[9]	LI Minjia, XU Guoyan, ZHU Shuai, et al. Influence Maximization Algorithm Based on Structure Hole and Degree Discount[J]. Journal of Computer Applications, 2018, 38(12): 3419-3424. doi: 10.11772/j.issn.1001-9081.2018040920
	李敏佳, 许国艳, 朱帅, 等. 基于结构洞和度折扣的影响力最大化算法[J]. 计算机应用, 2018, 38(12): 3419-3424. doi: 10.11772/j.issn.1001-9081.2018040920
[10]	PENG Sancheng, ZHOU Yongmei, CAO Lihong, et al. Influence Analysis in Social Networks: A Survey[J]. Journal of Network and Computer Applications, 2018, 106: 17-32.
[11]	SUN Xijing, SI Shoukui. Complex Network Algorithms and Applications[M]. Beijing: National Defense Industry Press, 2015.
	孙玺菁, 司守奎. 复杂网络算法与应用[M]. 北京: 国防工业出版社, 2015.
[12]	LI Gang, WANG Yuda, CUI Rong. KIC: An Extended K-Shell Decomposition Based on Improved Network Constraint Cofficient[J]. Journal of Modern Information, 2020, 40(12): 27-35.
	李钢, 王聿达, 崔蓉. KiC:一种结合“结构洞”约束值与K壳分解的社交网络关键节点识别算法[J]. 现代情报, 2020, 40(12): 27-35. doi: 10.3969/j.issn.1008-0821.2020.12.003
[13]	ZHAO Zhili, LI Ding, SUN Yue, et al. Ranking Influential Spreaders Based on Both Node K-Shell and Structural Hole[EB/OL]. (2023-01-25)[2024-02-10]. https://www.sciencedirect.com/science/article/abs/pii/S095070512201259X?via%3Dihub.
[14]	WANG Hao, WANG Jian, LIU Qian, et al. Identifying Key Spreaders in Complex Networks Based on Local Clustering Coefficient and Structural Hole Information[EB/OL]. [2024-02-10]. https://iopscience.iop.org/article/10.1088/1367-2630/ad0e89.
[15]	BERAHMAND K, BOUYER A, SAMADI N. A New Centrality Measure Based on The Negative and Positive Effects of Clustering Coefficient for Identifying Influential Spreaders in Complex Networks[J]. Chaos, Solitons and Fractals: The Interdisciplinary Journal of Nonlinear Science, and Nonequilibrium and Complex Phenomena, 2018, 110: 41-54.
[16]	YANG Jie, ZHANG Mingyang, RUI Xiaobin, el al. Influence Maximization Algorithm Based on Node Coverage and Structural Hole[J]. Journal of Computer Applications, 2022, 42(4): 1155-1161. doi: 10.11772/j.issn.1001-9081.2021071256
	杨杰, 张名扬, 芮晓彬, 等. 融合节点覆盖范围和结构洞的影响力最大化算法[J]. 计算机应用, 2022, 42(4): 1155-1161. doi: 10.11772/j.issn.1001-9081.2021071256
[17]	GAO Juyuan, WANG Zhixiao, RUI Xiaobin, el al. Node Coverage Based on Algorithm for Influence Maximization[J]. Computer Engineering and Design, 2019, 40(8): 2211-2215, 2246.
	高菊远, 王志晓, 芮晓彬, 等. 基于节点覆盖范围的影响力最大化算法[J]. 计算机工程与设计, 2019, 40(8): 2211-2215,2246.
[18]	ZHAO Linhai, LI Yingjie, WU Y J. An Identification Algorithm of Systemically Important Financial Institutions Based on Adjacency Information Entropy[J]. Computational Economics, 2022, 59(4): 1735-1753.
[19]	HUANG Wencheng, LI Haoran, YIN Yanhui, et al. Node Importance Identification of Unweighted Urban Rail Transit Network: An Adjacency Information Entropy Based Approach[J]. Reliability Engineering and System Safety, 2024(2): 1-16.
[20]	XU Xiang, ZHU Cheng, WANG Qingyong, et al. Identifying Vital Nodes in Complex Networks by Adjacency Information Entropy[EB/OL]. (2020-02-14)[2024-03-10]. https://pubmed.ncbi.nlm.nih.gov/32060330/.
[21]	KUMAR S, SPEZZANO F, SUBRAHMANIAN V S, et al. Edge Weight Prediction in Weighted Signed Networks[C]// IEEE. 2016 IEEE 16th International Conference on Data Mining(ICDM). New York: IEEE, 2016: 221-230.
[22]	KUMAR S, HOOI B, MAKHIJA D, et al. Rev2: Fraudulent User Prediction in Rating Platforms[C]// ACM. The Eleventh ACM International Conference on Web Search and Data Mining. New York: ACM, 2018: 333-341.
[23]	NEWMAN M E. Finding Community Structure in Networks Using The Eigenvectors of Matrices[J]. Physical Review E-Statistical, Nonlinear, and Soft Matter Physics, 2006, 74(3): 6104-6126.
[24]	LI Peng, WANG Shilin, CHEN Guangwu, et al. Identifying Key Nodes in Complex Networks Based on Local Structural Entropy and Clustering Coefficient[EB/OL]. (2022-08-30)[2024-02-10]. https://onlinelibrary.wiley.com/doi/10.1155/2022/8928765.
[25]	LU Mengke. Node Importance Evaluation Based on Neighborhood Structure Hole and Improved TOPSIS[EB/OL]. (2020-05-30)[2024-02-10]. https://www.sciencedirect.com/science/article/abs/pii/S138912861931031X.

名称	节点/个	边/条	平均度	平均聚类系数
network security	269	1083	8.05	0.918
soc-sign-bitcoinalpha	3783	24186	6.39	0.277
netscience	16264	95188	5.85	0.737

算法	$\xi $
算法	network security	soc-sign-bitcoinalpha	netscience
DC	0.115	0.148	0.047
BC	0.226	0.192	0.048
SHDD	0.156	0.124	0.045
NSCH	0.126	0.203	0.048
AIEAC	0.223	0.198	0.049
算法	$\tau $
算法	network security	soc-sign-bitcoinalpha	netscience
DC	0.082	0.832	0.845
BC	0.056	0.786	0.842
SHDD	0.048	0.859	0.848
NSCH	0.144	0.776	0.843
AIEAC	0.056	0.781	0.842
算法	网络平均剩余信息熵
算法	network security	soc-sign-bitcoinalpha	netscience
DC	1.65	0.987	1.860
BC	1.25	0.933	1.851
SHDD	1.28	1.138	1.877
NSCH	1.43	0.954	1.844
AIEAC	1.25	0.932	1.845

DC		BC		SHDD		NSCH		仅邻接信息熵		仅邻接中心性		AIEAC
ID	值	ID	值	ID	值	ID	值	ID	值	ID	值	ID	值
10	0.44	31	0.58	268	1	10	117	10	121.5	10	106.5	10	104.9
31	0.32	10	0.55	87	1	31	79	31	87.6	31	81.5	31	77.6
57	0.12	53	0.19	31	0.95	60	15	57	26.0	60	17.5	60	13.1
56	0.09	57	0.1	10	0.94	79	12	56	20.1	135	14.2	57	12.1
60	0.09	135	0.09	53	0.77	135	11	60	16.1	53	13	135	6.4
2	0.08	60	0.08	60	0.76	120	5	135	15.9	57	10.9	53	4.7
17	0.08	56	0.08	135	0.73	54	2	61	13.2	2	8.0	230	4.6
61	0.08	68	0.07	230	0.72	230	0	79	11.8	51	6.2	56	4.4