Computer Science ›› 2020, Vol. 47 ›› Issue (2): 21-30.doi: 10.11896/jsjkx.190600104

• Database & Big Data & Data Science • Previous Articles     Next Articles

Survey of Link Prediction Algorithms in Signed Networks

LIU Miao-miao1,2,HU Qing-cui1,GUO Jing-feng3,CHEN Jing3   

  1. (School of Computer & Information Technology,Northeast Petroleum University,Daqing,Heilongjiang 163318,China)1;
    (The Key Laboratory for Oil Big Data and Intelligent Analysis of Heilongjiang Province,Daqing,Heilongjiang 163318,China)2;
    (School of Information Science and Engineering,Yanshan University,Qinhuangdao,Hebei 066004,China)3
  • Received:2019-06-20 Online:2020-02-15 Published:2020-03-18
  • About author:LIU Miao-miao,born in 1982,Ph.D,associate professor,master supervisor,is member of China Computer Federation (CCF).Her main research interests include social network analysis and so on.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (61602401, 61871465), Natural Science Foundation of Heilongjiang Province (LH2019F042) and Youth Science Foundation of Northeast Petroleum University (2018QNQ-01).

Abstract: Link prediction in signed networks includes the possibility prediction of link existence or establishment and the sign prediction of unknown links between two nodes in the network.Related research is of great significance for analyzing and understanding the topological structure,function and evolutionary behaviors of signed networks,and has great application value in the fields of personalized recommendation,attitude prediction and protein interaction research and other fields.This paper reviewed the research results of link prediction in signed networks,and introduced related concepts,theoretical basis,commonly used data sets and evaluation indexes of link prediction accuracy of signed networks.According to the design idea,link prediction algorithms in signed networks were mainly divided into two categories,namely supervised and unsupervised machine learning method.The main idea of each algorithm was elaborated in detail.The characteristics,rules and existing problems of link prediction in signed networks were discussed,and the challenges and possible directions in the future were also pointed out,which can provide useful reference for relevant researchers in the fields of informatics,biology and sociology and so on.

Key words: Signed networks, Link prediction, Structural balance theory, Machine learning, Sign prediction

CLC Number: 

  • TP301
