基于最小描述长度原则的属性图概要方法

摘要

图概要技术是管理、分析和可视化大规模图的关键技术之一.如何综合结构和属性信息进行图概要是一个挑战.大部分现有的图概要方法或者只考虑结构或属性某一方面的信息,或者要求属性的表现形式是一致的.结合信息论中最小描述长度原则,对属性图概要问题建模,将其转化为求解最小表示代价问题,以实现图压缩和图概要的双重目标.提出了一种计算节点属性相似性的方法,该属性度量方法对节点属性的限制较小,并且将节点间的相似性统一为存储代价,实现了节点结构相似和属性相似的协同考虑.提出了两种求解最小代价表示的图概要算法.在真实和合成的数据集上实验,验证了提出算法的有效性.