Graph-based Natural Language Processing and Information Retrieval

by Rada Mihalcea , Dragomir Radev

• ISBN13: 9780521896139
• ISBN10: 0521896134
• Format: Hardcover
• Copyright: 2011-04-11
• Publisher: Cambridge University Press

Summary

Graph theory and the fields of natural language processing and information retrieval are well-studied disciplines. Traditionally, these areas have been perceived as distinct, with different algorithms, different applications, and different potential end-users. However, recent research has shown that these disciplines are intimately connected, with a large variety of natural language processing and information retrieval applications finding efficient solutions within graph-theoretical frameworks. This book extensively covers the use of graph-based algorithms for natural language processing and information retrieval. It brings together topics as diverse as lexical semantics, text summarization, text mining, ontology construction, text classification, and information retrieval, which are connected by the common underlying theme of the use of graph-theoretical methods for text and information processing tasks. Readers will come away with a firm understanding of the major methods and applications in natural language processing and information retrieval that rely on graph-based representations and algorithms.

Table of Contents

Introduction	p. 1
Background	p. 3
Book Organization	p. 4
Acknowledgments	p. 7
Introduction to Graph Theory
Notations, Properties, and Representations	p. 11
Graph Terminology and Notations	p. 11
Graph Properties	p. 13
Graph Types	p. 14
Representing Graphs as Matrices	p. 15
Using Matrices to Compute Graph Properties	p. 16
Representing Graphs as Linked Lists	p. 17
Eigenvalues and Eigenvectors	p. 18
Graph-Based Algorithms	p. 20
Depth-First Graph Traversal	p. 20
Breadth-First Graph Traversal	p. 22
Minimum Spanning Trees	p. 23
Shortest-Path Algorithms	p. 26
Cuts and Flows	p. 29
Graph Matching	p. 31
Dimensionality Reduction	p. 32
Stochastic Processes on Graphs	p. 34
Harmonic Functions	p. 38
Random Walks	p. 40
Spreading Activation	p. 41
Electrical Interpretation of Random Walks	p. 42
Power Method	p. 44
Linear Algebra Methods for Computing Harmonic Functions	p. 45
Method of Relaxations	p. 46
Monte Carlo Methods	p. 47
Networks
Random Networks	p. 53
Networks and Graphs	p. 53
Random Graphs	p. 54
Degree Distributions	p. 54
Power Laws	p. 57
Zipf's Law	p. 58
Preferential Attachment	p. 61
Giant Component	p. 62
Clustering Coefficient	p. 62
Small Worlds	p. 63
Assortativity	p. 65
Centrality	p. 67
Degree Centrality	p. 67
Closeness Centrality	p. 68
Betweenness Centrality	p. 69
Network Example	p. 70
Dynamic Processes: Percolation	p. 72
Strong and Weak Ties	p. 74
Assortative Mixing	p. 76
Structural Holes	p. 76
Language Networks	p. 78
Co-Occurrence Networks	p. 78
Syntactic Dependency Networks	p. 80
Semantic Networks	p. 81
Similarity Networks	p. 85
Graph-Based Information Retrieval
Link Analysis for the World Wide Web	p. 91
The Web as a Graph	p. 91
PageRank	p. 92
Undirected Graphs	p. 95
Weighted Graphs	p. 95
Combining PageRank with Content Analysis	p. 97
Topic-Sensitive Link Analysis	p. 97
Query-Dependent Link Analysis	p. 100
Hyperlinked-Induced Topic Search	p. 101
Document Reranking with Induced Links	p. 103
Text Clustering	p. 106
Graph-Based Clustering	p. 108
Spectral Methods	p. 111
The Fiedler Method	p. 113
The Kernighan-Lin Method	p. 114
Betweenness-Based Clustering	p. 115
Min-Cut Clustering	p. 117
Text Clustering Using Random Walks	p. 119
Graph-Based Natural Language Processing
Semantics	p. 123
Semantic Classes	p. 123
Synonym Detection	p. 125
Semantic Distance	p. 126
Textual Entailment	p. 129
Word-Sense Disambiguation	p. 131
Name Disambiguation	p. 134
Sentiment and Subjectivity	p. 135
Syntax	p. 140
Part-of-Speech Tagging	p. 140
Dependency Parsing	p. 141
Prepositional-Phrase Attachment	p. 144
Co-Reference Resolution	p. 146
Applications	p. 149
Summarization	p. 149
Semi-supervised Passage Retrieval	p. 150
Keyword Extraction	p. 154
Topic Identification	p. 156
Topic Segmentation	p. 161
Discourse	p. 162
Machine Translation	p. 165
Cross-Language Information Retrieval	p. 166
Information Extraction	p. 169
Question Answering	p. 171
Term Weighting	p. 174
Bibliography	p. 179
Index	p. 191
Table of Contents provided by Ingram. All Rights Reserved.