This web site is no longer maintained and the content may be outdated.
Please visit www.cmpe.boun.edu.tr for up-to-date information.
 
CmpE RSS
No upcoming events...

Home / Graduate / M.S. Theses Completed
 
 
 
 
  Mürsel Taşgın, 2005    

Thesis Title

Community detection model using genetic algorithm in complex networks and its application in real-life networks


Abstract

This work is an endeavor towards analyzing complex networks. Mainly, acommunity detection algorithm based on genetic algorithm will be introduced, and detailedbackground will be developed. Firstly, we introduce community detection methods in complex networks. Acommunity in a complex network is a group of nodes that has more connectivity withinand less connectivity with other communities. There are many community detectionalgorithms proposed so far, some of which performs very well, however most of them are not feasible in identifying communities in large complex networks, where many of the reallife examples of the complex networks are large complex networks (e.g. www network, emailnetworks) due to time complexity of the algorithms. We introduce and apply acommunity detection algorithm on some real-life complex networks, like Zachary̕s Karate Club and the Enron e-mail network. Zachary̕s Karate Club network is a well-knownnetwork dataset. We collected data of Enron e-mail network and processed that data toform the Enron e-mail network.We present a community detection algorithm that is based on the network modularity (Q) and is scalable to very large networks that has 100,000 nodes. We run our algorithm onknown networks to assess the accuracy of our algorithm and then on Enron e-mail datasetas well to examine the scalability of our algorithm. Our algorithm gives optimalcommunity structure in very short time and is scalable to very large networks.
 
 
Boğaziçi University Department of Computer Engineering
Address: 34342 Bebek, Istanbul, TURKEY
Phone: +90 212 359 4523-24 Fax: +90 212 287 2461
general information: infocmpe.boun.edu.tr   webmaster: webmastercmpe.boun.edu.tr