Community Detection in Networks

Abstract

An important property of networks/graphs modeling complex systems is the property of community structure, in which nodes are joined together in tightly knit groups (communities or clusters), between which there are only looser connections. The problem of detecting and extracting communities from such graphs has been the subject of intense investigations in recent years. This problem is very hard and not yet satisfactorily solved. In this project we explore and work on this community detection problem. We frame the problem as an optimization problem and hence explore the use of Genetic Algorithms (GAs) in solving the same. We have studied, analyzed and implemented several existing algorithms including standard ones and GA-based ones. The standard algorithms include the Girvan-Newman Algorithm and the Label Propagation Algorithm by Raghavan et al. while the GA-based one is Tasgin et al.s algorithm. We have also designed a new GA-based algorithm for the problem. We present a comparative performance (accuracy + efficiency) analysis of these algorithms (new + existing) to gain insights into the problem and reveal the advantages of our proposed algorithm over existing algorithms. We have also created some artificial datasets (based on standard existing algorithms like the one for LFR graphs) for the purpose of the analysis and have acquired some real-world datasets (like Zachary's karate club network, Lusseau's network of bottlenose dolphins, etc.) too.