Discovering link prediction methods' performances by network topology relation

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.

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