Discovering Link Prediction Methods' Performances by Network Topology Relation

Year 2022, , 778 - 788, 31.08.2022

Günce Keziban Orman

https://doi.org/10.35414/akufemubid.1127509

Abstract

One of the prominent topics in complex network analysis is link prediction, which is a key component of network-based recommendation systems or finding missing connections. There are several different link prediction methods in the literature based on measuring the likelihood of the existence of a link between two nodes. These methods use different topological properties of the network. Although there are methods using different strategies, previous studies have focused only on method success but have not adequately examined the relationship between the performance of these methods and the topology of the network. The main motivation for this study is to reveal the role of different network topologies in link prediction. Thus, the choice of link prediction method can be customized according to the topological characteristics of the network. The two main contributions of the study are, firstly, comparing different link prediction methods with well-known performance measures in social, biological, and information networks with different topological properties in a large experimental setup; and second, examining the possible relationship between the performance of link prediction methods and the network topology. Based on the experimental results, the global methods are more successful than others, regardless of the network topology. In addition, it was concluded that the high eigenvector centralization in the network may affect the missing link prediction performance.

Keywords

Link prediction, Performance evaluation, Network topology, Graph embedding

Ağ Topolojisi İlişkisi ile Bağlantı Tahmin Yöntemlerinin Performanslarının Keşfi

Abstract

Karmaşık ağ analizinde öne çıkan konulardan biri, ağ tabanlı öneri sistemlerinin veya eksik bağlantıların bulunmasının önemli bir bileşeni olan bağlantı tahminidir. Literatürde iki düğüm arasında bağlantı bulunma şansını ölçümlemeye dayanan birçok farklı bağlantı tahmini yöntemi vardır. Bu yöntemler ağın farklı topolojik özelliklerini kullanır. Çok farklı stratejiler kullanan yöntemler bulunmasına rağmen, önceki çalışmalar yalnızca yöntem başarısına odaklanmış ama bu yöntemlerin performansının ağın topolojisi ile ilişkisini yeteri kadar incelememiştir. Bu çalışmanın ana motivasyonu farklı ağ topolojilerininin bağlantı tahminindeki rolünü bir ortaya koymaktır. Böylece ağın topolojik özelliklerine göre bağlantı tahmin yöntemi seçimi özelleştirilebilir. Çalışmanın iki temel katkısı, ilk olarak, büyük bir deney düzeneğinde farklı topolojik özelliklere sahip sosyal, biyolojik ve bilgi ağlarında iyi bilinen performans ölçümleriyle farklı bağlantı tahmin yöntemlerini karşılaştırmak ve ikincisi, bağlantı tahmin yöntemlerinin performansı ile ağ topolojisi arasındaki olası ilişkinin incelenmesi olarak sıralanabilir. Sonuçlara göre, ağ topolojisine bakılmaksızın küresel yöntemlerin diğerlerinden daha başarılı olduğunu gördük. Ayrıca, ağda özvektör merkezileşmesinin yüksek olmasının eksik bağlantı tahmin performansını etkileyebileceği sonucuna ulaşıldı.

Keywords

Bağlantı tahmini, Performans değerlendirmesi, Ağ topolojisi, Graf gömme

References

