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, Spain, 18 - 23 July 2010 identifier

  • Publication Type: Conference Paper / Full Text
  • City: Barcelona
  • Country: Spain
  • Istanbul Technical University Affiliated: Yes


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.