Graph algorithms in text retrieval

This thesis surveys use of graph theory and algorithms in information retrieval. It provides an introduction to graph and information retrieval theories and an overview of the overlap between these disciplines. We show application of the graph theory in clustering, document classification, finding communities etc. The most stress is, however, put on ranking algorithms as they aim to improve the most critical property of the information retrieval systems, their precision. The paper presents different graphbased ranking algorithms, provides comments to their time and memory requirements and to realistic usage of these rankings. It also contains a description and test results of our implementation of algorithms for computing the PageRank distribution designed for the Egothor search engine