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

摘要：

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

关键词：在线社会网络、网络压缩、结构合并贡献、损失优化、压缩表达校准

所属期刊栏目：50

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金项目61073041,61073043,61202274,61370083;高等学校博士学科点专项科研基金项目20112304110011,20122304110012

在线出版日期：2014-01-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共16页

页码：2504-2519