Desikan, Prasanna K.2009-03-032009-03-032009-01https://hdl.handle.net/11299/47905University of Minnesota Ph.D. dissertation. January 2009. Major: Computer Science. Advisor: Dr. Jaideep Srivastava. 1 computer file (PDF); x, 137 pages. Ill. (some col.)A useful information infrastructure can be created from various types of data by modeling the set of data objects as a set of nodes, and the relationship (e.g. transition or interaction) between them as a set of links. Such a representation is commonly referred to as a link graph, and the analytical techniques associated with such representations are called link analysis techniques. These techniques have played a crucial role in improving applications such as Web searches, Web-based social networks, and cyber security. Link analysis techniques have been successfully applied to derive popular measurements such as PageRank, TrustRank, and SpamRank, which belong to a class of first-order Markov measures. A first-order Markov measure for a node is a measure that depends only on the set of nodes with direct links to it. A key characteristic of the representation of data as link graphs is that these graphs evolve as the corresponding real world phenomena change over time. Understanding such phenomena requires a study of the evolution of their representative graphs and the measures associated with them. However, the large size of these graphs and their evolution over time pose challenges in the computation of measures such as PageRank. This dissertation presents techniques for efficient computation for First-Order Markov Measures (FOMM) on large graphs that evolve over time. PageRank is used as a representative of the class of first-order Markov measures. The objective is to develop work reduction techniques to reduce the computation time for graphs representing relationships between nodes at a single point in time (static graphs) and graphs that evolve over time (evolving graphs). A "divide and conquer" strategy is proposed for the efficient computation of PageRank. This can be achieved by using a novel graph-partitioning technique to divide the graph into a set of subgraphs, the measure for each of which can be computed independently. This strategy differs from existing approaches in that it can be combined with any existing enhancements to PageRank. This approach also leads naturally into the development of an incremental approach for the computation of such ranking metrics, given that these large graphs evolve over a period of time. Finally, I/O efficient methods are proposed to compute first-order Markov measures on large static and evolving graphs. The experimental results for a static single graph (graph at a single time instance) as well as for the incremental computations in evolving graphs, illustrate the usefulness of the presented approach. This dissertation opens new directions for research such as (a) exploration of efficient computational techniques for other classes of measures (b) incremental maintenance of evolving graphs, and (c) analysis of graph growth models and dynamically changing change graphs.en-USComputer ScienceThesis or Dissertation