DEVELOPMENT OF NODE WEIGHTED LINK PREDICTION METHODS IN COMPLEX NETWORKS

Abstract

ÖZET

Bağlantı tahmini, karmaşık ağlarda gelecekte ortaya çıkabilecek yeni bağlantıların tahmin edilmesinde kullanılmaktadır. Geçmişte birçok bağlantı tahmin yöntemi önerilmiştir. Önerilen yöntemlerin birçoğu ağın anlık topolojik yapısına ait bilgileri kullanmaktadır. Özellikle düğümler arasındaki ortak komşulara ait bilgiler kullanılarak benzerlik ölçümü yapan yöntemler, başarı oranlarının diğer yöntemlere göre yüksek olmasından dolayı tercih edilmektedir. Ayrıca dinamik ağlarda zaman içerisinde ağın topolojik yapısında meydana gelen değişiklikleri dikkate alarak düğümler arasında benzerlik ölçümü yapan yöntemler de önerilmiştir. Ancak hem statik hem de dinamik ağlar için önerilen yöntemler, tahmin işlemlerine düğümlerin ağdaki gücünü dahil etmemektedir. Düğümlerin zaman içerisinde ağda içerisindeki etkileşimlerinde meydana gelen değişimlerin ortaya çıkarılması düğümün gücünü tespit etmede önemlidir. Tahmin işlemlerinin topolojik faktörlerle sınırlandırılması tahminlerin başarısını olumsuz etkilemektedir. Özellikle dinamik ağlar için etkili olan ve topolojik bilgilerle ifade edilemeyen faktörlerin tahmin sürecine dahil edilmesi önemlidir. Düğümlerin ağdaki gücünü hesaplarken, topolojik bilgilerle birlikte zaman periyodu gibi düğümün ağdaki gücünü ölçebilecek faktörlerinde dikkate alınması tahmin başarısını artırıcı bir etken olmaktadır. Bu tez çalışmasında, bahsedilen problemlerin üstesinden gelmek için karmaşık ağlarda düğümlerin ağırlıklandırıldığı ve ağırlıklandırılmış düğümlerle etkili bağlantı tahmini yapabilen bir yöntem geliştirilmiştir. Geliştirilen yöntem hem ağdaki güçlü düğümleri tespit etmede hem de iki düğüm arasındaki bağlantı olasılığını hesaplamada ortak komşuların ağırlıklarını dikkate almaktadır. Düğümlerin ağırlıkları hesaplanırken zaman periyodu ve düğümlerin ağın gelişimine etkisini ifade eden faktörler dikkate alınmıştır. Ayrıca zaman periyodu ile birlikte merkezilik ölçütleri kullanılarak tahmin işlemlerinde karşılaştırmalar yapılmıştır. Geliştirilen yöntem, Avustralya Açık Tenis Turnuvalarından ve IEEE Xplore’daki yayınlardan oluşturulan gerçek dünya ağlarında test edilmiştir. Farklı zaman periyotlarından oluşturulan ağlarda yapılan deneysel çalışmalarda geliştirilen yöntemin ortak komşuların ilişkilerine dayalı mevcut bağlantı tahmin yöntemlerinden daha başarılı olduğu görülmüştür. Deneysel çalışmaların bir diğer sonucu da dinamik ağlarda merkezi düğümlerin tespiti için geliştirilen yöntemin geleneksel merkezilik ölçütlerinden daha başarılı olmasıdır.

ABSTRACT

Link prediction is used to predict new connections that may arise in the future in complex networks. Many link estimation methods have been proposed in the past. Most of the proposed methods use instantaneous topological information of the network. Especially methods that measure similarity between nodes using information about common neighbors are preferred because their success rates are higher than other methods. In addition, methods that measure similarity between nodes in dynamic networks, taking into account the changes in the topological structure of the network over time are also proposed. However, the proposed methods for both static and dynamic networks do not adequately predict the power of the nodes in the network. Revealing the changes that occur in the interaction of nodes within the network over time is important in determining the strength of the node. Limiting the prediction processes to topological factors negatively affects the success of the predicts. Especially in dynamic networks, it is important to include factors that are effective in the expansion of the network and cannot be expressed with topological information into the prediction process. When calculating the power of nodes in the network, considering the factors that can measure the power of the node in the network, such as the time period together with topological information, is a factor that increases the prediction success. In this thesis, in order to overcome the mentioned problems, a method in which nodes are weighted in complex networks and that can effectively predict connections with weighted nodes has been developed. The developed method considers the weights of common neighbors both in detecting strong nodes in the network and in calculating the connection probability between two nodes. While calculating the weights of the nodes, the time period and factors that express the effect of nodes on the development of the network were considered. In addition, comparisons were made in prediction processes by using centrality criteria with the time period. The developed method has been tested in real world networks created from Australian Open Tennis Tournaments and publications in IEEE Xplore. It has been observed that the method developed in the experimental studies performed on networks created from different time periods is more successful than the existing link prediction methods. Another result of experimental studies is that the method developed for the detection of central nodes in dynamic networks is more successful than traditional centrality meauserements.