Karmaşık ağlarda hakim düğümlerin belirlenmesi için yeni bir yöntem

Dijital ortamlarda sosyalleşmenin yaygınlaşması devasa miktarlarda sayısal verilerin üretilmesine neden olmuştur. Bu verilerden faydalı örüntüler çıkarılması için birçok sosyal ağ analiz yöntemi geliştirilmiştir. Bu analiz yöntemleri sosyal ağ yapısında modellenebilen bütün problem türleri için çözümler sunmaktadır. Sosyal ağlarda çözümü karmaşık olan birçok problem türü vardır. NP-hard olarak ifade edilen bu problem türleri polinomsal zamanda çözülemeyen zor problemlerdir. Herhangi bir ağ veya çizge üzerindeki minimum hakim kümenin belirlenmesi problemi popüler NP-hard problemlerden birisidir. Minimum hakim kümenin(Minimum dominating set) belirlenmesi için literatürde etkili bir algoritma bulunmamaktadır. Literatürde minimum hakim kümenin belirlenmesi için çözümü uzun zamanlar alan açgözlü(greedy) yaklaşıma sahip ve yaklaşık çözümler sunan algoritmalar bulunmaktadır. Bu tez çalışmasında literatürde NP-hard problem olarak tanımlanmış minimum dominating set üyelerinin belirlenmesi için optimuma yakın sonuçlar üreten etkili bir algoritma önerilmiştir. Önerilen hâkim küme algoritması 2 önemli aşamadan oluşmaktadır. İlk aşamada hakim küme üyelerinin belirlenmesinde seçim önceliği veren Karcı merkezlilik algoritması geliştirilmiştir. İkinci aşamada hakim küme üyelerini tespit eden seçim algoritması geliştirilmiştir. Karcı merkezlilik algoritması herhangi çizgedeki düğümlerin baskın olma değerlerini hesaplamak için kullanılır. Karcı merkezlilik algoritması 3 alt algoritmadan oluşmaktadır. İlk algoritma bir kapsayan ağaç olan Karcı maksimum ağacını(Kmax Tree ) oluşturmak için kullanılır. İkinci algoritma Kmax ağacını göz önünde bulundurarak kesme derecelerinin hesaplanmasında kullanılmaktadır. Bu kesme işlemleri neticesinde çizgeden koparılan düğümlerin ağı ne kadar etkilediği sonuçları tespit edilmektedir. Üçüncü algoritma çizge düğüm derecesi, Kmax düğüm derecesi ve kesme derecelerinin birleşiminden oluşan Karcı merkezlilik(baskınlık) değerini üretir. Çalışmada ayrıca literatürde popüler olarak bilinen sayfa değeri, özvektör, arasındalık ve yakınlık merkezlilik algoritmaları gerçek dünya problemlerine uygulanmış ve başarıları karşılaştırmalı sonuçlar ile incelenmiştir. Diğer bir uygulamada özgün olarak geliştirilen Karcı merkezlilik algoritması ile sayfa değeri, özvektör, yakınlık, derece merkezlilik algoritmaları karşılaştırılmıştır. Karcı merkezlilik algoritmasının literatürdeki ix diğer popüler algoritmalar ile kısmi benzerlikler gösterdiği sonuçlarına ulaşılmıştır. Önerilen algoritmaların bütün aşamaları ve sözde kodları tez çalışmasında ayrıntılı olarak verilmiştir. Anahtar Kelimeler: Çizge teorisi, Baskın düğümler, Karcı merkezlilik, Hakim küme