Fitness evaluation for overlapping community detection in complex networks

The discovery of community structures in complex networks is a challenging problem intensively studied in recent years. This paper investigates the performance of evolutionary algorithms for the task of detecting overlapping communities. This task is of great importance as the membership of a node to more than one group is naturally occuring in many real-world networks from fields such as sociology, biology and computer science. One of the major challenges in designing evolutionary algorithms for overlapping community detection is the efficient assessment of the quality of any particular division of nodes into groups. We test four different fitness functions in an evolutionary approach to the problem using the same chromosome representation and search scheme. The performance of the resulting algorithms is tested in a set of computational experiments for some real-world networks. We show that none of the fitness functions used are able to guide the search process towards good partitions based on a measure of the normalized mutual information.