Compressing Online Social Networks by Calibrating Structure Redundancy

Online social networks are growing in unprecedented speed and emerge strong evolutionary characteristic which is caused by emerging new services such as social network and mobile Internet. Network compression is a new technique for representing a large-scale network by a concise network that can capture the structural and attributive information of the original large network. Network compression plays an important role in data storage and the visualization of networks. The previous network compression algorithm leads to exorbitant costs by comparing the difference between the original network and the compression one repeatedly when optimizing the compression loss. Furthermore, it can only deal with static network but not the evolutionary ones. To solve these problems, this paper proposes an efficient algorithm to deal with the evolutionary network compression issue. A function to measure structure merging contribution based on localized decision and its quick-adjusting algorithm are first designed, its time complexity of initial network compression is controlled between O(n) and O(mn). Then a dynamic calibrating algorithm for evolutionary network compression is proposed, which takes advantage of the changes of the topological structure in each snapshot to adjust the previous compression expression, and avoids redundantly compressing while achieving high efficiency. Finally, competitive experiments on real datasets demonstrate the effectiveness and efficiency of the proposed algorithm.