Efficient Link Analysis: A Hierarchical Voting System

Brown University, Providence RI

Investigators

Abstract

This research project will investigate efficient methods of link analysis that are applicable to large-scale networks with inherent hierarchical structure: in particular, the Web. The techniques rely on extensions to the theory of stochastic stability, a subarea of matrix perturbation theory. Central to the work is an algorithm for computing the stochastically stable distribution of a perturbed Markov process, believed to be the first algorithm that achieves this goal. Embedded within a perturbed Markov process is a hierarchy; consequently, the algorithm for computing stochastically stable distributions is recursive, operating on successively smaller substructures in this hierarchy. The algorithm can efficiently compute the stochastically stable distribution of any Markov process with inherent hierarchical structure. Currently, the most prominent application of link analysis on the Web is the PageRank algorithm, upon which the Google search engine is built. Research will apply the new algorithm to an alternative perturbation of the Web's adjacency matrix, exploiting the hierarchical structure embedded in the Web. An instance of the algorithm that computes importance rankings among web page is called QuickRank. By exploiting the hierarchical structure of the Web, QuickRank could yield dramatic computational gains over PageRank. Moreover, since QuickRank recursively aggregates local rankings into global rankings in an intuitively satisfying way, its importance rankings should be at least as compelling as those output by PageRank. Experiments with QuickRank will evaluate each of these claims. Among the sources of inspiration for this research are sociologists working in the area of social network analysis, who rely on centrality metrics (e.g., degree, closeness, and betweenness) to rank individuals in a society according to their power, prestige, and prominence. But the technology to be developed in this project is not only of interest in the realm of network analysis; it is potentially useful in any field where the theory of Markov chains is applied, most notably equilibrium selection in economic game theory. The research will develop efficient algorithms to tackle the general problem of computing stochastically stable distributions, and it will apply these ideas to study strategic agent behavior in games. Thus, the project has strong multidisciplinary roots; as such, it will contribute to the joint computer science-economics concentration for students at Brown University. It should also help build bridges between students and professors in computer science and economics, and potentially foster future collaborations among applied mathematicians and sociologists.