Social network analysis
Özet
Finding possible maximal cliques in a given graph is one of the basic problems of graph theory. Although the enumeration of maximal cliques in a graph is an NP-hard problem, various algorithms and novel methods for this problem have been proposed. In some application’s largest possible maximal cliques i.e. maximum cliques play an important role. This study proposes a new algorithm that finds maximum cliques in a graph. The proposed algorithm is applied to different real-world datasets to find them. Moreover, this study proposes two versions of the algorithm; one finds all possible maximum cliques, and the other finds only one maximum clique in a given graph. To evaluate the performance, the results of the proposed study are compared with the well-known Born Kerbosch algorithm. As a result, it is found that the proposed algorithm performs better than the Born Kerbosch method.
Keywords- Verilen bir çizgede olası maksimum klikleri bulmak, çizge kuramının temel
problemlerinden biridir. Bir çizgede maksimal kliklerin numaralandırılması NP-zor bir
problem olsa da, bu problem için çeşitli algoritmalar ve yeni yöntemler önerilmiştir. Bazı
uygulamalarda mümkün olan en büyük maksimal klikler, yani maksimum klikler, önemli
bir rol oynar. Bu çalışma, bir çizgede maksimum klikler bulan yeni bir algoritma
önermektedir. Önerilen algoritma, onları bulmak için farklı gerçek dünya veri kümelerine
uygulanır. Ayrıca bu çalışma, algoritmanın iki versiyonunu önermektedir; biri tüm olası
maksimum klikleri bulur ve diğeri belirli bir grafikte yalnızca bir maksimum klik bulur.
Performansı değerlendirmek için, önerilen çalışmanın sonuçları iyi bilinen Bron
Kerbosch algoritması ile karşılaştırılır. Sonuç olarak, önerilen algoritmanın Bron
Kerbosch yönteminden daha iyi performans gösterdiği görülmüştür.