关键词: 图汇总,概念分层,多目标规划,层次凝聚

Abstract: 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 summarization 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 stratified 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.

Key words: Graph summarization,Concept hierarchy,Multi-objective planning,Hierarchical agglomerative