Summarizing Documents by Measuring the Importance of a Subset of Vertices within a Graph

This paper presents a novel method of generating extractive summaries for multiple documents. Given a cluster of documents, we firstly construct a graph where each vertex represents a sentence and edges are created according to the asymmetric relationship between sentences. Then we develop a method to measure the importance of a subset of vertices by adding a super-vertex into the original graph. The importance of such a super-vertex is quantified as super-centrality, a quantitative measure for the importance of a subset of vertices within the whole graph. Finally, we propose a heuristic algorithm to find the best summary. Our method is evaluated with extensive experiments. The comparative results show that the proposed method outperforms other methods on several datasets.