[1]CHENG S Q,SHEN H W,ZHANG G Q,et al.A research review of signed networks [J].Journal of Software,2014,25(1):1-15.
[2]SONG D,MEYER D A,TAO D.Efficient Latent Link Recommendation in Signed Networks[C]∥Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining.2015:1105-1114.
[3]LV L Y,ZHOU T.Link prediction in complex networks:A survey [J].Physica A:Statistical Mechanics & Its Application,2011,390(6):1150-1170.
[4]LIU D W,LV Y N,YU Z H.An improved algorithm for link prediction in complex networks [J].Journal of Chinese Mini-Micro computer systems,2016,37(5):1071-1074.
[5]LIU M M,GUO J F,CHEN J.Link prediction in signed net-works based on similarity and structural balance theory [J].Advanced Engineering Sciences,2018,50(4):161-169.
[6]GUHA R,KUMAR R,RAGHAVAN P,et al.Propagation of trust and distrust[C]∥Proceeding of the 13th International Conference on World Wide Web.New York:ACM,2004,125(6952):403-412.
[7]TANG J,CHANG J,AGGARWAL C,et al.Negative Link Prediction in Social Media[C]∥Proceedings of the Eighth ACM International Conference on Web Search and Data Mining.2015:87-96.
[8]ZOLFAGHAR K,AGHAIE A.Mining trust and distrust relationships in social web applications[C]∥Proceedings of IEEE International Conference on Intelligent Computer Communication and Processing.New York:IEEE,2010:73-80.
[9]LI R H,YU J X,HUANG X,et al.A framework of algorithms:Computing the bias and prestige of nodes in trust networks [J].Plos One,2013,8(5):10.1371.
[10]KAYA B,POYRAZ M.Age-series based link prediction in evolving disease networks [J].Computers in Biology and Medicine,2015,63(C):1-10.
[11]NIGAM A,CHAWLA N V.Link Prediction in a Semi-bipartite network for recommendation[C]∥Proceedings of International Conference on Intelligent Information and Database Systems.Kanazawa:Japan,2016:127-135.
[12]TANG J,AGGARWAL C,LIU H.Recommendations in Signed Social Networks[C]∥Proceedings of the 25th International Conference on World Wide Web.2016:31-40.
[13]FANG H,GUO G,ZHANG J.Multi-faceted trust and distrust prediction for recommender systems [J].Decision Support Systems,2015,71:37-47.
[14]MAHTAR S,MASROM S,Omar N OMAR,et al.Trust aware recommender system with distrust in different views of trusted users [J].Journal of Fundamental and Applied Sciences,2017,9(55):168-181.
[15]XIE F,CHEN Z,SHANG J X,et al.A link prediction approach for item recommendation with complex number [J].Knowledge-Based Systems,2015(81):148-158.
[16]KUNEGIS J,SCHMIDT S,LOMMATZSCH A,et al.Spectral Analysis of Signed Graphs for Clustering,Prediction and Visua-lization [J].Siam International Conference on Data Mining,2010,64(6):975-978.
[17]GE M Q,LI A,WANG M H.A Bipartite Network-based Method for Prediction of Long Non-coding RNA-protein Interactions [J].Genomics,Proteomics & Bioinformations,2016,14(1):62-71.
[18]GUO J F,LIU M M,LUO X.Link Prediction Based on Similarity of Nodes of Multipath in Weighted Social Networks [J].Journal of Zhejiang University (Engineering Science),2016,50(7):1347-1352.
[19]HEIDER F.Attitudes and cognitive organization[J].Journal of Psychology,1946,21(1):107-112.
[20]CARTWRIGHT D,HARARY F.Structural balance:A genera-lization of Heider’s theory [J].Psychological Review,1956,63(5):277.
[21]LESKOVEC J,HUTTENLOCHER D,KLEINBERG J.Predicting Positive and Negative Links in Online Social Networks[C]∥Proceedings of the International World Wide Web Confe-rence Committee (IW3C2).Carolina,USA:ACM,2010:641-650.
[22]KUNEGIS J.Applications of Structural Balance in Signed Social Networks [J].arXiv:1402.6865v1.
[23]HASSAN A,ABU-JBARA A,RADEV D.Extracting signed social networks from text[C]∥Proceedings of the TextGraphs Workshop on Graph-based Methods for Natural Language Processing.Donostia-San,Spain:FSMNLP,2012:6-14.
[24]DAVIS J A.Clustering and structural balance in graphs [J].Human Relations,1967,20(2):181-187.
[25]BRUSCO M,DOREIAN P,MRVAR A,et al.Two algorithms for relaxed structural balance partitioning:linking theory,models and data to understand social network phenomena [J].Sociological Methods & Research,2011,40(1):57-87.
[26]ANCHURI P,MAGDON-ISMAIL M.Communities and Balance in Signed Networks:A Spectral Approach[C]∥Proceedings of International Conference on Advances in Social Networks Analysis and Mining.New York:ACM,2012,235-242.
[27]ZENG Y,LIU J.Community Detection from Signed Social Networks Using a Multi-objective Evolutionary Algorithm [M].Springer International Publishing,2015.
[28]GUO J F,LIU M M,LIU L L,et al.A community detection method to undirected weighted signed social networks [J].Journal of Computational Information Systems,2015,11(10):3623-3632.
[29]WANG S,TANG J,AGGARWAL C,et al.Signed Network Embedding in Social Media[C]∥Proceedings of the 2017 SIAM International Conference on Data Mining.2017.
[30]LESKOVEC J,HUTTENLOCHER D,KLEINBERG J.Signed networks in social media[C]∥Proceedings of the 28th International Conference on Human Factors in Computing Systems.New York:ACM,2010:1361-1370.
[31]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:555-564.
[32]KUNEGIS J,LOMMATZSCH A,BAUCKHAGE C.The Slashdot Zoo:Mining a social network with negative edges[C]∥Proceedings of the 18th International Conference on World Wide Web.New York,USA,2009:741-750.
[33]MANIU S,CAUTIS B,ABDESSALEM T.Building a signed network from interactions in Wikipedia[C]∥Proceedings of the Databases and Social Networks.New York:ACM Press,2011:19-24.
[34]BREIMAN L,SPECTOR P.Submodel selection and evaluation in regression-the x-random case [J].International statistical review,2011,60(3):291-319.
[35]LIU M M,GUO J F,CHEN J.Link prediction in signed networks based on the similarity and structural balance theory [J].Journal of Information Hiding and Multimedia Signal Processing,2017,8(4):831-846.
[36]LAN M W,LI C P,WANG S Q,et al.Research on the prediction algorithm of positive and negative relationships in signed social networks [J].Computer Research and Development,2015,52(2):410-422.
[37]KAYA B,POYRAZ M.Supervised link prediction in symptom networks with evolving case [J].Measurement,2014,56:231-238.
[38]ZHENG X,ZENG D,WANG F.Social balance in signed net-works [J].Information System Frontiers,2015,17(5):1077-1095.
[39]BORZYMEK P,SYDOW M.Trust and Distrust Prediction in Social Network with Combined Graphical and Review-based Attributes[C]∥Proceedings of the Agent and Multi-Agent Systems:Technologies and Applications.LNCS,Berlin:Springer,2010:122-131.
[40]YE J H,CHENG H,ZHU Z,et al.Predicting positive and negative links in signed social networks by transfer learning[C]∥Proceedings of the 22nd International Conference on World Wide Web.New York:ACM,2013:1477-1488.
[41]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):80-84.
[42]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:ACM,2011:1157-1162.
[43]PATIDAR A,AGARWAL V,BHARADWAJ K K.Predicting Friends and Foes in Signed Networks using Inductive Inference and Social Balance Theory[C]∥Proceedings of IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining.Istanbul,Turkey:ACM,2012:384-388.
[44]PAPAOIKONOMOU A,KARDARA M,TSERPES K,et al. Predicting edge signs in social networks using frequent sub-graph discovery[J].IEEE Internet Computing,2014,18(5):36-43.
[45]WU J H.Positive and Negative Social Relation Classification Prediction in Heterogeneous Signed Network [J].Information Science,2016,34(1):81-86.
[46]TENG S H,SU Q J,LIU D N,et al.Research about Optimizing Prediction Accuracy and Time Complexity in Signed Networks [J].Industrial Engineering Journal,2017,20(1):59-64.
[47]WEI T.Research on Predicting Positive and Negative Links in Social Networks by Ensemble Learning [D].Wuhan:Master dissertation of Huazhong University of Science and Technology,2016.
[48]DUBOIS T,GOLBECK J,SRINIVASAN A.Predicting trust and distrust in social networks.In Privacy,security,risk and trust[C]∥Proceedings of 2011 IEEE Third International Conference on Social Computing.2011:418-424.
[49]ZENG J F,ZHOU K,MA X,et al.Exploiting Cluster-based Meta Paths for Link Prediction in Signed Networks[C]∥Proceedings of the 2016 ACM Conference on Information and Know-ledge Management.Indianapolis,IN,USA:ACM,2016:1905-1908.
[50]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.California,USA:AAAI Press,2013:2591-2597.
[51]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:507-515.
[52]SU X P,SONG Y R.Local labeling features and a prediction method for a signed network [J].CAAI Transactions on Intelligent Systems,2018,13(3):437-444.
[53]ZHANG H,WU G,LING Q.Distributed stochastic gradient descent for link prediction in signed social networks [J].EURASIP Journal on Advances in Signal Processing,2019,3:1-11.
[54]MENON A K,ELKAN C.Link prediction via matrix factorization[C]∥Proceedings of the 2011 European Conference on Machine Learning and Knowledge Discovery in Databases.Athens,Greece,2011:437-452.
[55]CEN Y,GU R,JI Y.Sign Inference for Dynamic Signed Net-works via Dictionary Learning [J].Journal of Applied Mathematics,2013(3):701-710.
[56]DAI C,CHEN L,LI B.Link prediction based on sampling in complex networks[J].Applied Intelligence,2017,47(1):1-12.
[57]GU S S.Research on Link Prediction in signed complex net-works [D].Yangzhou:Master’s Dissertation of Yangzhou University,2018:6-9.
[58]SYMEONIDIS P,TIAKAS E.Transitive Node Similarity:pre-diction and recommending links in signed social networks [J].World Wide Web-internet & Web Information Systems,2014,17(4):743-776.
[59]JAVARI A,MAHDI J.Cluster-based collaborative filtering for sign prediction in social networks with positive and negative links [J].ACM Trans on Intelligent Systems and Technology,2014,5(2):1-24.
[60]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):464-468.
[61]ZHANG X Q,WANG X F.Signed network prediction based on structural balance theory and LP algorithm [J].Journal of Yunnan Minzu University (Natural Science Edition),2018,27(1):52-57.
[62] GIRDHAR N,MINZ S,BHARADWAJ K K.Link prediction in signed social networks based on fuzzy computational model of trust and distrust [J].Soft Computing,2019(3):12123-12138.
[63]LEE W P,MA C Y.Enhancing collaborative recommendation performance by combining user preference and trust-distrust propagation in social networks [J].Knowledge-Based Systems,2016,106:125-134.
[64]LU Z G,YE M L.Social network edge sign prediction based on node status and similarity [J/OL].
[65]LIU F,LIU B,SUN C,et al.Deep Belief Network-Based Ap-proaches for Link Prediction in Signed Social Networks [J].Entropy,2015,17(4):2140-2169.
[66]WANG X,WANG Y,ZUO W L.Exploring interactional opi-nions and status theory for predicting links in signed network[J].Journal of Computer Research and Development,2016,53(4):764-775.
[67]GU S S,CHEN L,LI B,et al.Link prediction on signed social networks based on latent space mapping [J].Applied Intelligence,2019,49:703-722.
[68]YUAN W,HE K,GUAN D,et al.Graph kernel based link prediction for signed social networks [J].Information Fusion,2019,46:1-10.
[69] CHEN X,GUO G F,PAN X,et al.Link prediction in signed networks based on connection degree [J].Journal of Ambient Intelligence and Humanized Computing,2019,10:1747-1757.
[70]SONG D J,MEYER D A.Link sign prediction and ranking in signed directed social networks [J].Social network analysis and mining,2015,5:52.
[71]ZHAO K K,ZHANG J,ZHANG L F,et al.Signed Network Prediction Method Based on the Client-to-Client Distributed Framework [J].Journal of Software,2018,29(3):614-626.
[72]ZHANG Z,WEN J,SUN L,et al.Efficient Incremental Dynamic Link Prediction Algorithms in Social Networks [J].Knowledge-Based Systems,2017,132:226-235.
[73]GUNES I,GUNDUZ-GUDUCU S,ATALTEPE Z.Link prediction using time series of neighborhood-based node similarity scores [J].Data Mining & Knowledge Discovery,2016,30(1):147-180.
[1] LI Yin, LI Bi-xin. Memory Leak Test Acceleration Based on Script Prediction and Reconstruction [J]. Computer Science, 2020, 47(9): 31-39.
[2] DING Yu, WEI Hao, PAN Zhi-song, LIU Xin. Survey of Network Representation Learning [J]. Computer Science, 2020, 47(9): 52-59.
[3] SU Chang, ZHANG Ding-quan, XIE Xian-zhong, TAN Ya. NFV Memory Resource Management in 5G Communication Network [J]. Computer Science, 2020, 47(9): 246-251.
[4] WANG Hui, LE Zi-chun, GONG Xuan, WU Yu-kun, ZUO Hao. Review of Link Prediction Methods Based on Feature Classification [J]. Computer Science, 2020, 47(8): 302-312.
[5] YUAN Ye, HE Xiao-ge, ZHU Ding-kun, WANG Fu-lee, XIE Hao-ran, WANG Jun, WEI Ming-qiang, GUO Yan-wen. Survey of Visual Image Saliency Detection [J]. Computer Science, 2020, 47(7): 84-91.
[6] PENG Wei, HU Ning and HU Jing-Jing. Overview of Research on Image Steganalysis Algorithms [J]. Computer Science, 2020, 47(6A): 325-331.
[7] BAO Zhen-shan, GUO Jun-nan, XIE Yuan and ZHANG Wen-bo. Model for Stock Price Trend Prediction Based on LSTM and GA [J]. Computer Science, 2020, 47(6A): 467-473.
[8] ZHU Lin-li, HUA Gang, GAO Wei. Stability Analysis of Ontology Learning Algorithm in Decision Graph Setting [J]. Computer Science, 2020, 47(5): 43-50.
[9] FU Kun, QIU Qian, ZHAO Xiao-meng, GAO Jin-hui. Event Detection Method Based on Node Evolution Staged Optimization [J]. Computer Science, 2020, 47(5): 96-102.
[10] YUAN Rong, SONG Yu-rong, MENG Fan-rong. Link Prediction Method Based on Weighted Network Topology Weight [J]. Computer Science, 2020, 47(5): 265-270.
[11] LI Xin-chao, LI Pei-feng, ZHU Qiao-ming. Knowledge Graph Representation Based on Improved Vector Projection Distance [J]. Computer Science, 2020, 47(4): 189-193.
[12] MA Yang, CHENG Guang-quan, LIANG Xing-xing, LI Yan, YANG Yu-ling, LIU Zhong. Improved SDNE in Weighted Directed Network [J]. Computer Science, 2020, 47(4): 233-237.
[13] JIAN Song-lei, LU Kai. Survey on Representation Learning of Complex Heterogeneous Data [J]. Computer Science, 2020, 47(2): 1-9.
[14] LIU Yun,YIN Chuan-huan,HU Di,ZHAO Tian,LIANG Yu. Communication Satellite Fault Detection Based on Recurrent Neural Network [J]. Computer Science, 2020, 47(2): 227-232.
[15] YANG Li, MA Jia-jia, JIANG Hua-xi, MA Xiao-xiao, LIANG Geng, ZUO Chun. Requirements Modeling and Decision-making for Machine Learning Systems [J]. Computer Science, 2020, 47(12): 42-49.
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .