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
The spread of socialization in digital environments has led to the production of huge amounts of digital data. Many social network analysis methods have been developed to extract useful patterns from these data. These analysis methods offer solutions for all types of problems that can be modeled in the social network structure. There are many types of problems in social networks that are complex to solve. These types of problems, expressed as NP-hard, are difficult problems that cannot be solved in polynomial time. The problem of determining the minimum dominant set on any network or graph is one of the popular NP-hard problems. There is no effective algorithm in the literature for determining the minimum dominant set. In the literature, there are algorithms with a greedy approach that provide approximate solutions and take a long time to solve to determine the minimum dominant set. In this thesis, an effective algorithm that produces near-optimal results is proposed to determine the minimum dominating set members defined as NP-hard problems in the literature. The proposed dominating set algorithm consists of two important stages. In the first stage, Karcı centrality algorithm which gives priority to selection in determining the dominant set members was developed. In the second stage, the selection algorithm that detects the dominating set members was developed. Karci centrality algorithm is used to calculate the dominance values of nodes in any graph. Karci centrality algorithm consists of 3 sub-algorithms. The first algorithm is used to construct the Karcı maximum tree (Kmax Tree ), which is a spanning tree. The second algorithm is used to calculate the cut-set degrees by considering the Kmax tree. As a result of these cut-set operations, the results of how much the nodes removed from the graph affect the network are determined. The third algorithm produces the Karci centrality (dominance) value, which is a combination of graph node degrees, Kmax node degrees, and cut-set degrees. Besides pagerank, eigenvector, betweenness and closeness centrality algorithms, which are popularly known in the literature, were applied to real world problems and their successes were examined with comparative results in the study. In another application, the Karci centrality algorithm, which was originally developed, and the pagerank, eigenvector, closeness, degree centrality algorithms were compared. It has been concluded that the Karci centrality algorithm shows partial similarities with other popular algorithms in the literature. All stages and pseudo-codes of the proposed algorithms are given in detail in the thesis study. Keywords: Graph theory, Dominant node, Karci centrality, Dominating set
