research-article

Link prediction in multi-relational networks based on relational similarity

Authors:

Yun LiAuthors Info & Claims

Information Sciences—Informatics and Computer Science, Intelligent Systems, Applications: An International Journal, Volume 394, Issue C

Pages 198 - 216

https://doi.org/10.1016/j.ins.2017.02.003

Published: 01 July 2017 Publication History

Abstract

Presented a belief propagation method to calculate the belief of each node in a network.Proposed a measurement of influence between different types of relations using belief vectors.Presented a nonnegative matrix factorization based algorithm for link prediction in multi-relational networks.Theoretically proved the convergence and correctness of the proposed algorithm.Empirically demonstrated the proposed algorithm can achieve higher quality prediction results. Many real-world networks contain multiple types of interactions and relations. Link prediction in such multi-relational networks has become an important area in network analysis. For link prediction in multi-relational networks, we should consider the similarity and influence between different types of relations. In this paper, we propose a link prediction algorithm in multi-relational networks based on relational similarity. In the algorithm, a belief propagation method is presented to calculate the belief of each node and to construct the belief vector for each type of link. We use the similarity between belief vectors to measure the influence between different types of relations. Based on the influence between different relations, we present a nonnegative matrix factorization -based method for link prediction in multi-relational networks. The convergence and correctness of the presented method are proved. Our experimental results show that our method can achieve higher-quality prediction results than other similar algorithms.

References

[1]

N.M. Ahmed, L. Chen, An efficient algorithm for link prediction in temporal uncertain social networks, Inf. Sci., 331 (2016) 120-136.

Digital Library

[2]

W. Ahn, W.S. Jung, Accuracy test for link prediction in terms of similarity index: the case of WS and BA models, Physica A, 429 (2015) 177-183.

[3]

L.M. Aiello, A. Barrat, R. Schifanella, Friendship prediction and homophily in social media, ACM Trans. Web (TWEB), 6 (2012) 9.

Digital Library

[4]

Z.F. Bao, Y. Zeng, Y.C. Tay, sonLP: social network link prediction by principal component regression, in: Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, 2013.

Digital Library

[5]

N. Barbieri, F. Bonchi, G. Manco, Who to follow and why: link prediction with explanations, in: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2014, pp. 1266-1275.

Digital Library

[6]

M. Berlingerio, M. Coscia, F. Giannotti, A. Monreale, D. Pedreschi, Foundations of multidimensional network analysis, in: ASONAM, 2011, pp. 485-489.

Digital Library

[7]

M.H. Bhuyan, D.K. Bhattacharyya, J.K. Kalita, A multi-step outlier-based anomaly detection approach to network-wide traffic, Inf. Sci., 348 (2016) 243-271.

Digital Library

[8]

C.A. Bliss, M.R. Frank, C.M. Danforth, P.S. Dodds, An evolutionary algorithm approach to link prediction in dynamic social networks, J. Comput. Sci., 5 (2014) 750-764.

[9]

B. Bringmann, M. Berlingerio, F. Bonchi, A. Gionis, Learning and predicting the evolution of social networks, in: IEEE Intelligent Systems, 2010, pp. 26-34.

[10]

F. Buccafurri, L. Fotia, G. Lax, Analysis-preserving protection of user privacy against information leak age of social-network Likes, Inf. Sci., 328 (2016) 340-358.

Digital Library

[11]

F. Buccafurri, G. Lax, A. Nocera, D. Ursino, Discovering missing me edges across social networks, Inf. Sci., 319 (2015) 18-37.

Digital Library

[12]

B.L. Chen, L. Chen, B. Li, A fast algorithm for predicting links to nodes of interest, Inf. Sci., 329 (2016) 552-567.

Digital Library

[13]

D. Darcy, L. Ryan, N.V. Chawla, Multi-relational link prediction in heterogeneous information networks, in: Proceedings of 2011 International Conference on Advances in Social Networks Analysis and Mining, 2011, pp. 281-288.

Digital Library

[14]

