TextRank: Bringing Order into Text

TextRank: Bringing Order into Texts Rada Mihalcea and Paul Tarau Department of Computer Science University of North Texas � rada,tarau � @cs.unt.edu Abstract In this paper, we introduce TextRank – a graph-based ranking model for text processing, and show how this model can be successfully used in natural language applications. In particular, we propose two innova- tive unsupervised methods for keyword and sentence extraction, and show that the results obtained com- pare favorably with previously published results on established benchmarks. 1 Introduction Graph-based ranking algorithms like Kleinberg’s HITS algorithm (Kleinberg, 1999) or Google’s PageRank (Brin and Page, 1998) have been success- fully used in citation analysis, social networks, and the analysis of the link-structure of the World Wide Web. Arguably, these algorithms can be singled out as key elements of the paradigm-shift triggered in the field of Web search technology, by providing a Web page ranking mechanism that relies on the col- lective knowledge of Web architects rather than in- dividual content analysis of Web pages. In short, a graph-based ranking algorithm is a way of deciding on the importance of a vertex within a graph, by tak- ing into account global information recursively com- puted from the entire graph, rather than relying only on local vertex-specific information. Applying a similar line of thinking to lexical or semantic graphs extracted from natural language documents, results in a graph-based ranking model that can be applied to a variety of natural language processing applications, where knowledge drawn from an entire text is used in making local rank- ing/selection decisions. Such text-oriented ranking methods can be applied to tasks ranging from auto- mated extraction of keyphrases, to extractive summa- rization and word sense disambiguation (Mihalcea et al., 2004). In this paper, we introduce the TextRank graph- based ranking model for graphs extracted from nat- ural language texts. We investigate and evaluate the application of TextRank to two language processing tasks consisting of unsupervised keyword and sen- tence extraction, and show that the results obtained with TextRank are competitive with state-of-the-art systems developed in these areas. 2 The TextRank Model Graph-based ranking algorithms are essentially a way of deciding the importance of a vertex within a graph, based on global information recursively drawn from the entire graph. The basic idea im- plemented by a graph-based ranking model is that of “voting” or “recommendation”. When one ver- tex links to another one, it is basically casting a vote for that other vertex. The higher the number of votes that are cast for a vertex, the higher the importance of the vertex. Moreover, the importance of the vertex casting the vote determines how important the vote itself is, and this information is also taken into ac- count by the ranking model. Hence, the score asso- ciated with a vertex is determined based on the votes that are cast for it, and the score of the vertices cast- ing these votes. Formally, let the set of vertices���� �  be a directed graph with � and set …

Content truncated to 500 words