Graph-based Natural Language Processing and Information Retrieval

Half-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 7
Introduction......Page 11
0.1 Background......Page 13
0.2 Book Organization......Page 14
Random Networks......Page 15
Semantics......Page 16
0.3 Acknowledgments......Page 17
Part I: Introduction to Graph Theory......Page 19
1.1 Graph Terminology and Notations......Page 21
1.2 Graph Properties......Page 23
1.3 Graph Types......Page 24
1.4 Representing Graphs as Matrices......Page 25
1.5 Using Matrices to Compute Graph Properties......Page 26
1.6 Representing Graphs as Linked Lists......Page 27
1.7 Eigenvalues and Eigenvectors......Page 28
Further Reading......Page 29
2.1 Depth-First Graph Traversal......Page 30
2.2 Breadth-First Graph Traversal......Page 32
2.3 Minimum Spanning Trees......Page 33
2.4 Shortest-Path Algorithms......Page 36
2.5 Cuts and Flows......Page 39
2.6 Graph Matching......Page 41
2.7 Dimensionality Reduction......Page 42
2.8 Stochastic Processes on Graphs......Page 44
2.9.3 Reaching the Boundary......Page 48
2.9.4 The Laplace Equation......Page 49
2.10 Random Walks......Page 50
2.11 Spreading Activation......Page 51
2.12 Electrical Interpretation of Random Walks......Page 52
2.13 Power Method......Page 54
2.14 Linear Algebra Methods for Computing Harmonic Functions......Page 55
2.15 Method of Relaxations......Page 56
2.16 Monte Carlo Methods......Page 57
Further Reading......Page 59
Part II: Networks......Page 61
3.1 Networks and Graphs......Page 63
3.3 Degree Distributions......Page 64
3.4 Power Laws......Page 67
3.5 Zipf's Law......Page 68
3.6 Preferential Attachment......Page 71
3.8 Clustering Coefficient......Page 72
3.9 Small Worlds......Page 73
3.10 Assortativity......Page 75
3.12 Degree Centrality......Page 77
3.13 Closeness Centrality......Page 78
3.14 Betweenness Centrality......Page 79
3.15 Network Example......Page 80
3.16 Dynamic Processes: Percolation......Page 82
3.17 Strong and Weak Ties......Page 84
3.19 Structural Holes......Page 86
Further Reading......Page 87
4.1 Co-Occurrence Networks......Page 88
4.2 Syntactic Dependency Networks......Page 90
4.3 Semantic Networks......Page 91
4.4.1 Networks of Summaries......Page 95
Further Reading......Page 97
Part III: Graph-Based Information Retrieval......Page 99
5.1 The Web as a Graph......Page 101
5.2 PageRank......Page 102
5.4 Weighted Graphs......Page 105
5.6 Topic-Sensitive Link Analysis......Page 107
5.7 Query-Dependent Link Analysis......Page 110
5.8 Hyperlinked-Induced Topic Search......Page 111
5.9 Document Reranking with Induced Links......Page 113
Further Reading......Page 115
6 Text Clustering......Page 116
6.1 Graph-Based Clustering......Page 118
6.2 Spectral Methods......Page 121
6.3 The Fiedler Method......Page 123
6.4 The Kernighan--Lin Method......Page 124
6.5 Betweenness-Based Clustering......Page 125
6.6 Min-Cut Clustering......Page 127
6.7 Text Clustering Using Random Walks......Page 129
Further Reading......Page 130
Part IV: Graph-Based Natural Language Processing......Page 131
7.1 Semantic Classes......Page 133
7.2 Synonym Detection......Page 135
7.3 Semantic Distance......Page 136
7.4 Textual Entailment......Page 139
7.5 Word-Sense Disambiguation......Page 141
7.6 Name Disambiguation......Page 144
7.7 Sentiment and Subjectivity......Page 145
Further Reading......Page 149
8.1 Part-of-Speech Tagging......Page 150
8.2 Dependency Parsing......Page 151
8.3 Prepositional-Phrase Attachment......Page 154
8.4 Co-Reference Resolution......Page 156
Further Reading......Page 158
9.1 Summarization......Page 159
9.2 Semi-supervised Passage Retrieval......Page 160
9.3 Keyword Extraction......Page 164
9.4 Topic Identification......Page 166
9.5 Topic Segmentation......Page 171
9.6 Discourse......Page 172
9.7 Machine Translation......Page 175
9.8 Cross-Language Information Retrieval......Page 176
9.9 Information Extraction......Page 179
9.10 Question Answering......Page 181
9.11 Term Weighting......Page 184
Further Reading......Page 187
Bibliography......Page 189
Index......Page 201