Efficient Link Analysis: A Hierarchical Voting System

高效的链接分析：分层投票系统

• 批准号: 0534586
• 负责人: Amy Greenwald
• 金额: --
• 依托单位: Brown University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-12-01 至 2010-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0534586&HistoricalAwards=false
• 关键词: Efficient; Link; Analysis; Hierarchical; Voting

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.

本研究课题将探讨适用于具有固有层次结构的大规模网络（特别是Web）的链接分析的有效方法。该技术依赖于扩展的随机稳定性理论，矩阵摄动理论的一个子区域。这项工作的核心是一个算法，用于计算随机稳定分布的扰动马尔可夫过程，被认为是第一个算法，实现了这一目标。嵌入在扰动马尔可夫过程是一个层次结构;因此，算法计算随机稳定分布是递归的，在这个层次结构中连续较小的子结构上操作。该算法可以有效地计算任何具有内在层次结构的马尔可夫过程的随机稳定分布。目前，链接分析在Web上最突出的应用是PageRank算法，Google搜索引擎就是基于该算法构建的。研究将新算法应用于Web邻接矩阵的替代扰动，利用嵌入在Web中的层次结构。计算网页之间的重要性排名的算法的一个实例被称为QuickRank。通过利用网络的层次结构，QuickRank可以产生比PageRank更大的计算收益。此外，由于QuickRank递归地以直观的方式将局部排名聚合为全局排名，因此其重要性排名至少应该与PageRank输出的排名一样引人注目。QuickRank的实验将评估这些说法中的每一个。这项研究的灵感来源之一是在社交网络分析领域工作的社会学家，他们依赖于中心性指标（例如，程度、接近程度和中间程度），根据个人的权力、声望和声望对社会中的个人进行排名。但是，在这个项目中开发的技术不仅在网络分析领域有意义，它在应用马尔可夫链理论的任何领域都有潜在的用处，最值得注意的是经济博弈论中的均衡选择。这项研究将开发有效的算法来解决计算随机稳定分布的一般问题，并将这些想法应用于研究游戏中的策略代理行为。因此，该项目具有强大的多学科根源;因此，它将有助于布朗大学学生的联合计算机科学-经济学集中。它还应该有助于在计算机科学和经济学的学生和教授之间建立桥梁，并有可能促进应用数学家和社会学家之间的未来合作。