Single Document Summarization Based on Triangle Analysis of Dependency Graphs

Extractive document summarization is a fundamental technique for document summarization. Most well-known approaches to extractive document summarization utilize supervised learning where algorithms are trained on collections of "ground truth" summaries built for a relatively large number of documents. In this paper, we propose a novel algorithm, called Triangle Sum for key sentence extraction from single document based on graph theory. The algorithm builds a dependency graph for the underlying document based on co-occurrence relation as well as syntactic dependency relations. In such a dependency graph, nodes represent words or phrases of high frequency, and edges represent dependency-co-occurrence relations between them. The clustering coefficient is computed from each node to measure the strength of connection between a node and its neighbors in a dependency graph. By identifying triangles of nodes in the graph, a part of the dependency graph can be extracted as marks of key sentences. At last, a set of key sentences that represent the main document information can be extracted.