Efficient and Robust Fully Distributed Power Method with an Application to Link Analysis

Methods for link analysis are a key component in search engines for hyperlinked document networks. Documents are assigned an importance score based on the graph structure of the hyperlinks among the documents. At the heart of link analysis protocols we find the problem of calculating the principal eigenvector of a suitable matrix that is defined based on the hyperlink graph. In this paper we introduce a fully distributed method, inspired by the power method, for the calculation of the principal eigenvector of generic matrices, focusing on link analysis as an application. Theoretical results are given that support the correctness of the approach, and experimental validation is presented based on subsets of the WWW. Unlike other proposals, our protocol matches the sequential power method in speed and accuracy for generic matrices even in extremely hostile failure scenarios. This allows for better scalability, fault tolerance and load balancing. Most importantly, it represents an important step towards a flexible, cheap and fully peer-to-peer search method in networks of hyperlinked documents. 1. Authors are listed in alphabetical order. This work was partially supported by the Future and Emerging Technologies unit of the European Commission through Project BISON (IST-2001-38923) and DELIS (IST-2002-001907). 2. Telenor R&D, N-1331 Fornebu, Norway 3. University of Bologna, Mura Anteo Zamboni 7, I-40126 Bologna, Italy, and MTA RGAI, SZTE, Szeged, Hungary