J.Y. Ding, L.C. Jiao, J.S. Wu, Y.T. Hou, Y.T. Qi, Prediction of missing links based on multi-resolution community division, Physica A, 417 (2015) 76-85.

[15]

J. Fournet, A. Barrat, Contact patterns among high school students, PLoS One, 9 (2014).

[16]

S. Gao, L. Denoyer, P. Gallinari, Temporal link prediction by integrating content and structure information, in: Proceedings of CIKM11, 2011, pp. 1169-1174.

Digital Library

[17]

M.Q. Ge, A. Li, M.H. Wang, A bipartite network-based method for prediction of long non-coding RNAprotein interactions, Genomics Proteomics Bioinf., 14 (2016) 62-71.

[18]

R. Guimera, M. Sales-Pardo, Missing and spurious interactions and the reconstruction of complex networks, Proc. Natl. Acad. Sci., 106 (2010) 22073-22078.

[19]

Y.L. He, J.N.K. Liu, Y.-x. Hu, Xi-z. Wang, OWA operator based link prediction ensemble for social network, Expert Syst. Appl., 42 (2015) 21-50.

Digital Library

[20]

M. Hoffman, D. Steinley, M.J. Brusco, A note on using the adjusted Rand index for link prediction in networks, Soc. Netw., 42 (2015) 72-79.

[21]

F.Y. Hu, H.S. Wong, Labeling of human motion based on CBGA and probabilistic model, Int. J. Smart Sens. Intell. Syst., 6 (2013) 583-609.

[22]

N.M.A. Ibrahim, L. Chen, Link prediction in dynamic social networks by integrating different types of information, Appl. Intell., 42 (2015) 738-750.

Digital Library

[23]

B. Kaya, M. Poyraz, Age-series based link prediction in evolving disease networks, Comput. Biol. Med., 63 (2015) 1-10.

Digital Library

[24]

B. Kaya, M. Poyraz, Supervised link prediction in symptom networks with evolving case, Measurement, 56 (2014) 231-238.

[25]

B. Kaya, M. Poyraz, Unsupervised link prediction in evolving abnormal medical parameter networks, Int. J. Mach. Learn. Cybern., 7 (2016) 145-155.

[26]

P. Klimek, A.S. Jovanovic, R. Egloff, R. Schneider, Successful fish go with the flow: citation impact prediction based on centrality measures for termdocument networks, Scientometrics, 107 (2016) 1265-1282.

Digital Library

[27]

D.D. Lee, HS. Seung, Algorithms for non-negative matrix factorization, in: Proceeding of the 13th Advances in Neural Information Processing Systems, 2001, pp. 556-562.

[28]

J. Li, L.L. Zhang, F. Meng, F.H. Li, Recommendation algorithm based on link prediction and domain knowledge in retail transactions, Procedia Comput. Sci., 31 (2014) 875-881.

[29]

X. Li, H.C. Chen, Recommendation as link prediction in bipartite graphs: a graph kernel-based machine learning approach, Decis. Support Syst., 54 (2013) 880-890.

Digital Library

[30]

H. Liao, A. Zeng, Y.C. Zhang, Predicting missing links via correlation between nodes, Physica A. 436(2015) 216223.

[31]

W.P. Liu, L. L, Link prediction based on local random walk, Euro. Phys. Lett., 89 (2010) 58007.

[32]

L. L, C.H. Jin, T. Zhou, Similarity index based on local paths for link prediction of complex networks, Phys. Rev. E Stat. Nonlin. Soft Matter Phys., 80 (2009).

[33]

L.Y. L, T. Zhou, Link prediction in complex networks: a survey, Physica A, 390 (2011) 1150-1170.

[34]

X. Ma, J.L. Liao, S.M. Djouadi, Q. Cao, LIPS: link prediction as a service for data aggregation applications, Ad Hoc Netw., 19 (2014) 43-58.

[35]

L.J. Micha, S. Jaroszewicz, . Ostrowski, A. Wierzbicki, Verifying social network models of Wikipedia knowledge community, Inf. Sci., 339 (2016) 158-174.

