Social Network Analysis

Abstract

To divide the network into various communities on the basis of characteristics Description As we know that data in real world is growing at a very fast pace. So it is very difficult to make analysis on this data which can be represented in the form of network. So to ease the computation or analysis of the complex network we divide the complete network into various communities on the basis of characteristics (i.e. distance between the nodes, modularity of sub graph). In this project i have studied three different algorithms for community detection in a network. These algorithms are based on different approaches. Firstly, Walktrap algorithm which works on agglomerative method in which edges are added to an initially empty network starting with the vertex pairs with highest similarity. Second, Multilevel Algorithm which works on modularity optimization approach. Modularity is the measure to check the quality of the community which is created by the adding or removing nodes from a community. Third, Girvan and Newman algorithm which follows divisive methodology which attempt to find the least similar connected pairs of vertices and then remove the edges between them. It divides the network into smaller and smaller components.