Proximity Analysis of Social network using skip graph

Abstract

With the enormous growth of Internet, Cloud Computing, etc. the world has become closer and faster and with the enormous growth of Social networks, 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. Major concern for computer experts is how to store such enormous amount of data especially in form of graphs. Further, data structure used for storage of such type of data should provide efficient format for fast retrieval of data as and when required. Although adjacency matrix is an effective technique to store a graph having few or large number of nodes and vertices but when it comes to analysis of huge amount of data from site like face book or twitter, adjacency matrix are not sufficient. The intent of this thesis is to optimize the graph storage and mapping without using a large adjacency matrix to represent a large graph. A special data structure Skip Graph, evolved from Skip list has been used as a replacement to a large adjacency matrix. Main advantage of skip graph is optimization in dynamic allocation of memory and fast search results with minimum computational cycles. 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 prior knowledge of the size of network. Once the graph or social network is optimally stored, different type of analysis like proximity Analysis, Role Analysis, Centrality analysis and other information diffusion analysis can be done on stored network. Our major focus is on proximity analysis using some parameters which significantly affect the proximity of a node to its neighbors. It has been experimentally proved that by using skip graph for social network analysis, access time for various operations such as insert, delete and traverse is significantly reduced and optimal storage, space utilization and retrieval can be achieved.