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].https://doi.org/10.19734/j.issn.1001-3695.2018.07.0516.
[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] JIAN Song-lei,LU Kai. Survey on Representation Learning of Complex Heterogeneous Data [J]. Computer Science, 2020, 47(2): 1-9.
[2] 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.
[3] CHEN Xiao-jun, XIANG Yang. STransH:A Revised Translation-based Model for Knowledge Representation [J]. Computer Science, 2019, 46(9): 184-189.
[4] WANG Peng-yue, GUO Mao-zu, ZHAO Ling-ling, ZHANG Yu1,4. Review on Urban Air Quality Perception Methods [J]. Computer Science, 2019, 46(6A): 35-40.
[5] TIAN Zhen-kun, FU Ying-ying, LIU Su-hong. Remote Sensing Image Classification Based on Heterogeneous Machine Learning Algorithm Fusion [J]. Computer Science, 2019, 46(5): 235-240.
[6] SHU Na,LIU Bo,LIN Wei-wei,LI Peng-fei. Survey of Distributed Machine Learning Platforms and Algorithms [J]. Computer Science, 2019, 46(3): 9-18.
[7] WU Jie-hua,SHEN Jing,ZHOU Bei. Community Features Based Balanced Modularity Maximization Social Link Prediction Model [J]. Computer Science, 2019, 46(3): 253-259.
[8] XIE Nian-nian, ZENG Fan-ping, ZHOU Ming-song, QIN Xiao-xia, LV Cheng-cheng, CHEN Zhao. Android Malware Detection with Multi-dimensional Sensitive Features [J]. Computer Science, 2019, 46(2): 95-101.
[9] SHAN Na, LI Long-jie, LIU Yu-yang, CHEN Xiao-yun. Link Prediction Based on Correlation of Nodes’ Connecting Patterns [J]. Computer Science, 2019, 46(12): 20-25.
[10] LUO Xu-dong, HUANG Qiao-juan, ZHAN Jie-yu. A Survey of Automated Negotiation and Its Fuzzy Set Based Models [J]. Computer Science, 2019, 46(12): 220-230.
[11] ZHAO Zhong-tang, ZHENG Xiao-dong. Feature Incremental Extreme Learning Machine [J]. Computer Science, 2019, 46(11A): 112-116.
[12] DING Ya-san, GUO Bin, XIN Tong, WANG Pei, WANG Zhu, YU Zhi-wen. WiCount:A Crowd Counting Method Based on WiFi Channel State Information [J]. Computer Science, 2019, 46(11): 297-303.
[13] YANG Hai-min, PAN Zhi-song, BAI Wei. Review of Time Series Prediction Methods [J]. Computer Science, 2019, 46(1): 21-28.
[14] YANG Xu-hua, YU Jia, ZHANG Duan. Link Prediction Method Based on Local Community and Nodes’ Relativity [J]. Computer Science, 2019, 46(1): 155-161.
[15] CUI Yan-peng,SHI Ke-xing,HU Jian-wei. Research of Webshell Detection Method Based on XGBoost Algorithm [J]. Computer Science, 2018, 45(6A): 375-379.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] FAN Ji-li, LI Xiao-hua, NIE Tie-zheng, YU Ge. Survey on Smart Contract Based on Blockchain System[J]. Computer Science, 2019, 46(11): 1 -10 .
[2] WANG Xiao-xia, SUN De-cai. Q-sample-based Local Similarity Join Parallel Algorithm[J]. Computer Science, 2019, 46(12): 38 -44 .
[3] HUANG Meng-ting, ZHANG Ling, JIANG Wen-chao. Short Text Feature Expansion and Classification Based on Non-negative Matrix Factorization[J]. Computer Science, 2019, 46(12): 69 -73 .
[4] XU Shu-yan, HAN Li-xin, XU Guo-xia. Domain Adaptation Algorithm Based on Tensor Decomposition[J]. Computer Science, 2019, 46(12): 89 -94 .
[5] CHEN Zi-hao, LI Qiang. Improved PBFT Consensus Mechanism Based on K-medoids[J]. Computer Science, 2019, 46(12): 101 -107 .
[6] YIN Jia, GUAN Xin-jie, BAI Guang-wei. Task Offloading and Cooperative Load Balancing Mechanism Based on Mobile Edge Computing[J]. Computer Science, 2019, 46(12): 126 -131 .
[7] WANG Hui, ZHOU Ming-ming. Medical Information Security Storage Model Based on Blockchain Technology[J]. Computer Science, 2019, 46(12): 174 -179 .
[8] GAO Dan, LING Jie, CHEN Jia-hui. Two-dimensional Code Encryption Based on Revocable Outsourced Attribute Encryption[J]. Computer Science, 2019, 46(12): 186 -191 .
[9] WANG Yang, LI Peng, JI Yi-mu, FAN Wei-bei, ZHANG Yu-jie, WANG Ru-chuan, CHEN Guo-liang. High Performance Computing and Astronomical Data:A Survey[J]. Computer Science, 2020, 47(1): 1 -6 .
[10] XU Chuan-fu,WANG Xi,LIU Shu,CHEN Shi-zhao,LIN Yu. Large-scale High-performance Lattice Boltzmann Multi-phase Flow Simulations Based on Python[J]. Computer Science, 2020, 47(1): 17 -23 .