You are previewing Graph-based Natural Language Processing and Information Retrieval.
O'Reilly logo
Graph-based Natural Language Processing and Information Retrieval

Book Description

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 2011 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

  1. Cover
  2. Half Title
  3. Title Page
  4. Copyright
  5. Contents
  6. Introduction
    1. 0.1 Background
    2. 0.2 Book Organization
    3. 0.3 Acknowledgments
  7. Part I: Introduction to Graph Theory
    1. 1. Notations, Properties, and Representations
      1. 1.1 Graph Terminology and Notations
      2. 1.2 Graph Properties
      3. 1.3 Graph Types
      4. 1.4 Representing Graphs as Matrices
      5. 1.5 Using Matrices to Compute Graph Properties
      6. 1.6 Representing Graphs as Linked Lists
      7. 1.7 Eigenvalues and Eigenvectors
    2. 2. Graph-Based Algorithms
      1. 2.1 Depth-First Graph Traversal
      2. 2.2 Breadth-First Graph Traversal
      3. 2.3 Minimum Spanning Trees
      4. 2.4 Shortest-Path Algorithms
      5. 2.5 Cuts and Flows
      6. 2.6 Graph Matching
      7. 2.7 Dimensionality Reduction
      8. 2.8 Stochastic Processes on Graphs
      9. 2.9 Harmonic Functions
      10. 2.10 Random Walks
      11. 2.11 Spreading Activation
      12. 2.12 Electrical Interpretation of Random Walks
      13. 2.13 Power Method
      14. 2.14 Linear Algebra Methods for Computing Harmonic Functions
      15. 2.15 Method of Relaxations
      16. 2.16 Monte Carlo Methods
  8. Part II: Networks
    1. 3. Random Networks
      1. 3.1 Networks and Graphs
      2. 3.2 Random Graphs
      3. 3.3 Degree Distributions
      4. 3.4 Power Laws
      5. 3.5 Zipf’s Law
      6. 3.6 Preferential Attachment
      7. 3.7 Giant Component
      8. 3.8 Clustering Coefficient
      9. 3.9 Small Worlds
      10. 3.10 Assortativity
      11. 3.11 Centrality
      12. 3.12 Degree Centrality
      13. 3.13 Closeness Centrality
      14. 3.14 Betweenness Centrality
      15. 3.15 Network Example
      16. 3.16 Dynamic Processes: Percolation
      17. 3.17 Strong and Weak Ties
      18. 3.18 Assortative Mixing
      19. 3.19 Structural Holes
    2. 4. Language Networks
      1. 4.1 Co-Occurrence Networks
      2. 4.2 Syntactic Dependency Networks
      3. 4.3 Semantic Networks
      4. 4.4 Similarity Networks
  9. Part III: Graph-Based Information Retrieval
    1. 5. Link Analysis for the World Wide Web
      1. 5.1 The Web as a Graph
      2. 5.2 PageRank
      3. 5.3 Undirected Graphs
      4. 5.4 Weighted Graphs
      5. 5.5 Combining PageRank with Content Analysis
      6. 5.6 Topic-Sensitive Link Analysis
      7. 5.7 Query-Dependent Link Analysis
      8. 5.8 Hyperlinked-Induced Topic Search
      9. 5.9 Document Reranking with Induced Links
    2. 6. Text Clustering
      1. 6.1 Graph-Based Clustering
      2. 6.2 Spectral Methods
      3. 6.3 The Fiedler Method
      4. 6.4 The Kernighan–Lin Method
      5. 6.5 Betweenness-Based Clustering
      6. 6.6 Min-Cut Clustering
      7. 6.7 Text Clustering Using Random Walks
  10. Part IV: Graph-Based Natural Language Processing
    1. 7. Semantics
      1. 7.1 Semantic Classes
      2. 7.2 Synonym Detection
      3. 7.3 Semantic Distance
      4. 7.4 Textual Entailment
      5. 7.5 Word-Sense Disambiguation
      6. 7.6 Name Disambiguation
      7. 7.7 Sentiment and Subjectivity
    2. 8. Syntax
      1. 8.1 Part-of-Speech Tagging
      2. 8.2 Dependency Parsing
      3. 8.3 Prepositional-Phrase Attachment
      4. 8.4 Co-Reference Resolution
    3. 9. Applications
      1. 9.1 Summarization
      2. 9.2 Semi-supervised Passage Retrieval
      3. 9.3 Keyword Extraction
      4. 9.4 Topic Identification
      5. 9.5 Topic Segmentation
      6. 9.6 Discourse
      7. 9.7 Machine Translation
      8. 9.8 Cross-Language Information Retrieval
      9. 9.9 Information Extraction
      10. 9.10 Question Answering
      11. 9.11 Term Weighting
  11. Bibliography
  12. Index