Efficient Link Analysis: A Hierarchical Voting System

这项研究项目将研究适用于具有内在层次结构的大规模网络的高效链接分析方法：特别是Web。这些技术依赖于随机稳定性理论的扩展，随机稳定性理论是矩阵扰动理论的一个子领域。这项工作的核心是计算扰动马尔可夫过程的随机稳定分布的算法，据信这是第一个实现这一目标的算法。在扰动的马尔可夫过程中嵌入了一个层次结构；因此，用于计算随机稳定分布的算法是递归的，在该层次结构中连续地操作较小的子结构。该算法可以有效地计算任何具有内在层次结构的马尔可夫过程的随机稳定分布。目前，Web上最突出的链接分析应用是PageRank算法，Google搜索引擎就是基于该算法构建的。研究将把新的算法应用于Web邻接矩阵的另一种扰动，利用Web中嵌入的层次结构。该算法的一个实例称为QuickRank，该算法计算网页之间的重要性排名。通过利用Web的层次结构，QuickRank可以比PageRank产生显著的计算收益。此外，由于QuickRank以一种直观令人满意的方式递归地将本地排名聚合为全球排名，其重要性排名至少应该与PageRank输出的排名一样令人信服。QuickRank的实验将对这些说法进行评估。这项研究的灵感来源之一是社交网络分析领域的社会学家，他们依靠中心性度量(例如，程度、亲密度和介数)来根据个人的权力、声望和显赫程度对社会中的个人进行排名。但是，这个项目中将要开发的技术不仅在网络分析领域令人感兴趣，而且在任何应用马尔科夫链理论的领域都有潜在的用处，最显著的是经济博弈论中的均衡选择。该研究将开发有效的算法来解决计算随机稳定分布的一般问题，并将这些思想应用于研究游戏中的策略代理行为。因此，该项目具有强大的多学科基础；因此，它将有助于布朗大学学生的计算机科学-经济学联合专业。它还应该有助于在计算机科学和经济学的学生和教授之间架起桥梁，并有可能促进应用数学家和社会学家之间未来的合作。

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.