Büyük ölçekli iki parçalı karmaşık ağlarda güçlendirilmiş yansıma modeline dayalı bağlantı tahmini yöntemleri
Link prediction methods based on strengthening projection model in large-scale bipartite networks
Yazar: SERPİL ASLAN
Danışman: PROF. DR. MEHMET KAYA
Fırat Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2018
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Gerçek dünya verilerinden oluşturulmuş birçok karmaşık ağ, doğası gereği iki parçalı bir yapıya sahiptir. İki parçalı ağlar, gerçek dünya sistemlerinin karmaşık yapısı hakkında önemli fikirler veren, farklı düğüm grupları arasındaki etkileşimleri temsil eden karmaşık bir ağ türüdür. Son zamanlarda, özellikle büyük ölçekli, karmaşık ağlarda bağlantı tahmini çalışmaları farklı bilim alanlarındaki araştırmacılar için ilgi odağı haline gelmiştir. Birçok gerçek dünya sistemi gibi akademik bilgi ağları da iki parçalı bir yapıya sahiptir. Akademik bilgi ağları sürekli değişen ve gelişen bir yapıdadır. Bu ağlarda, yazarlara kendi alanlarına uygun popüler konu başlıklarını tavsiye eden bir sistemin bulunması araştırmacıların işini kolaylaştıracaktır. Son zamanlarda, akademik konuların yazarlara önerilmesine yönelik yapılan birçok çalışma, problemi bağlantı tahmini olarak ele almıştır. Bu çalışmalardan sadece birkaçı, yüksek pratik ilgisine ve üstesinden geldiği belirli zorluklara rağmen iki parçalı ağları kullanmaktadır. İki parçalı ağlarda bağlantı tahmini alanında yapılan önceki çalışmaların çoğu, düğüm çiftleri arasındaki ilişkileri tahmin etmek için iki parçalı ağdan çıkartılan geleneksel tek parçalı ağların özelliklerini kullanmaya odaklanmıştır. Geleneksel projeksiyon yöntemleri, gerçek dünya verilerinden oluşturulan ağlarda kullanıldığında zayıf ilişkilere sahip birçok düğüm çifti içerebilir. Bu zayıf ve gereksiz bilgilerin analizi yüksek hesaplama zamanına neden olur. Bu problemlere bir çözüm olarak, bu çalışmada klasik tek parçalı yöntemlere dönüştürmek yerine ağın omurgası niteliğini taşıyan güçlendirilmiş tek parçalı ağ modeli önerilmiştir. Daha sonra, ağdaki potansiyel bağlantıları tahmin etmek için güçlendirilmiş tek parçalı ağ modeline dayalı benzerlik tabanlı bir tavsiye edici yöntem geliştirilmiştir. Son olarak, önerilen yöntemle elde edilen potansiyel bağlantıların kalitesini değerlendirmek amacıyla zamandan bağımsız ve zaman farkındalı olmak üzere iki yeni yakınlık ölçütü algoritması önerilmiştir. Önerilen yöntemler, IEEE Xplorer çevrimiçi kütüphanesinden toplanan verilerle oluşturduğumuz ağ üzerinden test edilmiştir. Gerçek bir ağ üzerinde yapılan deneyler, önerilen yöntemin başarısının umut verici olduğunu ve büyük ölçekli bir ağdan hızlı ve yüksek kaliteli bağlantı tahmini sonuçları elde etmenin mümkün olduğunu göstermektedir.

Anahtar Kelimeler:  İki Parçalı Ağlar, Karmaşık Ağ Analizi, Bağlantı Tahmini, Akademik Konu Önerisi, Güçlendirilmiş Tek Parçalı Ağ, Zaman-farkındalı Yakınlık Ölçütü

Abstract:
Many complex networks created from the real-world data are bipartite structured by nature. Bipartite networks give important ideas about the complex nature of the real-world systems, they are also complex network types that represent the interactions between the different node groups. Recently, the link prediction studies on large-scale and complex networks have particularly become the focus of interest for researchers in various scientific fields. They have a constantly changing and evolving structure. A system that would propose popular topic titles among these networks that are related with an author's fields of work would simplify the work of many researchers. Recently, a lot of work has been done which address recommending academic topics to authors as a link prediction problem. Only a few of these studies use the bipartite networks despite its high practical interest and the specific challenges it raises. The majority of the previous works on the link prediction in bipartite networks focus on using the properties of traditional unimodal projection networks to predict the relations between the node pairs. The traditional projection methods involve many node pairs with weak relationships when used in networks constructed from real-world data. The analysis of these weak and unnecessary information requires high computation time. To cope with this problems, we proposed in this study the notion of strengthening projection networks which is the backbone of the network instead of traditional unimodal projection networks in bipartite graphs. Then, a link prediction method based on strengthening projection network have been developed to predict the potential links. Finally, two new proximity measure algorithms such as time-aware proximity measure algorithm and time-ignored proximity measure algorithm was proposed to evaluate the quality of the potential link. We test the proposed method on the academic information bipartite network constructed with collected data from IEEE XPlorer. Experiments on a real network demonstrate that the success of the proposed method is promising and it is possible to obtain fast and high-quality link prediction results from a large-scale network.

Key Words: Bipartite Networks, Complex Network Analysis, Link Prediction, Academic Topic Recommendation, Strengthening Weighted Projection, Time-aware Proximity Measure