• Adamic, L. A., & Adar, E., 2003. Friends and neighbors on the web. Social networks, 25, 211-230.
• Albert, R., & Barabási, A. L., 2002. Statistical mechanics of complex networks. Reviews of modern physics, 74, 47-97.
• Belkin, M., & Niyogi, P., 2001. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic (NIPS'01). MIT Press, Cambridge, MA, USA, 585–591.
• Cannistraci, C. V., Alanis-Lobato, G., & Ravasi, T., 2013. Minimum curvilinearity to enhance topological prediction of protein interactions by network embedding. Bioinformatics, 29, 199-209.
• Cannistraci, C. V., Alanis-Lobato, G., & Ravasi, T., 2015. From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks. Scientific reports, 3, 1-14.
• Clauset, A., Moore, C., & Newman, M. E., 2008. Hierarchical structure and the prediction of missing links in networks. Nature, 453, 98-101.
• De Sá, H. R., & Prudêncio, R. B., 2011. Supervised link prediction in weighted networks. The 2011 International Joint Conference on Neural Networks, IEEE, 2281-2288,
• Dice, L. R., 1945. Measures of the amount of ecologic association between species. Ecology, 26, 297-302. Gleiser, P. M., & Danon, L., 2003. Community structure in jazz. Advances in complex systems, 6, 565-573.
• Jaccard, P., 1912. The distribution of the flora in the alpine zone. 1. New phytologist, 11, 37-50.
• Kaya, B., 2020. Hotel recommendation system by bipartite networks and link prediction. Journal of Information Science, 46, 53-63.
• Kovács, I. A., Luck, K., Spirohn, K., Wang, Y., Pollis, C., Schlabach, S., ... & Barabási, A. L., 2019. Network-based prediction of protein interactions. Nature communications, 10, 1-8.
• Kuchaiev, O., Rašajski, M., Higham, D. J., & Pržulj, N., 2009. Geometric de-noising of protein-protein interaction networks. PLoS computational biology, 5, 1-10.
• Kunegis, J., 2013. Konect: the koblenz network collection. In Proceedings of the 22nd international conference on world wide web, 1343-1350.
• Liben‐Nowell, D., & Kleinberg, J., 2007. The link‐prediction problem for social networks. Journal of the American society for information science and technology, 58, 1019-1031.
• Li, J., Zhang, L., Meng, F., & Li, F., 2014. Recommendation algorithm based on link prediction and domain knowledge in retail transactions. Procedia Computer Science, 31, 875-881.
• Lü, L., & Zhou, T., 2011. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications, 390, 1150-1170.
• Lü, L., Pan, L., Zhou, T., Zhang, Y. C., & Stanley, H. E., 2015. Toward link predictability of complex networks. Proceedings of the National Academy of Sciences, 112, 2325-2330.
• Malhotra, D., & Goyal, R., 2021. Supervised-learning link prediction in single layer and multiplex networks. Machine Learning with Applications, 6, 1-9.
• Martínez, V., Berzal, F., & Cubero, J. C., 2016. A survey of link prediction in complex networks. ACM computing surveys, 49, 1-33.
• Newman, M. E., 2001. Clustering and preferential attachment in growing networks. Physical review E, 64, 1-13.
• Newman, M. E., 2003. The structure and function of complex networks. SIAM review, 45, 167-256.
• Rossi, R., & Ahmed, N., 2015. The network data repository with interactive graph analytics and visualization. In Twenty-ninth AAAI conference on artificial intelligence, AAAI Press, 4262-4293
• Rossi, A., Barbosa, D., Firmani, D., Matinata, A., & Merialdo, P., 2021. Knowledge graph embedding for link prediction: A comparative analysis. ACM Transactions on Knowledge Discovery from Data, 15, 1-49.
• Sørensen, T. J., 1948. A method of establishing groups of equal amplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on Danish commons. Kongelige Danske Videnskabernes Selskab Biologiske Skrifter, 5, 1-34.
• Tenenbaum, J. B., Silva, V. D., & Langford, J. C., 2000. A global geometric framework for nonlinear dimensionality reduction. Science, 290, 2319-2323.
• Wang, M., Qiu, L., & Wang, X., 2021. A survey on knowledge graph embeddings for link prediction. Symmetry, 13, 1-29.
• Watts, D. J., & Strogatz, S. H., 1998. Collective dynamics of ‘small-world’networks. Nature, 393, 440-442.
• Zareie, A., & Sakellariou, R., 2020. Similarity-based link prediction in social networks using latent relationships between the users. Scientific Reports, 10, 1-11.
• Zhou, T., Lü, L., & Zhang, Y. C., 2009. Predicting missing links via local information. The European Physical Journal B, 71, 623-630.