An Efficient Community Detection Method using Parallel Clique-Finding Ants


Sadi S., Öğüdücü Ş., Uyar A. S.

2010 IEEE World Congress on Computational Intelligence, Barcelona, İspanya, 18 - 23 Temmuz 2010 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Basıldığı Şehir: Barcelona
  • Basıldığı Ülke: İspanya
  • İstanbul Teknik Üniversitesi Adresli: Evet

Özet

Attractiveness of social network analysis as a research topic in many different disciplines is growing in parallel to the continuous growth of the Internet, which allows people to share and collaborate more. Nowadays, detection of community structures, which may be established on social networks, is a popular topic in Computer Science. High computational costs and non-scalability on large-scale social networks are the biggest drawbacks of popular community detection methods. The main aim of this study is to reduce the original network graph to a maintainable size so that computational costs decrease without loss of solution quality, thus increasing scalability on such networks. In this study, we focus on Ant Colony Optimization techniques to find quasi-cliques in the network and assign these quasi-cliques as nodes in a reduced graph to use with community detection algorithms. Experiments are performed on commonly used social networks with the addition of several large-scale networks. Based on the experimental results on various sized social networks, we may say that the execution times of the community detection methods are decreased while the overall quality of the solution is preserved.