融入节点平衡性指数的有向符号网络链路符号预测

doi:10.19678/j.issn.1000-3428.0068368

摘要/Abstract

摘要：

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

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

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

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

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.

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

图/表 15

图1 3阶平衡圈结构与3阶不平衡圈的结构

Fig.1 The structure of balanced triangles and unbalanced triangles

图2 有向符号网络链路符号预测

Fig.2 Sign prediction of links in signed directed networks

图3 节点平衡性指数

Fig.3 Node balanced index

图4 5个真实网络的度分布

Fig.4 Degree distributions of five real networks

图5 完整数据集下的AUC和Accuracy

Fig.5 AUC and Accuracy for complete datasets

图6 正负链路比例各为50%数据集的AUC和Accuracy

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

图7 完整数据集的AUC

Fig.7 AUC of complete datasets

图8 完整数据集的Accuracy

Fig.8 Accuracy of complete datasets

图9 正负链路比例各为50%的数据集AUC

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

图10 正负链路比例各为50%的数据集Accuracy

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

图11 模型的泛化能力

Fig.11 Generalization capability of models

图12 完整数据集和正负链路比例各为50%的数据集基于Accuracy指标的链路预测实验结果

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

参考文献 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]	单永航, 张希, 胡川, 丁涛军, 姚远. 基于集成学习的交通事故严重程度预测研究与应用[J]. 计算机工程, 2024, 50(2): 33-42.
[2]	马娜, 温廷新, 贾旭, 李晓会. 复杂光照条件下自适应的车脸重识别模型[J]. 计算机工程, 2023, 49(8): 275-282, 290.
[3]	唐敏, 张宇浩, 邓国强. 一种高效的非交互式隐私保护逻辑回归模型[J]. 计算机工程, 2023, 49(4): 32-42,51.
[4]	杨越佳, 华蓓, 钟志威, 高咪. 基于同态加密的隐私保护逻辑回归协同计算[J]. 计算机工程, 2023, 49(4): 23-31.
[5]	梁晓萌, 严明, 吴杰. 基于人工蜂群算法的Tor流量在线识别方法[J]. 计算机工程, 2021, 47(11): 129-135,143.
[6]	胡斌, 周志洪, 姚立红, 李建华. 结合报文负载与流指纹特征的恶意流量检测[J]. 计算机工程, 2020, 46(11): 157-163.
[7]	陈扬洋, 钱鹏江, 赵开发, 苏冠豪. 基于mDixon序列下腹部MRI数据的sCT生成方法[J]. 计算机工程, 2019, 45(7): 273-281.
[8]	邓路佳,刘平山. 基于GMM-FMs的广告点击率预测研究[J]. 计算机工程, 2019, 45(5): 122-126.
[9]	李平,戴月明,王艳. 基于混合卡方统计量与逻辑回归的文本情感分析[J]. 计算机工程, 2017, 43(12): 192-196,202.
[10]	陈霞,闵华清,宋恒杰. 众包平台作弊用户自动识别[J]. 计算机工程, 2016, 42(8): 139-145,152.
[11]	巫可,战荫伟,李鹰. 融合用户属性的隐语义模型推荐算法[J]. 计算机工程, 2016, 42(12): 171-175.
[12]	陈鸿,金培权,岳丽华,胡玉娟,殷凤梅. 基于上下文特征分类的评论长句切分方法[J]. 计算机工程, 2015, 41(9): 233-237,244.
[13]	郭丽，郑忠龙，贾炯，张海新，付芳梅. 一种有监督的线性降维人脸识别算法[J]. 计算机工程, 2013, 39(11): 169-173.
[14]	吕韶华, 杨亮, 林鸿飞. 基于LDA模型的餐馆评论排序[J]. 计算机工程, 2011, 37(19): 62-64,67.
[15]	钟明, 薛惠锋, 梅觅. 基于局部线性嵌入的最大散度矩阵算法[J]. 计算机工程, 2011, 37(12): 176-178.

选择文件类型/文献管理软件名称

选择包含的内容