While advances in computing resources have made processing enormous amounts of data possible, human ability to identify patterns in such data has not scaled accordingly. Thus, efficient computational methods for condensing and simplifying data are becoming vital for extracting actionable insights. In particular, while data summarization techniques have been studied extensively, only recently has summarizing interconnected data, or graphs, become popular. This survey is a structured, comprehensive overview of the state-of-the-art methods for summarizing graph data. We first broach the motivation behind and the challenges of graph summarization. We then categorize summarization approaches by the type of graphs taken as input and further organize each category by core methodology. Finally, we discuss applications of summarization on real-world graphs and conclude by describing some open problems in the field.
翻译:虽然计算资源的进步使得处理大量数据成为可能,但人类确定此类数据模式的能力并没有相应缩小,因此,对提取可操作的洞察力而言,精密和简化数据的高效计算方法变得至关重要,特别是,虽然数据总化技术已经进行了广泛研究,但直到最近才对相互关联的数据或图表进行了总结,这一调查对图表数据总化的最新方法进行了有条不紊的全面概述,我们首先探讨了图形总化背后的动机和挑战,然后按投入的图表类型对汇总方法进行分类,并进一步按核心方法对每一类别进行分类。最后,我们讨论了对现实世界图形进行总化的应用,并总结了该领域的一些未解决的问题。