Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/49093
Title: Searching social networks
Authors: Doyen Sahoo
Keywords: DRNTU::Engineering::Computer science and engineering::Computer applications::Social and behavioral sciences
Issue Date: 2012
Abstract: Searching Social Networks is about using graph theory to search and analyse the cause and effect of phenomena and get useful information about social networks. With the growth of Social Networks, particularly in the recent years, it can be extremely lucrative to mine the data in the social networks and get useful information out of it. One of the many applications is marketing. We can find people with similar interests linked to each other on social networks, and if we can identify such groups, the marketing is more focused and cheaper. This project focuses on the development of tools which help us analyse the closeness measures in graphs or social networks. In this project we aim to identify subgraphs within a graph or a social network that satisfies some property. We focus on clique, kd-clique, k-club, k-plex and quasi cliques. A clique is in simple terms a complete subgraph. The other structures are relaxation of the clique. This project gives a description of how the tools were built and how they work in order to detect these structures, which have been defined in further detail later. This project also analyses the performance of each of the algorithms implemented. These problems can easily be implemented if a naïve enumeration algorithm is used. However, all of these problems fall in the NP-Hard category with an enumeration approach having the worst case complexity of the order of O (2nn2) to O (2nn3). Such problems for graphs with 50 vertices could take a day to solve. However, we aim to make these tools work small social networks of 5,000 to 20,000 vertices that can be found on SNAP (Stanford data sets). Thus efficient heuristics and optimizations are required in order to handle such large graphs and social networks and finish the computation in reasonable time, which otherwise could have taken decades or even centuries – even on the fastest computers. A lot of research was done to find the correct algorithms which were implemented and comprehensively analysed on common data sets like DIMACS and also randomly generated graphs. Most of these algorithms were able to give a decent performance on the SNAP data sets with execution time ranging from less than a second to a couple of hours.
URI: http://hdl.handle.net/10356/49093
Rights: Nanyang Technological University
Fulltext Permission: restricted
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Student Reports (FYP/IA/PA/PI)

Files in This Item:
File Description SizeFormat 
SCE11-0334.pdf
  Restricted Access
1.56 MBAdobe PDFView/Open

Page view(s) 50

221
checked on Oct 20, 2020

Download(s) 50

15
checked on Oct 20, 2020

Google ScholarTM

Check

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.