Searching social networks

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.