Community detection from biological and social networks: A comparative analysis of metaheuristic algorithms

Atay Y., Koc I., Babaoglu I., Kodaz H.

APPLIED SOFT COMPUTING, cilt.50, ss.194-211, 2017 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 50
  • Basım Tarihi: 2017
  • Doi Numarası: 10.1016/j.asoc.2016.11.025
  • Dergi Adı: APPLIED SOFT COMPUTING
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.194-211
  • Anahtar Kelimeler: Metaheuristic optimization algorithms, Community detection, Biological networks, Social networks, Modularity, GENETIC ALGORITHM, MEMETIC ALGORITHM, COMPLEX NETWORKS, OPTIMIZATION
  • Gazi Üniversitesi Adresli: Hayır

Özet

In order to analyze complex networks to find significant communities, several methods have been proposed in the literature. Modularity optimization is an interesting and valuable approach for detection of network communities in complex networks. Due to characteristics of the problem dealt with in this study, the exact solution methods consume much more time. Therefore, we propose six metaheuristic optimization algorithms, which each contain a modularity optimization approach. These algorithms are the original Bat Algorithm (BA), Gravitational Search Algorithm (GSA), modified Big BangBig Crunch algorithm (BB-BC), improved Bat Algorithm based on the Differential Evolutionary algorithm (BADE), effective Hyperheuristic Differential Search Algorithm (HDSA) and Scatter Search algorithm based on the Genetic Algorithm (SSGA). Four of these algorithms (HDSA, BADE, SSGA, BB-BC) contain new methods, whereas the remaining two algorithms (BA and GSA) use original methods. To clearly demonstrate the performance of the proposed algorithms when solving the problems, experimental studies were conducted using nine real-world complex networks - five of which are social networks and the rest of which are biological networks. The algorithms were compared in terms of statistical significance. According to the obtained test results, the HDSA proposed in this study is more efficient and competitive than the other algorithms that were tested. (C) 2016 Elsevier B.V. All rights reserved.