Community detection in complex networks

Abstract

Etkileşim halindeki nesneleri düğümler ve aralarındaki ilişkiyi de bağlantılar kullanarak modelleyen karmaşık ağlar geçtiğimiz on yılda çok ilgi çekmeye başladı. Birbirleriyle daha sıkı ilişki halinde olan grupları saptamayı kapsayan komün arama, karmaşık ağ analizinin önemli bir alt dalı olarak karşımıza çıkmakta. Araştırmacılar, algoritmalarını test etmek için, yapay olarak yaratılmış ağları kullanmaktadırlar. Bu çalışmada, bilgisayarla yaratılmış olan yapay ağların gerçeklik düzeylerinin, algoritmaların komün arama performansları üzerindeki etkilerini araştırdık. Öncelikle, Lancichinetti et al. model, şimdiye kadar sunulmuş en gerçekçi model, kullanılarak oluşturduğumuz ağların özelliklerini inceledik. Sonrasında, bu modelin gerçeklik düzeyini artırmak için bazı değişiklikler yaptık ve sonuçları topolojik olarak inceledik. Yaptığımız değişiklikler, belirgin biçimde gerçeklik düzeyini artırdı ve özellikle modelin kararlılığını güçlendirdi. Daha sonra, çeşitli kategorilerden seçilmiş on bir komün tarama algoritmasını hem orijinal hem değiştirilmiş modellerle yaratılan ağlar üzerinde test ettik. Performans analizi bize, algoritmaların karşılaştırmalı değerlerinin, gerçeklik düzeyinden çok fazla etkilenmediğini gösterdi, ancak tek tek algoritmalar incelendiğinde, belirgin değişiklikler oluştuğunu gördük. Özellikler, artan gerçeklik düzeyinin, tüm algoritmalarda performans düşüşü yarattığını yani, komün belirleme işlemini zorlaştırdığını gördük.

Complex networks have become very popular since the last decade. They allow modeling a given system by representing its components and their relationships with nodes and links, respectively. One of the most prominent sub domains in complex network analysis is community detection, which consists in searching cohesive subgroups in complex networks. The researchers use the networks which are generated artificially in order to test their community detection algorithms. In this study, we search the effect of the realism level of those computer generated artificial networks on algorithms community detection performance. We first analyze the properties of generated networks with the model proposed by Lancichinetti et al., which is supposed to be the most realistic until now. We propose a modification to further improve the level of realism and study their consequences in terms of topology. Our modification improves significantly the level of realism and especially the robustness of the model. We then apply a representative panel of eleven community detection algorithms on generated networks with the original model and its modified versions. The analysis of performance shows that the relative value of algorithms is generally not affected by the level of realism, however significant differences emerge when considering individual algorithms. In particular, an increased level of realism makes the task of identifying communities clearly more difficult, causing a significant drop in performance for all algorithms.