Sociologists working in the area of social network analysis rely on centrality metrics (e.g., degree, closeness, and betweenness) to rank individuals in a society according to their power, prestige, and prominence. To evaluate these metrics, social networks are represented by graphs: specifically, individuals are represented as nodes, and the fact that individual A respects individual B is represented by a link from the node representing A to the node representing B.

Recently, computer scientists have applied this same abstraction to compute the ``importance'' of a web page based on the Web's underlying topology. Just as the power, prestige, and prominence of individuals in a society is measured in terms of the respect they are granted by others, the significance of web pages can be measured in terms of the references they receive from others. The most prominent application of this idea is the PageRank algorithm, upon which the Google search engine is built.

At Brown, we are investigating efficient methods of link analysis that are applicable to large-scale networks with inherent hierarchical structure: for example, the Web. Our techniques rely on extensions to the theory of stochastic stability, which we are presently developing. The technology we are building is not only of interest in the realm of social network analysis, but it is potentially useful in any field where the theory of Markov chains is applied, most notably equilibrium selection in game theory.