Social network analysis

Abstract

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.