Sign Prediction of Links in Signed Directed Networks with Node's Balanced Index

doi:10.19678/j.issn.1000-3428.0068368

Abstract

Abstract:

The sign prediction of links in signed directed networks can be used to model many real-life problems; however, sign prediction is a core problem in the field of network science. The main theoretical support for sign prediction algorithms for links in signed directed networks is structural balance theory, which has profound research significance. Real-world networks are complicated. They do not precisely follow the structural balance theory, and different networks have their own unique characteristics. This study first analyzes the basic mechanisms affecting the signs of links and explores the network features reflecting the formation of signs. Next, the study defines the balanced index of a node from each remaining node and integrates its features according to Chiang's prediction method. The amount of feature information increases and the sign prediction of links in signed directed networks is achieved without increasing the computational complexity. The network features are divided into three categories and a logistic regression model is used to train and test different combinations of these features. Experimental results on several real network datasets demonstrate that the model exhibits good generalization ability and the inclusion of the node balance index feature significantly improves the predictive accuracy of the model. Finally, a logistic regression model is used to train and test all network features involved. Experimental comparisons are conducted between the proposed algorithm and the current advanced sign prediction link algorithm to validate its effectiveness.

Key words: signed directed networks, node's balanced index, sign prediction of links, supervised learning, logistic regression

摘要：

有向符号网络链路符号预测问题是网络科学领域核心问题之一, 在现实生活中的许多实际问题都可以建模为有向符号网络链路符号预测问题。结构平衡理论作为有向符号网络链路符号预测算法的主要理论支撑, 具有深远的研究意义。事实上, 现实世界的网络构成十分复杂, 并非完全符合结构平衡理论, 不同类型的网络有其独有特点。基于此, 分析影响链路符号的各项基本机理, 对反映链路符号形成的网络特征进行研究, 从每个节点出发, 定义节点平衡性指数, 并在Chiang的预测方法基础上融入节点平衡性指数相关特征, 增大特征信息量, 实现有向符号网络链路符号预测, 且在此过程中不提升计算复杂度。将所有网络特征分为三类, 通过逻辑回归模型对三类网络特征的不同组合进行训练和测试, 在真实网络数据集上的实验结果表明, 节点平衡性指数相关特征的加入能大幅提升模型的预测精度, 且模型具有较好的泛化能力。最后根据逻辑回归模型对所有涉及的网络特征进行训练和测试, 通过提出算法与目前较为先进的链路符号预测算法做实验对比, 验证其有效性。

关键词: 有向符号网络, 节点平衡性指数, 链路符号预测, 有监督学习, 逻辑回归

LI Shupeng, DONG Jiyuan, LIU Juan. Sign Prediction of Links in Signed Directed Networks with Node's Balanced Index[J]. Computer Engineering, 2025, 51(6): 360-374.

李树鹏, 董继远, 刘娟. 融入节点平衡性指数的有向符号网络链路符号预测[J]. 计算机工程, 2025, 51(6): 360-374.

/ Recommend / Download Citations

URL: https://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0068368

https://www.ecice06.com/EN/Y2025/V51/I6/360

Figures/Tables 15

Fig.1 The structure of balanced triangles and unbalanced triangles

Fig.2 Sign prediction of links in signed directed networks

Fig.3 Node balanced index

Fig.4 Degree distributions of five real networks

Fig.5 AUC and Accuracy for complete datasets

Fig.6 AUC and Accuracy of datasets with 50% positive and negative links

Fig.7 AUC of complete datasets

Fig.8 Accuracy of complete datasets

Fig.9 AUC of datasets with 50% positive and negative links

Fig.10 Accuracy of datasets with 50% positive and negative links

Fig.11 Generalization capability of models

Fig.12 Link prediction results based on Accuracy about complete datasets and datasets with 50% positive and negative links

References 29

1	HEIDER F . Attitudes and cognitive organization. Journal of Psychology, 1946, 21, 107- 112. doi: 10.1080/00223980.1946.9917275
2	LESKOVEC J, HUTTENLOCHER D, KLEINBERG J, et al. Predicting positive and negative links in online social networks[C]//Proceedings of the 19th International Conference on World Wide Web. New York, USA: ACM Press, 2010: 641-650.
3	HASSAN A, ABU-JBARA A, RADEV D, et al. Extracting signed social networks from text[C]//Proceedings of Text Graphs Workshop on Graph-based Methods for Natural Language Processing. Washington D. C., USA: IEEE Press, 2012: 6-14.
4	GUHA R, KUMAR R, RAGHAVAN P, et al. Propagation of trust and distrust[C]//Proceedings of the 13th International Conference on World Wide Web. New York, USA: ACM Press, 2004: 403-412.
5	BRZOZOWSKI M J, HOGG T, SZABO G. Friends and foes: ideological social networking[C]//Proceedings of SIGCHI Conference on Human Factors in Computing Systems. New York, USA: ACM Press, 2008: 817-820.
6	刘苗苗, 扈庆翠, 郭景峰, 等. 符号网络链接预测算法研究综述. 计算机科学, 2020, 47 (2): 21- 30.
	LIU M M , HU Q C , GUO J F , et al. Survey of link prediction algorithms in signed networks. Computer Science, 2020, 47 (2): 21- 30.
