A Comprehensive Review of Similarity Based Link Prediction Methods for Complex Networks including Computational Biology
Main Article Content
Abstract
Information retrieval is one of the most challenging tasks for the mankind and to retrieve information interaction is required, which ultimately leads to the formation of networks. Universe is packed with different type of networks. Networks with complex topological properties are called complex network. Such types of networks are major tools for learning the connection between the organizations and finding the purpose of complex systems. The link prediction problems in complex networks facilitate predictions about the future organization of the network. Network is represented as a graph. The data in the network is signified by nodes, and the relations are represented by links. The future of non-connected links amid node pairs is predicted. This paper reviews the methods used to predict links for complex networks using similarity-based heuristics. Previous reviews, despite having a clear outline of the link prediction study, only described the prediction approaches. Research gaps between the similarity-based link prediction techniques, however, were not explicitly stated. With the help of chronological findings and a research gaps approach, this review seeks to give a continuing review and introduce the link prediction.
Downloads
Article Details
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
Estrada, E., 2014, ‘Introduction To Complex Networks: Structure And Dynamics’, Book Chapter,www.Estradalab.Org › Uploads › 2015/10 › Bookchapter_11
Gupta, A., ‘Analysis and Improvement of Link Prediction Techniques in Online Social Networks’, Doctoral Dissertation, Jaypee Institute Of Information Technology (Declared Deemed To Be University), Noida, India, July 2020, https://shodhganga.inflibnet.ac.in /handle/10603/295019
Bellotti, R., 2018,‘Complex network-based quantitative methods applied to the study of neurodegenerative disease’, Università Degli Studi Di Bari, http://phdphysics.cloud.ba.infn.it/wp- content/uploads/ 2018/03/la_rocca_tesi-compressed.pdf
Liben-Nowell, D., Kleinberg, J., ‘The Link Prediction Problem for Social Networks’, Journal of The American Society for Information Science and Technology, 58(7):1019–1031, (May 2007).
Daud. N., Hamid,S.et al., 2020, ‘Applications of link prediction in social network: A review’, Journal of
Network and Computer Applications ( IF 5.570 ) Pub Date : 2020-05-21 , DOI:
1016/j.jnca.2020.102716
Euler, L., 1741, ‘Solutioproblematisadgeometriamsituspertinentis’, Commentarii academiaescientiarum Petropolitanae, Volume 8, pp. 128-140.
Jaccard, P., 1901. “Etude Comparative De La Distribution FloraleDansUne Portion Des Alpes Et. Des Jura”, Bulletin Del La Soci´Et.´EVaudoise Des Sciences Naturelles, Vol. 37, Pp. 547–579, 1901 (In French)
Erdős, P. Rényi, A., 1960,‘On The Evolution Of Random Graphs’, Magyar Tudományos Akadémia Matematikai KutatóIntézetének Kőzleményei [Publications Of The Mathematical Institute Of The Hungarian Academy Of Sciences]. 5: 17–61
Watts, D, Strogatz, S., 1998, Small World, Nature, 393:440-442
Milgram S, 1967, ‘The Small World Problem’, Psychology Today, Vol. 2, Pp. 60–67, 1967.
Travers J, Milgram S, 1969, ‘An Experimental Study of the Small World Problem’, Sociometry, Vol. 32, No. 4, Pp. 425–443, 1969.
Faloutsos, M, Faloutsos C. et al., 1999, ‘On Power-Law Relationships Of The Internet Topology’, ACM SIGCOMM Computer Communication Review, August 1999, Https://Doi.Org/10.1145/316194.316229.
Brin, S.& Page,L., 1998, ‘The Anatomy of a Large-Scale Hypertextual Web Search Engine’ Computer Networks, vol. 30, pp. 107-117
Barabási A, Albert A,1999, ‘Emergence of scaling in random networks’, AAAS-American Association For The Advancement Of Science, Science , Oct 1999: Vol. 286, Issue 5439, Pp. 509-512, DOI: 10.1126/Science.286.5439.509
Newman, M., 2001, ‘Clustering And Preferential Attachment In Growing Networks’ Physical Review E, 64.
Jeh, G. & Widom, J., 2002, ‘Simrank’,Proceedings of The Eighth ACM SIGKDD International Conference on Knowledge Discovery And Data Mining - KDD '02,ACM Press.
Ravasz, E., Somera, L. et al., 2002, ‘Hierarchical organization of modularity in metabolic networks,’ Science, vol. 297, no. 5586, pp. 1551–1555, 2002.
Liben-Nowell, Kleinberg, 2003, 'The Link Prediction Problem For Social Networks', Proceedings Of The
Twelfth International Conference On Information And Knowledge Management, 3-8 November 2003, Pp. 556-559
Adamic & Adar , 2003, “Friend and Neighbors On The Web” Social Networks, Networks, 2003, 25: 211{230
Taskar, B., Wonng M. et al. 2003, 'Label And Link Prediction In Relational Data', Proceedings Of The IJCAI Workshop On Learning Statistical Models From Relational Data, 11 August 2003.
Popescul, A, Ungar, L, 2003, 'Structural Logistic Regression For Link Analysis', Proceedings Of KDD Workshop On Multi-Relational Data Mining, 2003, http://www.cis.upenn.edu/~popescul/publications/popescul03mrdm .pdf.
Zhou, D., Scholkopf, B, 2004, 'A Regularization Framework for Learning from Graph Data', Proceedings of Workshop on Statistical Relational Learning’, International Conference on Machine Learning, Banff, 12 June 2006, http://www.cs.umd.edu/projects/srl2004/papers/zhou.pdf.
Popescul, A., Ungar, L., 2004, 'Cluster-Based Concept Invention For Statistical Relational Learning', Proceedings Of Conference Knowledge Discovery And Data Mining (KDD-2004), 22-25 August 2004, Viewed 12 June 2006
Getoor, L.& Diehl, C., 2005, ‘Link Mining: A Survey’, ACM SIGKDD Explorations Newsletter, Vol. 7, Issue 2, Pp 3-12.
Leicht, E., Holme, P. et al., 2006, ‘Vertex Similarity In Networks’, Physical Review E, 2006, 73: 026120
Sørensen T., 1948, ‘A Method of Establishing Groups of Equal Amplitude in Plants Ociology Based on Similarity of Species and Its Application to Analyses of The Vegetation on Danish Commons’, vol. 5 of BiologiskeSkrifter, E. Munksgaard, 1948.
Berkhout J, 2016, “Google's Pagerank Algorithm For Ranking Nodes In General Networks”, IEEE, 2016
th International Workshop On Discrete Event Systems (WODES)
Page, L., 1999, ‘The PageRank Citation Ranking: Bringing Order to the Web’, WWW 1999
Ou, Q., Jin, Y. et al.,2007, ‘Power-Law Strength-Degree Correlation From Resource-Allocation Dynamics On Weighted Networks’ Phys. Rev. E, 75:021102, 2007. Doi: 10.1103/Physreve.75.021102. http://Dx.Doi.Org/10.1103/Physreve.75.021102.
Fouss, F., Pirotte A. et al., 2007, ‘Random-Walk Computation of Similarities between Nodes of A Graph with Application to Collaborative Recommendation’, IEEE Transactions on Knowledge and Data Engineering, 19, 355-369.
Lu, L., Jin, C. et al., 2009 ‘Similarity Index Based On Local Paths for Link Prediction of Complex Networks’, Physical Review E, 80: 046122
Zhou, T., Lu, L.et al., 2009, ‘Predicting Missing Links via Local Information’, The European Physical Journal B, 2009, 71: 623{630
Katz L, 1953, ‘New Status Index Derived From Sociometric Analysis’, Psychometrika, 1953, 18: 39{43138{143
Lichtenwalter, R., Lussier, J. et al., ‘New Perspectives and Methods in Link Prediction’, Proceedings ofthe 16th ACM SIGKDD International Conference On Knowledge Discovery And Data Mining, 2010. 243{252
Sarkar, P. Chakrabarti,D. et al, 2011, ‘Theoretical Justification of Popular Link Prediction Heuristics’,
Proceedings of the 22nd International Joint Conference on ArtiCial Intelligence, Barcelona, Spain, 2011. 2722-27276
Lü, L. and Zhou T, 2011, ‘Link prediction in complex networks: a survey,’ Physica A: Statistical Mechanics and Its Applications, vol. 390, no. 6, pp. 1150–1170, 2011.
Lichtenwalter R, Chawla N, 2012, ‘Vertex Collocation Pro_Les: Subgraph Counting For Link Analysis And Prediction’, Proceedings Of The 21st World Wide Web Conference (WWW'12), Lyon, France, 2012. 1019{1028
Papadimitriou, A.,Symeonidis, P. et al., 2012, ‘Fast And Accurate Link Prediction In Social Networking Systems’, Journal of Systems and Software, 2012, 85: 2119{2132
Chen, H., Liang, G.et al.,2012”, ‘Discovering Missing Links In Networks Using Vertex Similarity Measures’, Proceedings Of The Twenty-Seventh Annual ACM Symposium On Applied Computing (SAC'12), Trento, Italy, 2012.
Zhu, Y., Lu, L.et al.,2012, ‘Uncovering Missing Links With Cold Ends’, Physica A, 2012, 391: 5769{5778.
Chen, X., Xia, M. et al., 2016 ‘Trend Prediction of Internet Public Opinion Based on Collaborative Filtering’, Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD), 12th International Conference On, 2016. IEEE, 583-588
Martínez, V., Berzal, F. et al., 2016, ‘A Survey of Link Prediction In Complex Networks’, ACM Computing Surveys (CSUR), 49, 69.
Srilatha, P. & Manjula, R., 2016, ‘Similarity Index Based Link Prediction Algorithms In Social Networks: A Survey’, Journal of Telecommunications and Information Technology, 2016 | nr 2 | 87--94
Zeng, S., 2016, ‘Link Prediction Based On Local Information Considering Preferential Attachment’, Physica A: Statistical Mechanics And Its Applications, 443, 537-542.
Jia, Y. & Qu, L., 2016, ‘Improve The Performance Of Link Prediction Methods In Citation Network By
Using H-Index’, Cyber-Enabled Distributed Computing And Knowledge Discovery (Cyberc), 2016 International Conference On, 2016. IEEE, 220-223. (ANT 2016), Published By Elsevier B
Mohan, A.,Venkatesan, R. et al., 2017, ‘A scalable method for link prediction in large real world
networks’, Journal of Parallel and Distributed Computing, http://dx.doi.org/10.1016/j.jpdc.2017.05.009
Nandi ,G., & Das, A., 2018, ‘An Efficient Link Prediction Technique in Social Networks based on Node Neighborhoods’, (IJACSA) International Journal of Advanced Computer Science and Applications, Vol. 9, No. 6, 2018
Zhou, K., Michalak,T. et al., 2019, ‘Adversarial Robustness of Similarity-Based Link Prediction’, IEEE International Conference on Data Mining (ICDM), Nov,2019,added to IEEE Xplore: 30 January 2020.
Iftikhar, A., Akhtar, A. et al., 2020, ‘Missing Link Prediction using Common Neighbor and Centrality based Parameterized Algorithm’, Nature Research, Scientific Reports, Sci Rep 10, 364 (2020). https://doi.org/10.1038/s41598-019-57304-y
Wang, X., Chai, Y. ,et al., 2021, ‘Link prediction in heterogeneous information networks: An improved deep graph convolution approach’, Elsevier, Decision Support Systems, Volume 141, February 2021, 113448, https://doi.org/10.1016/j.dss.2020.113448
Longjie et al. ‘Towards Effective Link Prediction: A Hybrid Similarity Model’, Journal of Intelligent & Fuzzy Systems, vol. 40, no. 3, pp. 4013-4026, 2021
Szyman, P. & Barbucha, D., 2022, ‘Link prediction in organizational social network based on e-mail communication’, Proceedings of the 26th International Conference on Knowledge-Based and Intelligent Information & Engineering Systems (KES 2022)
Zhao, Z et al, Link Prediction with Hypergraphs via Network Embedding. Appl. Sci. 2023, 13, 523. https://doi.org/10.3390/app13010523
Blöcker, C. et al, Similarity-based link prediction from modular compression of network flows, in the Proceedings of the Machine Learning Research Press (Vol. 198, pp. 1-18), 2023. https://proceedings.mlr.press/v198/blocker22a/blocker22a.pdf