计算机科学 ›› 2020, Vol. 47 ›› Issue (2): 21-30.doi: 10.11896/jsjkx.190600104

• 数据库&大数据&数据科学 • 上一篇    下一篇

符号网络链接预测算法研究综述

刘苗苗1,2,扈庆翠1,郭景峰3,陈晶3   

  1. (东北石油大学计算机与信息技术学院 黑龙江 大庆163318)1;
    (黑龙江省石油大数据与智能分析重点实验室 黑龙江 大庆163318)2;
    (燕山大学信息科学与工程学院 河北 秦皇岛066004)3
  • 收稿日期:2019-06-20 出版日期:2020-02-15 发布日期:2020-03-18
  • 通讯作者: 刘苗苗(liumiaomiao82@163.com)
  • 基金资助:
    国家自然科学基金项目(61602401,61871465);黑龙江省自然科学基金项目(LH2019F042);东北石油大学青年基金项目(2018QNQ-01)

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

中图分类号: 

  • 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] 宋杰, 梁美玉, 薛哲, 杜军平, 寇菲菲.
基于无监督集群级的科技论文异质图节点表示学习方法
Scientific Paper Heterogeneous Graph Node Representation Learning Method Based onUnsupervised Clustering Level
计算机科学, 2022, 49(9): 64-69. https://doi.org/10.11896/jsjkx.220500196
[2] 黄丽, 朱焱, 李春平.
基于异构网络表征学习的作者学术行为预测
Author’s Academic Behavior Prediction Based on Heterogeneous Network Representation Learning
计算机科学, 2022, 49(9): 76-82. https://doi.org/10.11896/jsjkx.210900078
[3] 冷典典, 杜鹏, 陈建廷, 向阳.
面向自动化集装箱码头的AGV行驶时间估计
Automated Container Terminal Oriented Travel Time Estimation of AGV
计算机科学, 2022, 49(9): 208-214. https://doi.org/10.11896/jsjkx.210700028
[4] 宁晗阳, 马苗, 杨波, 刘士昌.
密码学智能化研究进展与分析
Research Progress and Analysis on Intelligent Cryptology
计算机科学, 2022, 49(9): 288-296. https://doi.org/10.11896/jsjkx.220300053
[5] 李瑶, 李涛, 李埼钒, 梁家瑞, Ibegbu Nnamdi JULIAN, 陈俊杰, 郭浩.
基于多尺度的稀疏脑功能超网络构建及多特征融合分类研究
Construction and Multi-feature Fusion Classification Research Based on Multi-scale Sparse Brain Functional Hyper-network
计算机科学, 2022, 49(8): 257-266. https://doi.org/10.11896/jsjkx.210600094
[6] 张光华, 高天娇, 陈振国, 于乃文.
基于N-Gram静态分析技术的恶意软件分类研究
Study on Malware Classification Based on N-Gram Static Analysis Technology
计算机科学, 2022, 49(8): 336-343. https://doi.org/10.11896/jsjkx.210900203
[7] 何强, 尹震宇, 黄敏, 王兴伟, 王源田, 崔硕, 赵勇.
基于大数据的进化网络影响力分析研究综述
Survey of Influence Analysis of Evolutionary Network Based on Big Data
计算机科学, 2022, 49(8): 1-11. https://doi.org/10.11896/jsjkx.210700240
[8] 陈明鑫, 张钧波, 李天瑞.
联邦学习攻防研究综述
Survey on Attacks and Defenses in Federated Learning
计算机科学, 2022, 49(7): 310-323. https://doi.org/10.11896/jsjkx.211000079
[9] 李亚茹, 张宇来, 王佳晨.
面向超参数估计的贝叶斯优化方法综述
Survey on Bayesian Optimization Methods for Hyper-parameter Tuning
计算机科学, 2022, 49(6A): 86-92. https://doi.org/10.11896/jsjkx.210300208
[10] 赵璐, 袁立明, 郝琨.
多示例学习算法综述
Review of Multi-instance Learning Algorithms
计算机科学, 2022, 49(6A): 93-99. https://doi.org/10.11896/jsjkx.210500047
[11] 肖治鸿, 韩晔彤, 邹永攀.
基于多源数据和逻辑推理的行为识别技术研究
Study on Activity Recognition Based on Multi-source Data and Logical Reasoning
计算机科学, 2022, 49(6A): 397-406. https://doi.org/10.11896/jsjkx.210300270
[12] 姚烨, 朱怡安, 钱亮, 贾耀, 张黎翔, 刘瑞亮.
一种基于异质模型融合的 Android 终端恶意软件检测方法
Android Malware Detection Method Based on Heterogeneous Model Fusion
计算机科学, 2022, 49(6A): 508-515. https://doi.org/10.11896/jsjkx.210700103
[13] 王飞, 黄涛, 杨晔.
基于Stacking多模型融合的IGBT器件寿命的机器学习预测算法研究
Study on Machine Learning Algorithms for Life Prediction of IGBT Devices Based on Stacking Multi-model Fusion
计算机科学, 2022, 49(6A): 784-789. https://doi.org/10.11896/jsjkx.210400030
[14] 许杰, 祝玉坤, 邢春晓.
机器学习在金融资产定价中的应用研究综述
Application of Machine Learning in Financial Asset Pricing:A Review
计算机科学, 2022, 49(6): 276-286. https://doi.org/10.11896/jsjkx.210900127
[15] 李野, 陈松灿.
基于物理信息的神经网络:最新进展与展望
Physics-informed Neural Networks:Recent Advances and Prospects
计算机科学, 2022, 49(4): 254-262. https://doi.org/10.11896/jsjkx.210500158
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!