Graph Clustering using Treaps and Deaps

Abstract

With the advent of the Internet, Social networks have grown enormously and Social Network Analysis (SNA) has come up as an important field for research. Social networks are represented as graphs and the fundamental component of SNA is the relationship defined by linkages among units or nodes in the network. Since graphs in social networks comprise of large number of vertices and edges, adjacency matrix is considered to be an effective and efficient technique to represent them. The intent of this thesis is to cluster the graphs, optimize the graph storage and mapping without using a large adjacency matrix to represent a large graph. A special data structure Treap, a combination of binary search tree and heaps has been used as a replacement to a large adjacency matrix. It has been experimentally evaluated that the proposed approach significantly improves the space occupied by adjacency matrix and helps the graph to grow dynamically without affecting the current data structure. Once the graph or social network is optimally stored, clusters are generated, based on some probabilistic mathematical models and heuristic approaches. After the graph clustering is done efficiently, the next task of this thesis is to store and map the clustering information in an efficient format so that storage space is optimized and access time is less. A special kind of data structure ClusteredDeap inherited by Deaps data structure is used, in which dynamically generated array of linked list is properly mapped. It has been experimentally proved that access time for various operation such as insert, delete and traverse is significantly reduced using such data structure.