Topology of Complex Networks and Performance Limitations of Community Detection Algorithms

Abstract

One of the most widely studied problems in the analysis of complex networks is the detection of community structures. Many algorithms have been proposed to find communities but the quest to find the best algorithm is still on. More often than not, researchers focus on developing fast and accurate algorithms that can be generically applied to networks from various domains. As the topology of networks changes with respect to domains, community detection algorithms fail to accommodate these changes to detect communities. In this paper, we attempt to highlight this problem by studying networks with different topologies and evaluate the performance of community detection algorithms in the light of these topological changes. To generate networks with different topologies, we used the well-known Lancichinetti-Fortunato-Radicchi (LFR) model, and we also propose a new model named Naïve Scale-Free Clustering to avoid any bias that can be introduced by the underlying network generation model. Results reveal several limitations of the current popular network clustering algorithms failing to correctly find communities. This suggests the need to revisit the design of current clustering algorithms in order to improve their performances.

Keywords

• Social networks and graphs
• network topology
• benchmark networks
• community detection algorithms
• normalized mutual information