Searching social networks
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 mod...
Saved in:
Main Author: | |
---|---|
Other Authors: | |
Format: | Final Year Project |
Language: | English |
Published: |
2012
|
Subjects: | |
Online Access: | http://hdl.handle.net/10356/49094 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
Summary: | 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. |
---|