Searching social networks

• Main Author: Bharath Vijay Palukurthi.
• Other Authors: School of Computer Engineering
• Format: Final Year Project
• Language: English
• Published: 2012
• Subjects: DRNTU::Engineering::Computer science and engineering::Computer applications::Social and behavioral sciences
• Online Access: http://hdl.handle.net/10356/49094
• Institution: Nanyang Technological University

In the wake of the recent information revolution, there has been a strong interest in understanding the structure of real world social networks and in detecting cohesive subcomponents within social networks. These models to detect cohesion are gaining popularity in Social Network Analysis. These models have found usage in diverse areas ranging from analyzing friendship networks such as Facebook to understanding criminal networks such as terrorist rings, etc. This project aims to provide different algorithms & their implementations for the commonly used models to detect social cohesion. All of these problems belong to the NP category. Despite being very hard problems, it is important to study these problems and look for fast and scalable algorithms for these problems especially since they are widely used. In this project we study the clique model and its various relaxations such as k-plexes, k-clubs, kd-cliques & quasi-cliques. We introduce the different measures used to model social cohesion and study their benefits and limitations. We have also implemented different algorithms for each of these problems and have modified them to work faster on real world social network graphs. We also study the performance of the various algorithms on different types of graphs and suggest the best the algorithms to use where applicable. All the implementations have also been optimized to work best on sparse graphs and have been built to be scalable so as to work on the extremely large real world data sets from the Stanford SNAP database.