Efficient Link Analysis
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.
Project status: Active
Project Home Page: http://www.cs.brown.edu/people/amy/link.html
People
| Amy Greenwald |
| John R. Wicks |
Funding
Publications
Wicks, J. R., and Greenwald, A. An Algorithm for Computing Stochastically Stable Distributions with Applications to Multiagent Learning in Repeated Games. In Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence (2005), pp. 623-632.
Wicks, J. R., and Greenwald, A. A Quotient Construction on Markov Chains with Applications to the Theory of Generalized Simulated Annealing. In Proceedings of the Ninth International Symposium on Artificial Intelligence and Mathematics (2005). [ postscript | pdf ]
| Page Owner: Webmaster | Last Modified: Mon Oct 23 14:57:09 2006 |