Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
|---|---|---|---|---|---|
Searching... | 30000010270363 | QA76.9.N38 M53 2011 | Open Access Book | Book | Searching... |
On Order
Summary
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 |
| 0.1 Background | p. 3 |
| 0.2 Book Organization | p. 4 |
| 0.3 Acknowledgments | p. 7 |
| Part I Introduction to Graph Theory | |
| 1 Notations, Properties, and Representations | p. 11 |
| 1.1 Graph Terminology and Notations | p. 11 |
| 1.2 Graph Properties | p. 13 |
| 1.3 Graph Types | p. 14 |
| 1.4 Representing Graphs as Matrices | p. 15 |
| 1.5 Using Matrices to Compute Graph Properties | p. 16 |
| 1.6 Representing Graphs as Linked Lists | p. 17 |
| 1.7 Eigenvalues and Eigenvectors | p. 18 |
| 2 Graph-Based Algorithms | p. 20 |
| 2.1 Depth-First Graph Traversal | p. 20 |
| 2.2 Breadth-First Graph Traversal | p. 22 |
| 2.3 Minimum Spanning Trees | p. 23 |
| 2.4 Shortest-Path Algorithms | p. 26 |
| 2.5 Cuts and Flows | p. 29 |
| 2.6 Graph Matching | p. 31 |
| 2.7 Dimensionality Reduction | p. 32 |
| 2.8 Stochastic Processes on Graphs | p. 34 |
| 2.9 Harmonic Functions | p. 38 |
| 2.10 Random Walks | p. 40 |
| 2.11 Spreading Activation | p. 41 |
| 2.12 Electrical Interpretation of Random Walks | p. 42 |
| 2.13 Power Method | p. 44 |
| 2.14 Linear Algebra Methods for Computing Harmonic Functions | p. 45 |
| 2.15 Method of Relaxations | p. 46 |
| 2.16 Monte Carlo Methods | p. 47 |
| Part II Networks | |
| 3 Random Networks | p. 53 |
| 3.1 Networks and Graphs | p. 53 |
| 3.2 Random Graphs | p. 54 |
| 3.3 Degree Distributions | p. 54 |
| 3.4 Power Laws | p. 57 |
| 3.5 Zipf's Law | p. 58 |
| 3.6 Preferential Attachment | p. 61 |
| 3.7 Giant Component | p. 62 |
| 3.8 Clustering Coefficient | p. 62 |
| 3.9 Small Worlds | p. 63 |
| 3.10 Assortativity | p. 65 |
| 3.11 Centrality | p. 67 |
| 3.12 Degree Centrality | p. 67 |
| 3.13 Closeness Centrality | p. 68 |
| 3.14 Betweenness Centrality | p. 69 |
| 3.15 Network Example | p. 70 |
| 3.16 Dynamic Processes: Percolation | p. 72 |
| 3.17 Strong and Weak Ties | p. 74 |
| 3.18 Assortative Mixing | p. 76 |
| 3.19 Structural Holes | p. 76 |
| 4 Language Networks | p. 78 |
| 4.1 Co-Occurrence Networks | p. 78 |
| 4.2 Syntactic Dependency Networks | p. 80 |
| 4.3 Semantic Networks | p. 81 |
| 4.4 Similarity Networks | p. 85 |
| Part III Graph-Based Information Retrieval | |
| 5 Link Analysis for the World Wide Web | p. 91 |
| 5.1 The Web as a Graph | p. 91 |
| 5.2 PageRank | p. 92 |
| 5.3 Undirected Graphs | p. 95 |
| 5.4 Weighted Graphs | p. 95 |
| 5.5 Combining PageRank with Content Analysis | p. 97 |
| 5.6 Topic-Sensitive Link Analysis | p. 97 |
| 5.7 Query-Dependent Link Analysis | p. 100 |
| 5.8 Hyperlinked-Induced Topic Search | p. 101 |
| 5.9 Document Reranking with Induced Links | p. 103 |
| 6 Text Clustering | p. 106 |
| 6.1 Graph-Based Clustering | p. 108 |
| 6.2 Spectral Methods | p. 111 |
| 6.3 The Fiedler Method | p. 113 |
| 6.4 The Kernighan-Lin Method | p. 114 |
| 6.5 Betweenness-Based Clustering | p. 115 |
| 6.6 Min-Cut Clustering | p. 117 |
| 6.7 Text Clustering Using Random Walks | p. 119 |
| Part IV Graph-Based Natural Language Processing | |
| 7 Semantics | p. 123 |
| 7.1 Semantic Classes | p. 123 |
| 7.2 Synonym Detection | p. 125 |
| 7.3 Semantic Distance | p. 126 |
| 7.4 Textual Entailment | p. 129 |
| 7.5 Word-Sense Disambiguation | p. 131 |
| 7.6 Name Disambiguation | p. 134 |
| 7.7 Sentiment and Subjectivity | p. 135 |
| 8 Syntax | p. 140 |
| 8.1 Part-of-Speech Tagging | p. 140 |
| 8.2 Dependency Parsing | p. 141 |
| 8.3 Prepositional-Phrase Attachment | p. 144 |
| 8.4 Co-Reference Resolution | p. 146 |
| 9 Applications | p. 149 |
| 9.1 Summarization | p. 149 |
| 9.2 Semi-supervised Passage Retrieval | p. 150 |
| 9.3 Keyword Extraction | p. 154 |
| 9.4 Topic Identification | p. 156 |
| 9.5 Topic Segmentation | p. 161 |
| 9.6 Discourse | p. 162 |
| 9.7 Machine Translation | p. 165 |
| 9.8 Cross-Language Information Retrieval | p. 166 |
| 9.9 Information Extraction | p. 169 |
| 9.10 Question Answering | p. 171 |
| 9.11 Term Weighting | p. 174 |
| Bibliography | p. 179 |
| Index | p. 191 |