7	LESKOVEC J, HUTTENLOCHER D, KLEINBERG J, et al. Signed networks in social media[C]//Proceedings of SIGCHI Conference on Human Factors in Computing Systems. New York, USA: ACM Press, 2010: 1361-1370.
8	KUNEGIS J , SCHMIDT S , LOMMATZSCH A , et al. Spectral analysis of signed graphs for clustering, prediction and visualization. Data Mining, 2010, 64 (6): 975- 978.
9	SHEN P F , LIU S F , WANG Y , et al. Unsupervised negative link prediction in signed social networks. Mathematical Problems in Engineering, 2019, 2019 (1): 7348301. doi: 10.1155/2019/7348301
10	吴清春, 贾彩燕. 一种融合社交关系的矩阵分解推荐模型. 计算机工程, 2020, 46 (8): 72-77, 84. doi: 10.19678/j.issn.1000-3428.0054954
	WU Q C , JIA C Y . A matrix factorization recommendation model fusing social relationship. Computer Engineering, 2020, 46 (8): 72-77, 84. doi: 10.19678/j.issn.1000-3428.0054954
11	PRIYANKA A, GARG V K, NARAYANAM R. Link label prediction in signed social networks[C]//Proceedings of the 23rd International Joint Conference on Artificial Intelligence. San Diego, USA: AAAI Press, 2013: 2591-2597.
12	HSIEH C J, CHIANG K Y, DHILLON I S, et al. Low rank modeling of signed networks[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM Press, 2012: 507-515.
13	佘宏俊, 胡梦缘. 基于符号网络的边值预测方法研究. 武汉理工大学学报(信息与管理工程版), 2015, 37 (5): 602- 606. doi: 10.3963/j.issn.2095-3852.2015.05.017
	SHE H J , HU M Y . Link prediction based on signed network. Journal of Wuhan University of Technology (Information & Management Engineering), 2015, 37 (5): 602- 606. doi: 10.3963/j.issn.2095-3852.2015.05.017
14	刘苗苗, 郭景峰, 陈晶. 相似性与结构平衡论结合的符号网络边值预测. 工程科学与技术, 2018, 50 (4): 161- 169.
	LIU M M , GUO J F , CHEN J . Link prediction in signed networks based on similarity and structural balance theory. Advanced Engineering Sciences, 2018, 50 (4): 161- 169.
15	刘苗苗, 扈庆翠, 郭景峰, 等. 符号网络中融合聚集系数与符号影响力的链路预测算法. 四川大学学报(自然科学版), 2021, 58 (5): 52- 62.
	LIU M M , HU Q C , GUO J F , et al. Link prediction algorithm in signed networks based on clustering coefficient and sign influence. Journal of Sichuan University (Natural Science Edition), 2021, 58 (5): 52- 62.
16	ZHANG H , WU G , LING Q . Distributed stochastic gradient descent for link prediction in signed social networks. EURASIP Journal on Advances in Signal Processing, 2019, 2019 (1): 3. doi: 10.1186/s13634-019-0601-0
17	盛俊, 顾沈胜, 陈崚. 基于隐空间映射的带符号网络上的顶点分类. 计算机应用, 2019, 39 (5): 1411- 1415.
	SHENG J , GU S S , CHEN L . Node classification in signed networks based on latent space projection. Journal of Computer Applications, 2019, 39 (5): 1411- 1415.
18	刘林峰, 于子兴, 祝贺. 基于门控循环单元的移动社会网络链路预测方法. 计算机研究与发展, 2023, 60 (3): 705- 716.
	LIU L F , YU Z X , ZHU H . A link prediction method based on gated recurrent units for mobile social network. Journal of Computer Research and Development, 2023, 60 (3): 705- 716.
19	BURKE M, KRAUT R. Mopping up: modeling wikipedia promotion decisions[C]//Proceedings of the 2008 ACM Conference on Computer Supported Cooperative Work. New York, USA: ACM Press, 2008: 27-36.
20	CHIANG K Y, NATARAJAN N, TEWARI A, et al. Exploiting longer cycles for link prediction in signed networks[C]//Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York, USA: ACM Press, 2011: 1157-1162.
21	张维玉, 吴斌, 刘旸. 融合多特征的符号网络连边符号预测. 北京邮电大学学报, 2014, 37 (5): 80- 84.
	ZHANG W Y , WU B , LIU Y . Integrating multi-feature for link sign prediction in signed networks. Journal of Beijing University of Posts and Telecommunications, 2014, 37 (5): 80- 84.
22	PAPAOIKONOMOU A , KARDARA M , TSERPES K , et al. Predicting edge signs in social networks using frequent subgraph discovery. IEEE Internet Computing, 2014, 18 (5): 36- 43.
23	ZOLFAGHAR K, AGHAIE A. Mining trust and distrust relationships in social Web applications[C]//Proceedings of the 2010 IEEE 6th International Conference on Intelligent Computer Communication and Processing. Washington D. C., USA: IEEE Press, 2010: 73-80.
24	ZHOU T , LEE Y L , WANG G N . Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms. Physica A: Statistical Mechanics and Its Applications, 2021, 564, 125532.
25	SITUNGKIR H, KHANAFIAH D. Social balance theory: revisiting Heider's balance theory for many agents[EB/OL]. [2023-08-10]. https://arxiv.org/ftp/nlin/papers/0405/0405041.pdf.
26	LU Z D, SAVAS B, TANG W, et al. Supervised link prediction using multiple sources[C]//Proceedings of IEEE International Conference on Data Mining. Washington D. C., USA: IEEE Press, 2010: 923-928.
27	YANG S , HU B B , ZHANG Z Q , et al. Inductive link prediction with Interactive structure learning on attributed graph. Berlin, Germany: Springer, 2021: 383- 398.
28	DERR T, MA Y, TANG J L. Signed graph convolutional networks[C]//Proceedings of IEEE International Conference on Data Mining. Washington D. C., USA: IEEE Press, 2018: 929-934.
29	HE C X , ZENG J Y , LI Y , et al. Two-stream signed directed graph convolutional network for link prediction. Physica A: Statistical Mechanics and Its Applications, 2022, 605, 128036.

[1]	GAO Rui, AN Guocheng, ZOU Danping, PEI Ling. Semi-Supervised Vehicle Detection Algorithm Based on Improved YOLOv5 [J]. Computer Engineering, 2025, 51(3): 300-309.
[2]	ZHANG Xinbo, ZHANG Xueying, HUANG Lixia, CHEN Guijun. Classification Algorithm and Application Based on Semi-Supervised Deep Auto-Encoder Network [J]. Computer Engineering, 2025, 51(1): 71-80.
[3]	GUO Min, ZHANG Xihan, LI Yang. Integrated Attentional Teacher Mutual Consistency Semi-Supervised Medical Image Segmentation [J]. Computer Engineering, 2024, 50(9): 313-323.
[4]	YANG Jinlin, LI Chaofeng. Domain Transform Image Raindrop Removal Method by Integrating Fast Fourier Convolution [J]. Computer Engineering, 2024, 50(9): 296-303.
[5]	Xuanyu ZHOU, Lianhua WU, Qinhua ZHENG, Tianxing XIAO, Zixuan WANG, Simin ZHANG. Weakly Supervised Video Anomaly Detection Method for Rope Skipping Combined with Semantic Prompts and Memory Enhancement [J]. Computer Engineering, 2024, 50(7): 87-95.
[6]	Zhengkang ZHANG, Dan YANG, Tiezheng NIE, Yue KOU. Self-Supervised Learning Based on Graph Structural Clustering for Disease Diagnosis Method [J]. Computer Engineering, 2024, 50(7): 360-371.
[7]	LI Yongfei, LI Mingyang, CHANG Xin, CAO Kexin. Anomaly Detection of IoT Water Quality Monitoring Data Based on Explainable Deep Learning [J]. Computer Engineering, 2024, 50(6): 179-187.
[8]	ZHANG Huiyan, LIANG Yong, LAN Jinghong, ZHAO Qiang. Intrusion Detection Method Based on Memory Module and Filtered Generative Adversarial Network [J]. Computer Engineering, 2024, 50(6): 197-207.
[9]	GU Yonggen, GAO Lingxuan, WU Xiaohong, TAO Jie. Research on Data Sharing of Federated Semi-Supervised Learning with Non-IID [J]. Computer Engineering, 2024, 50(6): 188-196.
[10]	YU Changhong, XU Konghao, ZHANG Ze, GAO Ming. Improving Network Intrusion Detection Methods in Isolated Forests Based on Split Points [J]. Computer Engineering, 2024, 50(6): 148-156.
[11]	LI Jing, LI Jian, CHEN Haifeng, ZHANG Qian, WANG Liyan, PEI Ercheng. Facial Expression Recognition Based on Key Region Masking and Reconstruction [J]. Computer Engineering, 2024, 50(5): 241-249.
[12]	ZHANG Baoxin, YANG Dan, NIE Tiezheng, KOU Yue. Recommendation Method Based on Self-supervised Multi-view Graph Collaborative Filtering [J]. Computer Engineering, 2024, 50(5): 100-110.
[13]	WANG Lin, HUANG Hao. Voice Conversion Combining Vector Quantization and CTC Introducing Pre-Trained Representation [J]. Computer Engineering, 2024, 50(4): 313-320.
[14]	Yonghang SHAN, Xi ZHANG, Chuan HU, Taojun DING, Yuan YAO. Traffic Accident Severity Prediction Research and Application Based on Ensemble Learning [J]. Computer Engineering, 2024, 50(2): 33-42.
[15]	Yinyin HE, Jing HU, Zhibo CHEN, Rongguo ZHANG. Low-light Image Enhancement Method Combining Gated Transformation Mechanism and GAN [J]. Computer Engineering, 2024, 50(2): 247-255.

Please choose a citation manager

Content to export