基于结构冗余性校准的在线式社会网络压缩

Compressing Online Social Networks by Calibrating Structure Redundancy

随着社交网络、移动互联网等新兴服务的不断涌现,在线社会网络正以前所未有的速度增长并且呈现出极强的演化特性.网络压缩技术能够将大规模网络压缩成规模更小、结构信息更简洁的网络,在数据存储和网络可视化领域发挥着重要作用.现有的压缩算法为了优化压缩损失,重复比对原始网络与压缩网络之间的差异导致过高的时间开销,并且算法仅局限于静态网络,无法满足在线社会网络的演变要求.针对上述问题,提出一种解决演化网络压缩问题的高效算法,首先设计了基于局部化判定的结构合并贡献函数及其快速调整算法,将网络的首次压缩复杂度控制在O(n)到O(mn)之间;其次,设计了一种面向演化网络压缩的动态校准算法,参照网络演化前后拓扑结构的变化,校准前一时刻的压缩表达以避免网络的重复压缩,在满足在线社会网络演变要求的同时提高了压缩效率;最后,通过对真实数据集的实验分析,验证了算法的有效性.

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 （ran）. 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.