Signed Prediction Algorithm Based on Structural Balance Theory and Status Theory
CUI Xiaoli1, XUE Leyang1,2, ZHANG Peng 1
1. School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China; 2. International Academic Center of Complex Systems, Beijing Normal University, Zhuhai 519087, China
Abstract：Aiming at the difficulty of balancing the accuracy and complexity of the sign prediction algorithm, this paper effectively integrates the law of social development and the local characteristics of the network, and proposes a sign prediction algorithm based on structural balance theory and status theory to calculate the similarity of nodes. In order to better combine the contribution of the above two theories to the similarity score of the two nodes, this paper uses the regulator to sum the similarity score based on the two theories according to the weight of the regulator, and the positive or negative of the similarity score is the result predicted by the edge symbol. Finally, the algorithm is tested on several different data sets and compared with the classical CN algorithm and PSNBS algorithm in two aspects of prediction accuracy and algorithm complexity. The proposed algorithm is very close to the classical algorithm in terms of prediction accuracy, but in terms of time complexity, it is an order of magnitude lower than the classical algorithm.It is obviously better than classical algorithm.
崔晓丽, 薛乐洋, 张鹏. 基于结构平衡理论与地位理论的符号预测算法[J]. 复杂系统与复杂性科学, 2023, 20(3): 68-73.
CUI Xiaoli, XUE Leyang, ZHANG Peng. Signed Prediction Algorithm Based on Structural Balance Theory and Status Theory. Complex Systems and Complexity Science, 2023, 20(3): 68-73.
[1] 程苏琦,沈华伟,张国清,等.符号网络研究综述[J].软件学报,2014,25(1):115. CHENG S Q, SHEN H W, ZHANG G Q, et al.Survey of signed network research[J].Journal of Software,2014,25(1):115. [2] HEIDER F. Attitudes and cognitive organization[J]. The Journal of Psychology Interdisciplinary and Applied, 1946, 21(1):107112. [3] GHOSN F, PALMER G, BREMER S A. The MID3 data set, 19932001: procedures, coding rules, and description[J]. Conflict Management and Peace Science, 2004, 21(2):133154. [4] 蓝梦微,李翠平,王绍卿,等.符号社会网络中正负关系预测算法研究综述[J].计算机研究与发展,2015,52 (2):410422. LAN M W, LI C P, WANG S Q, et al. Survey of sign prediction algorithms in signed social networks[J].Journal of Computer Research and Development,2015,52(2):410422. [5] GUHA R, KUMAR R, RAGHAVAN P, et a1. Propagation of trust and distrust[C] // Proc of the 13th Int Conf onworld wide Web.New York: ACM, 2004: 403412. [6] AGRAWAL P, GARG V K,NARAYANAM R. Link label prediction in signed social networks[C] //Proceedings of the 23rd International Joint Conference on Artificial Intelligence. Beijing: AAAI,2013:25912597. [7] HSIEH C J, CHIANG K Y, DHILLON I S. Low rank modeling of signed networks[C] //Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM,2012:507515. [8] LESKOVEC J, HUTTENLOCHER D,KLEINBERG J.Signed networks in social media[C] //Proceedings of the SIGCHI International Conference on Human Factors in Computing Systems.New York:ACM,2010:13611370. [9] YANG S H, SMOLA A J,LONG B, et al.Friend or frenemy?prediction signed ties in social networks[C] //Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval.New York:ACM,2012:555564. [10] SYMEONIDIS P, TIAKAS E. Transitive node similarity:Prediction and recommending links in signed social networks[J]. Internet & Web Information Systems,2014,17(4):743776. [11] 佘宏俊,胡梦缘.基于符号网络的边值预测方法研究[J].武汉理工大学学报(信息与管理工程版),2015,37 (5):464468. SHE H J, HU M Y. Research of link prediction based on signed networks[J]. Journal of Wuhan University of Technology (Information & Management Engineering), 2015,37(5):464468. [12] ZHANG W Y, WU B, LIU Y. Integrating multi-feature for link sign prediction in signed networks[J]. Journal of Beijing University of Posts and Telecommunications, 2014, 37(5): 8084. [13] 刘苗苗,郭景峰,陈晶.相似度与结构平衡论结合的符号网络边值预测[J].工程科学与技术,2018, 50(4): 161169. LIU M M, GUO J F, CHEN J. Link prediction in signed networks based on similarity and structural balance theory[J].Advanced Engineering Sciences,2018,50(4):161169. [14] CA RTWRIGHT D, HARARY F. Structural balance: a generalization of Heider’s theory [J]. Psychological Review,1956,63(5):27. [15] LESKOVEC J, HUTTENLOCHER D, K1EINBERG J. Predicting positive and negative links in online social networks[C] //Proc of the 19th Int Conf on World Wide Web. New York:ACM,2010:641650. [16] SRINIVASAN A. Local balancing influences global structure in social networks[J].Proc of the National Academy of Sciences of the United States of America, 2011, 108(5):17511752. [17] EASLEY D, KLEINBERG J. Networks, Crowds, and Markets: Reasoning About a Highly connected world[M]. New York:Cambridge University Press,2010:119152. [18] CHIANG K Y, NATARAJAN N, TEWARI A, et al. Exploiting longer cycles for link prediction in signed networks[C] // Proceedings of the 20th ACM Conference on Information and Knowledge Management.New York: ACM, 2011:11571162. [19] CHIANG K Y, HSIEH C J, NATARAJAN N, et al. Prediction and clustering in signed networks: a local to global perspective[J]. Journal of Machine Learning Research, 2013, 15(1):11771213.
