Karmaşık ağlarda düğüm ağırlıklı bağlantı tahmin yöntemlerinin geliştirilmesi
Development of node weighted link prediction methods in complex networks
Yazar: EMRAH ÖZKAYNAK
Danışman: PROF. DR. OĞUZ FINDIK
Karabük Üniversitesi / Lisansüstü Eğitim Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2020
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Ö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 olarak 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. Tahmin işlemlerinin topolojik faktörlerle sınırlandırılması tahminlerin başarısını olumsuz etkilemektedir. Özellikle dinamik ağlarda ağın genişlemesinde 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örlerin de 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. 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.