Digital Library

[36]

A. Nigam, N.V. Chawla, Link Prediction in a Semi-bipartite network for recommendation, Lect. Notes Comput. Sci., 9622 (2016) 127-135.

[37]

A. Papadimitriou, P. Symeonidis, Y. Manolopoulos, Fast and accurate link prediction in social networking systems, J. Syst. Softw., 85 (2012) 2119-2132.

Digital Library

[38]

M. Pujari, R. Kanawati, Supervised Rank Aggregation Approach for Link Prediction in Complex Networks, in: Supervised Rank Aggregation Approach for Link Prediction in Complex Networks, 2012, pp. 1189-1196.

Digital Library

[39]

K. Saito, M. Kimura, K. Ohara, H. Motoda, Super mediator, A new centrality measure of node importance for information diffusion over social network, Inf. Sci., 329 (2016) 985-1000.

Digital Library

[40]

A.D. Sarma, A.R. Molla, G. Pandurangan, Distributed computation in dynamic networks via random walks, Theor. Comput. Sci., 58 (2015) 45-66.

Digital Library

[41]

E. Sherkat, M. Rahgozar, M. Asadpour, Structural link prediction based on ant colony approach in social networks, Physica A, 419 (2015) 80-94.

[42]

V. Stroele, G. Zimbrao, J.M. Souza, Group and link analysis of multi-relational scientific social networks, J. Syst. Softw., 86 (2013) 1819-1830.

Digital Library

[43]

Y. Sun, R. Barbery, M. Gupta, C.C. Aggarwal, J. Han, Co-author relationship prediction in heterogeneous bibliographic networks, in: Proceedings of 2011 International Conference on Advances in Social Networks Analysis and Mining, (ASONAM 2011), 2011, pp. 121-128.

Digital Library

[44]

Z. Sun, Q. Peng, J. Lv, A prediction model of post subjects based on information lifecycle in forum, Inf. Sci., 337-338 (2016) 59-71.

Digital Library

[45]

A. Vidmer, A. Zeng, M. Medo, Y.C. Zhang, Prediction in complex systems: the case of the international trade network, Physica A, 436 (2015) 188-199.

[46]

D.Q. Vu, A.U. Asuncion, D.R. Hunter, P. Smyth, Continuous-time regression models for longitudinal networks, in: Advances in Neural Information Processing Systems 24: Proceedings of the 25th Annual Conference on Neural Information Processing Systems, 2011, pp. 1-9.

Digital Library

[47]

P. Wang, B.W. Xu, Y.R. Wu, X.Y. Zhou, Link prediction in social networks: the state-of-the-art, Sci. China Inf. Sci., 58 (2015) 1-38.

[48]

X.J. Wang, X. Zhang, C.L. Zhao, Predicting link directions using local directed path, Physica A, 419 (2015) 260-267.

[49]

X.M. Wang, Y. Liu, F. Xiong, Improved personalized recommendation based on a similarity network, Physica A, 456 (2016) 271-280.

[50]

F. Xie, Z. Chen, J.X. Shang, X.P. Feng, J. Li, A link prediction approach for item recommendation with complex number, Knowl. Based Syst., 81 (2015) 148-158.

Digital Library

[51]

Yang Yang, Nitesh Chawla, Yizhou Sun, Jiawei Han, Predicting links in multi-relational and heterogeneous networks, 2012, in: IEEE 12th International Conference on Data Mining, 2012, pp. 756-764.

Digital Library

[52]

Z.Z. Zeng, Ke-Jia Chen, Shaobo Zhang, Haijin Zhang, A link prediction approach using semi-supervised learning in dynamic networks, in: Proceedings of Sixth International Conference on Advanced Computational Intelligence (ICACI), 2013, pp. 276-280.

[53]

L. Zhang, P.N. Suganthan, A survey of randomized algorithms for training neural networks, Inf. Sci., 364 (2016) 146-155.

Digital Library

[54]

http://www.linkprediction.org/index.php/link/resource/data.

