Computer Science

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).

PDF (PC)

1371

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: Link prediction, Machine learning, Sign prediction, Signed networks, Structural balance theory

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] LENG Dian-dian, DU Peng, CHEN Jian-ting, XIANG Yang. Automated Container Terminal Oriented Travel Time Estimation of AGV [J]. Computer Science, 2022, 49(9): 208-214.
[2] NING Han-yang, MA Miao, YANG Bo, LIU Shi-chang. Research Progress and Analysis on Intelligent Cryptology [J]. Computer Science, 2022, 49(9): 288-296.
[3] SONG Jie, LIANG Mei-yu, XUE Zhe, DU Jun-ping, KOU Fei-fei. Scientific Paper Heterogeneous Graph Node Representation Learning Method Based onUnsupervised Clustering Level [J]. Computer Science, 2022, 49(9): 64-69.
[4] HUANG Li, ZHU Yan, LI Chun-ping. Author’s Academic Behavior Prediction Based on Heterogeneous Network Representation Learning [J]. Computer Science, 2022, 49(9): 76-82.
[5] LI Yao, LI Tao, LI Qi-fan, LIANG Jia-rui, Ibegbu Nnamdi JULIAN, CHEN Jun-jie, GUO Hao. Construction and Multi-feature Fusion Classification Research Based on Multi-scale Sparse Brain Functional Hyper-network [J]. Computer Science, 2022, 49(8): 257-266.
[6] ZHANG Guang-hua, GAO Tian-jiao, CHEN Zhen-guo, YU Nai-wen. Study on Malware Classification Based on N-Gram Static Analysis Technology [J]. Computer Science, 2022, 49(8): 336-343.
[7] HE Qiang, YIN Zhen-yu, HUANG Min, WANG Xing-wei, WANG Yuan-tian, CUI Shuo, ZHAO Yong. Survey of Influence Analysis of Evolutionary Network Based on Big Data [J]. Computer Science, 2022, 49(8): 1-11.
[8] CHEN Ming-xin, ZHANG Jun-bo, LI Tian-rui. Survey on Attacks and Defenses in Federated Learning [J]. Computer Science, 2022, 49(7): 310-323.
[9] XIAO Zhi-hong, HAN Ye-tong, ZOU Yong-pan. Study on Activity Recognition Based on Multi-source Data and Logical Reasoning [J]. Computer Science, 2022, 49(6A): 397-406.
[10] YAO Ye, ZHU Yi-an, QIAN Liang, JIA Yao, ZHANG Li-xiang, LIU Rui-liang. Android Malware Detection Method Based on Heterogeneous Model Fusion [J]. Computer Science, 2022, 49(6A): 508-515.
[11] LI Ya-ru, ZHANG Yu-lai, WANG Jia-chen. Survey on Bayesian Optimization Methods for Hyper-parameter Tuning [J]. Computer Science, 2022, 49(6A): 86-92.
[12] ZHAO Lu, YUAN Li-ming, HAO Kun. Review of Multi-instance Learning Algorithms [J]. Computer Science, 2022, 49(6A): 93-99.
[13] WANG Fei, HUANG Tao, YANG Ye. Study on Machine Learning Algorithms for Life Prediction of IGBT Devices Based on Stacking Multi-model Fusion [J]. Computer Science, 2022, 49(6A): 784-789.
[14] XU Jie, ZHU Yu-kun, XING Chun-xiao. Application of Machine Learning in Financial Asset Pricing:A Review [J]. Computer Science, 2022, 49(6): 276-286.
[15] LI Ye, CHEN Song-can. Physics-informed Neural Networks:Recent Advances and Prospects [J]. Computer Science, 2022, 49(4): 254-262.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.