Pre-processing and Path Normalization of a web graph used as a social network

Many efforts have been made for compression of web graphs. Most of these methods are suitable for search engines and are centered around encoding links and URLs efficiently. The purpose is to handle a large set of web pages in the main memory against any web based search. The authors of the present paper are interested in studying web graph as a social network and to develop a data model for it. So, suitable compression techniques, which are space efficient for disk based storage, are required. This paper has provided a two level compression technique. In the first level, the structural properties of a graph are studied and strongly connected components are fused to reduce the original graph to a DAG. Paths on this DAG are then stored efficiently using a Path Normalization technique. Space complexity expressions indicate the efficiency of the method. Relevant operators required for accessing the original graph through the compressed representations have also been discussed. Important earlier works have been referred to indicate the requirements of the present approach.