Graph Compression Algorithm Based On Nodes Classification And Ordering For Social Networks

In recent years,the analysis of social network graphs has received widespread concern.However,due to limitations of memory,social network graphs that are growning up in scale can no longer be fully loaded into memory,which is a great challenge for the storage and analysis of social networks.Graph compression provides an effective solution to this challenge by reducing storage space requirements of graphs.The existing graph compression algorithms for social networks either adopt complex encoding techniques to improve the compression ratio but can not guarantee the running performance of graph processing algorithms,or adopt simple encoding techniques to ensure the running performance of graph processing algorithms but sacrifice the compression ratio,which can not take both into consideration.In order to solve the above problem,the graph compression algorithms for social networks need to ordering nodes to mine the key attributes affecting the compression ratio of the social network graphs to improve the compression ratio,and adopt a simple encoding technique to ensure the running performance of graph processing algorithms.Existing research has confirmed that the compression ratio of social network graphs is highly dependent on locality.However,the existing nodes ordering methods do not take the different influences of different nodes on locality into account,and only a part of locality can be mined.Therefore,a hybrid nodes ordering method based on nodes classification designed to mine more locality and provide the compressible range of graphs,in which different ordering strategies are adopted for high-degree nodes,low-degree nodes and zero-degree nodes.Based on the above method,a graph compression algorithm for social networks based on nodes classification and ordering,namely NCOGC,is proposed,which can not only obtain good compression ratio but also ensure the running performance of graph processing algorithms.And the typical graph processing algorithms on the compressed graphs are implemented,such as representative Breadth-First Search and PageRank,for evaluating NCOGC.Experiments on real-world social network graphs and synthetic graphs show that NCOGC increases the compression ratio by 6%~53% for different graphs,and the running performance of Breadth-First Search and PageRank can be increased by up to 86% and21.4% respectively.The experimental results show that NCOGC can achieve both good compression ratio and the running performance of graph processing algorithms.