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...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Final Year Project (FYP) |
| Language: | English |
| Published: |
2012
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10356/49094 |
| _version_ | 1811679342294466560 |
|---|---|
| author | Bharath Vijay Palukurthi. |
| author2 | School of Computer Engineering |
| author_facet | School of Computer Engineering Bharath Vijay Palukurthi. |
| author_sort | Bharath Vijay Palukurthi. |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T03:07:38Z |
| format | Final Year Project (FYP) |
| id | ntu-10356/49094 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T03:07:38Z |
| publishDate | 2012 |
| record_format | dspace |
| spelling | ntu-10356/490942023-03-03T20:29:43Z Searching social networks Bharath Vijay Palukurthi. School of Computer Engineering Centre for Advanced Information Systems Cheng Sheung Chak James DRNTU::Engineering::Computer science and engineering::Computer applications::Social and behavioral sciences 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. Bachelor of Engineering (Computer Science) 2012-05-15T01:00:58Z 2012-05-15T01:00:58Z 2012 2012 Final Year Project (FYP) http://hdl.handle.net/10356/49094 en Nanyang Technological University 75 p. application/pdf |
| spellingShingle | DRNTU::Engineering::Computer science and engineering::Computer applications::Social and behavioral sciences Bharath Vijay Palukurthi. Searching social networks |
| title | Searching social networks |
| title_full | Searching social networks |
| title_fullStr | Searching social networks |
| title_full_unstemmed | Searching social networks |
| title_short | Searching social networks |
| title_sort | searching social networks |
| topic | DRNTU::Engineering::Computer science and engineering::Computer applications::Social and behavioral sciences |
| url | http://hdl.handle.net/10356/49094 |
| work_keys_str_mv | AT bharathvijaypalukurthi searchingsocialnetworks |