基于编辑行为码的图概要技术

摘要

图数据的处理面临庞大规模和复杂结构的制约.图的概要化,旨在寻找一组简洁的超图或稀疏图,阐明原始图的主要结构信息或变化趋势.针对属性图提出了基于编辑行为码的概要模型,遵循最小描述长度原理(Mini-mum Description Length,MDL),将结构的相似性和属性的相似性统一为存储代价,构建编辑行为码.在此模型基础上提出了Greedy算法和Random算法,存储属性和结构的编辑信息,生成高质量的超图,并支持原始图的重构.实验结果表明本文提出的概要模型和算法相比于其他图概要算法,在压缩率和时间代价等指标上具有一定的优越性.