RnR: Reduce and Raise - Bottom-Up Community Detection in Bipartite and Tripartite Graphs

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2019

Tezin Dili: İngilizce

Öğrenci: KADİR EKMEKCİ

Eş Danışman: GÖKTÜRK ÜÇOLUK, İSMAİL HAKKI TOROSLU

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Özet:

Bu tezde, iki parçalı yakın-klik bulma ve üç parçali yakın-klik bulma problemlerine özgün ve hızlı bir yaklaşım sunuyoruz. Klik bulma probleminin $NP-zor$ olduğu kanıtlandı. Bu problemi çözmek için birçok buluşsal algoritma ve degisik yaklasimlar sunuldu. Bizim yaklaşımımız diğer yöntemlerden şu şekilde ayrışmaktadır: Bizim algoritmamız yüksek dereceli düğümlerin bir arada toplandığı yakın-klikleri bulmayı amaçlıyor. Hız için kaliteden ödün verdigimiz bu tezde yedi tane özgün algoritmayı kıyaslayıp, açıklıyoruz. Bu algoritmalar, varolan bir algoritma olan Louvain metodu kullanılarak geliştirilmişlerdir. Louvain metodu modüler-bazlı bir komünite bulma algoritmasıdır. Algoritmalarımızı bilgisayar ile üretilmiş çizgelerle test ettik. Gözlemlerimize göre, algoritmalarımız yoğun bölgeleri olan ve seyrek çizgelerde daha iyi çalışıyor.