Ağırlıkların belirsiz olduğu çizge üzerinde topluluk tespiti: Sosyal ağ üzerinde bir çalışma
Community detection on a graph which weights are unknown: A case study on social network
Yazar: PELİN ÇETİN
Danışman: PROF. DR. ŞAHİN EMRAH
Ankara Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2022
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Grafikler = Graphics ; Karmaşık ağlar = Complex networks ; Topluluk yöntemleri = Community methods

Özet:
Karmaşık ağlar kişi veya nesneleri aralarındaki ilişkilerle birlikte gösteren yapılardır. Örneğin; insanlar, proteinler veya internet sayfaları aralarındaki etkileşimlerle beraber karmaşık ağ olarak modellenebilir. Karmaşık ağların analizi, sosyal ağlarda kişiye özel reklam vermek, protein ağlarında benzer proteinleri tespit etmek, arama motorlarında ilgili internet sayfalarını bulmak gibi bu ağı ortaya çıkaran probleme bağlı olarak farklı nedenlerden dolayı yapılmaktadır. Ancak karmaşık ağların büyüklüğü her ögeyi ilişkileri ile beraber incelemeyi zorlaştırmaktadır. Bu nedenle de karmaşık ağlar topluluk adı verilen alt ağlara ayrılarak incelenmektedir. Topluluk tespiti problemi, her üyenin en fazla bir toplulukta bulunduğu ayrık ve birden fazla toplulukta bulunduğu örtüşen topluluk tespiti olmak üzere iki sınıfa ayrılmaktadır.

Bu tezin amacı farklı topluluk yapılarını tespit eden yeni ve verimli algoritmalar önermektir. Yapılan çalışmada karmaşık ağlarda topluluk tespiti yapabilen mevcut algoritmalar incelenmiş, farklı benzerlik ölçütleri ile başlangıç toplulukları kullanmanın etkisi gözlemlenmiştir. Birçok ağda daha verimli olan ve farklı topluluk yapılarını tespit edebilen iki yeni ayrık ve örtüşen topluluk tespiti algoritması önerilmiştir. Önerilen algoritmalar birbirine benzeyen iki komşu üyenin aynı toplulukta bulunabileceği varsayımından yola çıkarak tasarlanmıştır. Algoritmaların başarılarını ölçmek için normalleştirilmiş ortak bilgi, F-skor, modülarite ve performans gibi farklı metriklerle birlikte, bu çalışmada örtüşen topluluklar için uyarlanan kapsama metriği kullanılmıştır. Önerilen algoritmalar gerçek ve sentetik ağlar üzerinde test edilmiş ve mevcut algoritmalarla karşılaştırılmıştır. Ayrık topluluk tespitinde toplulukların doğruluğu hedeflenirken, örtüşen topluluk tespitinde algoritmanın çalışma zamanı da dikkate alınarak başarılı sonuçlar elde edilmiştir.

Abstract:
Complex networks are structures that represent objects together with their relationships. The connections between people, proteins, and web pages can be modeled as complex networks. Complex networks are analyzed for different reasons depending on the problem that creates this network, such as giving personalized advertisements in social networks, detecting similar proteins in protein networks, and finding relevant web pages in search engines. However, the size of complex networks makes it difficult to examine each user or object individually with their relationships. Therefore, complex networks are examined by dividing them into sub-networks called communities. The community detection problem is divided into two classes: discrete, where each member is in at most one community, and overlapping, where there is more than one community.

In this thesis, new discrete and overlapping community detection algorithms that are more efficient in many networks and can detect different community structures are proposed. Existing algorithms are examined, and the effect of using initial communities and different similarity criteria is observed. Besides different metrics such as normalized mutual information, F-score, modularity, and performance, the coverage metric is adapted for overlapping communities in this study and used for measuring the success of the algorithms. The proposed algorithms are tested on real and synthetic networks and compared with existing algorithms. While the accuracy of the communities is taken into account in discrete community detection, the running time of the algorithm is also considered in overlapping community detection, and successful results are obtained for both algorithms.