Fragile link structure in PageRank computation

Author

Ishii, Hideaki ; Tempo, Roberto

Author_Institution

Dept. of Comput. Intell. & Syst. Sci., Tokyo Inst. of Technol., Yokohama, Japan

fYear

2009

fDate

15-18 Dec. 2009

Firstpage

121

Lastpage

126

Abstract

In this paper, we study the so-called PageRank algorithm used at Google that determines the importance of each webpage. We first provide a brief overview of this algorithm. Then, we consider the problem of computing the changes in PageRank values when the web data contains erroneous link information. Based on interval matrix techniques, we develop an efficient centralized algorithm using linear programming. The theoretical results are verified by means of extensive simulations for a small web with 150 pages and a larger web of 1,200 pages.

Keywords

linear programming; matrix algebra; search engines; Fragile link structure; Google; PageRank computation; Web page; centralized algorithm; interval matrix techniques; linear programming; Computational modeling; Control systems; Distributed computing; Educational technology; Linear matrix inequalities; Linear programming; Multiagent systems; Network servers; Search engines; Telecommunication traffic; Fragile links; Interval matrices; PageRank algorithm; Search engines;

fLanguage

English

Publisher

ieee

Conference_Titel

Decision and Control, 2009 held jointly with the 2009 28th Chinese Control Conference. CDC/CCC 2009. Proceedings of the 48th IEEE Conference on

Conference_Location

Shanghai

ISSN

0191-2216

Print_ISBN

978-1-4244-3871-6

Electronic_ISBN

0191-2216

Type

conf

DOI

10.1109/CDC.2009.5399501

Filename

5399501