Information Retrieval and Natural Language Processing : A Graph Theory Approach

Preface
Acknowledgements
Contents
About the Authors
Part I Basics of Graph Theory
1 Graph Theory Basics
	1.1 Introduction
	1.2 Graph Terminology
	1.3 Graphs Types
	1.4 Graphs Properties
	1.5 Graph Representation
	1.6 Operation on Graph
	References
2 Graph Algorithms
	2.1 Introduction
	2.2 Graph Traversal Algorithm
		2.2.1 Breadth First Search (BFS)
		2.2.2 Depth First Search (DFS)
	2.3 Shortest Path
		2.3.1 Dijkstra Algorithm
		2.3.2 Bellman–Ford Algorithm
	2.4 Max Flow Min Cut
	2.5 Random Walk
	2.6 Graph Clustering
	2.7 Graph Colouring
	References
3 Network Using Graph
	3.1 Introduction
	3.2 Network Graph
	3.3 Random Graph ( GR( n,p ) )
	3.4 Degree Distribution ( P( x ) )
	3.5 Centrality
		3.5.1 Degree of Centrality (Cd ( x ))
		3.5.2 Closeness Centrality (Cc  ( x ))
		3.5.3 Betweenness Centrality
	3.6 Prestige
	3.7 Clustering Coefficient (CC)
	3.8 Preferential Attachment
	3.9 Giant Component
	3.10 Small World Network
	3.11 Node Assortativity
	3.12 Strong and Weak Ties
	3.13 Heaps’ and Zipf’s Law
	References
Part II IR and NLP Using Graph
4 Information Retrieval
	4.1 Introduction
	4.2 Working of IR System
		4.2.1 Document Pre-processing Steps
	4.3 Indexing
	4.4 Searching and Ranking
	4.5 The Representative Terms of a Document
		4.5.1 Term Frequency (TF)
		4.5.2 Inverse Document Frequency (IDF)
	4.6 Models Used for Searching and Ranking
		4.6.1 Boolean Model
		4.6.2 Vector Space Model
		4.6.3 Probabilistic Model
	4.7 Applications of Information Retrieval
	References
5 Text Document Pre-processing Using Graph Theory
	5.1 Introduction
	5.2 Text as a Graph
		5.2.1 Cooccurrence Relation
		5.2.2 Sentence Graph
		5.2.3 Term Order Graph
		5.2.4 Graph Word Embedding
		5.2.5 Semantic Graph or Concept Graph
		5.2.6 Knowledge Graph
		5.2.7 Context Graph
	5.3 Name Entity Recognition
	5.4 Coreference Resolution
		5.4.1 Feature Functions for Selecting Correct Mentions
		5.4.2 Edge Weight
		5.4.3 Graph Modelling
		5.4.4 Graph Operations
	5.5 POS Tagger
	5.6 Word Sense Disambiguation
	5.7 Topic Modelling Using Graph Base Term Weights
	5.8 Open-Source Tools and Libraries
		5.8.1 Tools for Various NLP Tasks
		5.8.2 Tools Information Specific to NLP Task
	References
6 Text Analytics Using Graph Theory
	6.1 Introduction
	6.2 Graph Edge Measures
		6.2.1 Jaccard Coefficient
		6.2.2 Euclidean Distance
		6.2.3 Cosine Similarity
		6.2.4 Sentence Similarity Score
		6.2.5 BM 25
	6.3 Semantic Similarity Graph
		6.3.1 Entity Graph
		6.3.2 Directed Projection Graph
	6.4 Term Weighting
		6.4.1 By Graph Ranking Weight
		6.4.2 By Link Weight
		6.4.3 Feature Based
	6.5 Document Similarity Using Graph
		6.5.1 Annotation Graph
		6.5.2 Concept Graph
		6.5.3 Graph Isomorphism
		6.5.4 Graph Kernels
	6.6 Document Summarization Using Graph
		6.6.1 Centroid-Based Extractive Summarization
		6.6.2 Extractive Summarization Using Independent Set
		6.6.3 A Graph-Based Extractive Summarization Using Topic [10]
	6.7 Recommendation System
	6.8 Sentiment Analysis [12]
	6.9 Open-Source Tool Specific to Application
	References
7 Knowledge Graph
	7.1 Introduction
	7.2 Basics
		7.2.1 RDF and RDFS
		7.2.2 OWL
		7.2.3 SPARQL
	7.3 Construction of Knowledge Graph
		7.3.1 Neural Machine Translation for Translating Natural Language to SPARQL
		7.3.2 Ontology Tool to Convert Natural Language Text to RDF and OWL in One Click
		7.3.3 Extraction of RDF Statements from Text
		7.3.4 Constructing Knowledge Graph from Unstructured Text [7]
		7.3.5 PAROT: A Dependency-Based Natural Language to SPARQL Tool for Translating Natural Language to SPARQL
		7.3.6 End-To-End Relation Extraction Using LSTMs on Sequences and Tree Structures
		7.3.7 Relation Extraction Between Entities
	7.4 Applications
	7.5 Tools and Libraries
	References
Part III Emerging Applications and Development
8 NLP and IR Applications Using Graph Theory
	8.1 Introduction
	8.2 Case Study 1: Graph-Based Information Retrieval System [1]
	8.3 Case Study 2: Single Document Extractive Marathi Text Summarizer [2]
		8.3.1 Feature Extraction
		8.3.2 Ranking
	8.4 Case Study 3: Text Summarization of Medical Documents Using Graph
	8.5 Case Study 4: Extractive Summarization Using Semigraph [7]
	8.6 Query-Specific Multimodal Summarization Using Graph [9]
		8.6.1 Multimodal Summarization Tasks
	8.7 Graph Neural Networks
	8.8 Tools and Libraries
	References
9 Conclusion and Future Scope
	9.1 Conclusion
	9.2 Open Research Issues
		9.2.1 Complex Reasoning
		9.2.2 Scalability
		9.2.3 Handling Dynamic Nature of Data
		9.2.4 Features/Attributes/properties for Entity/Node Value Aggregation
	9.3 Future Outlook
	References