Date of Award

8-14-2008

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Department of Electrical and Computer Engineering

First Advisor

Barry E. Mullins, PhD

Abstract

A graph is a key construct for expressing relationships among objects, such as the radio connectivity between nodes contained in an unmanned vehicle swarm. The study of such networks may include ranking nodes based on importance, for example, by applying the PageRank algorithm used in some search engines to order their query responses. The PageRank values correspond to a unique eigenvector typically computed by applying the power method, an iterative technique based on matrix multiplication. The first new result described herein is a lower bound on the execution time of the PageRank algorithm that is derived by applying standard assumptions to the scaling value and numerical precision used to determine the PageRank vector. The lower bound on the PageRank algorithm’s execution time also equals the time needed to compute the coarsest equitable partition, where that partition is the basis of all other results described herein. The second result establishes that nodes contained in the same block of a coarsest equitable partition must yield equal PageRank values. The third result is an algorithm that eliminates differences in the PageRank values of nodes contained in the same block if the PageRank values are computed using finite-precision arithmetic. The fourth result is an algorithm that reduces the time needed to find the PageRank vector by eliminating certain dot products when any block in the partition contains multiple vertices. The fifth result is an algorithm that further reduces the time required to obtain the PageRank vector of such graphs by applying the quotient matrix induced by the coarsest equitable partition. Each algorithm’s complexity is derived with respect to the number of blocks contained in the coarsest equitable partition and compared to the PageRank algorithm’s complexity.

AFIT Designator

AFIT-DCS-ENG-08-08

DTIC Accession Number

ADA490530

Download

Share

COinS