[55]

http://symatlas.gnf.org.

[56]

http://www.cgd.ucar.edu/cas/catalog/climind/.

Cited By

Wang HLiu RShi CChen JFang LLiu SGong Z(2023)Resisting the Edge-Type Disturbance for Link Prediction in Heterogeneous NetworksACM Transactions on Knowledge Discovery from Data10.1145/361409918:2(1-24)Online publication date: 7-Aug-2023
https://dl.acm.org/doi/10.1145/3614099
Li JLiu LShu J(2022)Progresses in Link Prediction: A SurveyProceedings of the 2022 11th International Conference on Computing and Pattern Recognition10.1145/3581807.3581903(651-655)Online publication date: 17-Nov-2022
https://dl.acm.org/doi/10.1145/3581807.3581903
Li JPeng XWang JZhao N(2021)A Method for Improving the Accuracy of Link Prediction AlgorithmsComplexity10.1155/2021/88894412021Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1155/2021/8889441
Show More Cited By

Index Terms

Link prediction in multi-relational networks based on relational similarity
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Predicting Links in Multi-relational Networks
JISIC '14: Proceedings of the 2014 IEEE Joint Intelligence and Security Informatics Conference

Most traditional methods of link prediction in networks deal with homogeneous networks, i.e., networks with a single type of nodes and a single type of relationships. However, most real-life systems modelled by networks comprise multiple types of ...
Dynamic Multi-relational Networks Integration and Extended Link Prediction Method
IScIDE 2015: Revised Selected Papers, Part II, of the 5th International Conference on Intelligence Science and Big Data Engineering. Big Data and Machine Learning Techniques - Volume 9243

Link prediction is an effective method in complex networks analysis, not only in simple networks but also in dynamic multi-relational ones. How to integrate these multi-relational networks is of great importance to link prediction results. In this paper, ...
Link prediction using time series of neighborhood-based node similarity scores

We propose a link prediction method for evolving networks. Our method first computes a number of different node similarity scores (e.g. Common Neighbor, Preferential Attachment, Adamic---Adar, Jaccard) and their weighted versions, for different past ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information Sciences: an International Journal

Information Sciences: an International Journal Volume 394, Issue C

July 2017

295 pages

ISSN:0020-0255

Issue’s Table of Contents

Copyright © Elsevier Inc.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 01 July 2017

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang HLiu RShi CChen JFang LLiu SGong Z(2023)Resisting the Edge-Type Disturbance for Link Prediction in Heterogeneous NetworksACM Transactions on Knowledge Discovery from Data10.1145/361409918:2(1-24)Online publication date: 7-Aug-2023
https://dl.acm.org/doi/10.1145/3614099
Li JLiu LShu J(2022)Progresses in Link Prediction: A SurveyProceedings of the 2022 11th International Conference on Computing and Pattern Recognition10.1145/3581807.3581903(651-655)Online publication date: 17-Nov-2022
https://dl.acm.org/doi/10.1145/3581807.3581903
Li JPeng XWang JZhao N(2021)A Method for Improving the Accuracy of Link Prediction AlgorithmsComplexity10.1155/2021/88894412021Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1155/2021/8889441
Liu YShen DKou YNie T(2019)Link Prediction Based on Node Embedding and Personalized Time Interval in Temporal Multi-relational NetworkWeb Information Systems and Applications10.1007/978-3-030-30952-7_40(404-417)Online publication date: 20-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-30952-7_40
Chen XLi XDeng YChen SGao C(2019)A New Multi-objective Evolution Model for Community Detection in Multi-layer NetworksKnowledge Science, Engineering and Management10.1007/978-3-030-29551-6_18(197-208)Online publication date: 28-Aug-2019
https://dl.acm.org/doi/10.1007/978-3-030-29551-6_18
Gao MChen LLi BLiu W(2018)A link prediction algorithm based on low-rank matrix completionApplied Intelligence10.1007/s10489-018-1220-448:12(4531-4550)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1007/s10489-018-1220-4

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents