Sosyal Ağlarda Topluluk Tespiti İçin Yeni Bir Algoritma: Ayrık Denge Optimizasyonu

Abstract

Modern ağ bilimi, karmaşık sistemleri anlamlandırmada önemli ilerlemeler sunmaktadır. Gerçek sistemleri temsil eden grafların en alakalı özelliklerinden biri topluluk yapısıdır. Bu tür topluluklar, örneğin insan vücudundaki dokular veya organlar gibi benzer bir rol oynayan, bir grafın oldukça bağımsız bölümleri olarak düşünülebilir. Topluluk tespiti (CD), sistemlerin genellikle graflarla temsil edildiği sosyoloji, biyoloji ve bilgisayar bilimlerinde büyük önem taşımaktadır. CD probleminin araştırılması birçok farklı algoritmayı motive etmesine rağmen, çoğu hesaplama maliyeti nedeniyle büyük ölçekli sosyal ağlar için uygun değildir. Ayrıca, olası topluluk yapılarını tanımlamanın yanı sıra, birçok pratik senaryoda keşfedilen toplulukların nasıl tanımlanacağı ve açıklanacağı da önemlidir. Bu tür gerekçelerde dolayı bu çalışmada klasik yöntemler yerine optimizasyon algoritmasının kullanılması tercih edilmiştir. Optimizasyon algoritması olarak ise son yıllarda geliştirilmiş olan Denge Optimizasyon (EO) Algoritması CD problemine uyarlanmıştır. EO temel versiyonu sürekli problemlerin çözümü üzerine önerildiğinden, ayrık bir problem olan CD problemi için EO yöntemi ayrık hale getirilmiştir. Deneysel çalışmalarda beş farklı sosyal ağ kullanılmıştır. Tüm çalışmalar adil bir kıyaslama yapabilmek için eşit koşullarda gerçekleştirilmiştir. EO algoritması iki farklı makalede yer alan önemli algoritmalarla çözüm kalitesi ve zaman açısından kıyaslanmıştır. Bu sonuçlara göre EO algoritmasının sosyal ağlarda CD probleminin çözümünde çok başarılı olduğu görülmüştür.

Modern network science offers significant advances in making sense of complex systems. One of the most relevant features of graphs representing real systems is the community detection. Such communities can be thought of as highly independent sections of a graph, playing a similar role, for example, tissues or organs in the human body. Community detection (CD) is of great importance in sociology, biology and computer science, where systems are often represented by graphs. Although the investigation of the CD problem motivates many different algorithms, most of them are not suitable for large-scale social networks due to computational cost. It is also important to identify possible community structures as well as how to identify and describe communities discovered in many practical scenarios. For such reasons, it was preferred to use the optimization algorithm instead of classical methods in this study. As an optimization algorithm, the Equilibrium Optimization (EO) Algorithm, which has been developed in recent years, has been adapted to the CD problem. Since the basic version of EO is proposed on the solution of continuous problems, the EO method is made discrete for the CD problem which is a discrete problem. Five different social networks were used in experimental studies. All studies were carried out under equal conditions in order to make a fair comparison. The EO algorithm was compared with the important algorithms in two different articles in terms of solution quality and time. According to these results, it has been seen that the EO algorithm is very successful in solving the CD problem in social networks.