Community Detection in Networks

Jayannavar, Prashant A. (2013) Community Detection in Networks. BTech thesis.



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.

Item Type:Thesis (BTech)
Uncontrolled Keywords:Communities; Partitions; Genetic Algorithms; Optimization; LFR Graphs
Subjects:Engineering and Technology > Computer and Information Science > Data Mining
Divisions: Engineering and Technology > Department of Computer Science
ID Code:4755
Deposited By:Hemanta Biswal
Deposited On:31 Oct 2013 10:10
Last Modified:20 Dec 2013 14:56
Supervisor(s):Majhi, B

Repository Staff Only: item control page