摘要
将原始图中节点分配到多个分组并根据原始边来确立分组间关系,这样得到的图称作汇总图。汇总图的规模可以由用户设定,用户可以通过浏览小规模的汇总图来获得原始图的相关信息。K-SGS方法是一种新的基于节点概念分层的图汇总算法,它解决了传统K-SNAP算法的汇总图规模参数受限问题。为了解决该问题,算法引入了节点的属性值概念分层,从而增强了图汇总过程中节点分组的灵活性:不仅可以合并同值的节点,还可合并具有相似值的节点。除了关注汇总过程中边的信息损失外,K-SGS方法还关注节点的信息损失,它将图汇总问题建模成多目标规划问题,并通过分层序列法和基于分级的统一评价函数两种不同策略来解决该问题。算法上,提出了快速的层次聚类方法,使得每轮可以合并多个聚类,从而提高效率。经数据集上的实验表明,新算法能生产各种规模参数的汇总图,并具有较好的汇总质量。
This paper allocated the raw nodes of graph into some different groups and established relationships among the groups by considering the raw edges of graph. We called this procedure graph summarization and the newly built graph was called graph summary. Users can set the scale value of graph summary and obtain the information of raw graph with the help of it. However, by using the classic method, we can only build the graph summaries whose sizes are above a certain scale lower bound, which cannot be acceptable in many applications. K-SGS is a novel graph summariza- tion method which solves the scale limits. By using the concept hierarchy of the nodes~ attributes, K-SGS can group the nodes in a flexible way. It groups the nodes not only with same values but also with similar values. Besides the edges＇ information loss,it also considers the nodes~ information loss during the summarization and models the summarization as multi-objective planning. We proposed two hierarchical agglomerative algorithms. One is based on forbearing strati- fied sequencing method and the other is based on unified objective function method. The experiment on real life dataset shows that our methods can solve the problem and get the graph summaries with good quality.
出处
《计算机科学》
CSCD
北大核心
2013年第8期165-171,共7页
Computer Science
基金
国家"十一五"部委预研基金(513150402)资助
关键词
图汇总
概念分层
多目标规划
层次凝聚
Graph summarization
Concept hierarchy
Multi-objective planning
Hierarchical agglomerative
