Decomposition of the Google pagerank and optimal linking strategy

Konstatin Avrachenkov, Nelli Litvak

Research output: Book/ReportReportProfessional

21 Downloads (Pure)

Abstract

We provide the analysis of the Google PageRank from the perspective of the Markov Chain Theory. First we study the Google PageRank for a Web that can be decomposed into several connected components which do not have any links to each other. We show that in order to determine the Google PageRank for a completely decomposable Web, it is sufficient to compute a subPageRank for each of the connected components separately. Then, we study incentives for the Web users to form connected components. In particular, we show that there exists an optimal linking strategy that benefits a user with links inside its Web community and on the other hand inappropriate links penalize the Web users and their Web communities.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages13
Publication statusPublished - 2004

Publication series

NameMemorandum Faculty of Mathematical Sciences
PublisherUniversity of Twente, Department of Applied Mathematics
No.1712
ISSN (Print)0169-2690

Keywords

  • MSC-68U35
  • MSC-60J20
  • IR-65897
  • EWI-3532
  • METIS-216975
  • MSC-60J22

Cite this

Avrachenkov, K., & Litvak, N. (2004). Decomposition of the Google pagerank and optimal linking strategy. (Memorandum Faculty of Mathematical Sciences; No. 1712). Enschede: University of Twente, Department of Applied Mathematics.
Avrachenkov, Konstatin ; Litvak, Nelli. / Decomposition of the Google pagerank and optimal linking strategy. Enschede : University of Twente, Department of Applied Mathematics, 2004. 13 p. (Memorandum Faculty of Mathematical Sciences; 1712).
@book{6bc84c694ad744ddb3f1f7b86c1b8a6c,
title = "Decomposition of the Google pagerank and optimal linking strategy",
abstract = "We provide the analysis of the Google PageRank from the perspective of the Markov Chain Theory. First we study the Google PageRank for a Web that can be decomposed into several connected components which do not have any links to each other. We show that in order to determine the Google PageRank for a completely decomposable Web, it is sufficient to compute a subPageRank for each of the connected components separately. Then, we study incentives for the Web users to form connected components. In particular, we show that there exists an optimal linking strategy that benefits a user with links inside its Web community and on the other hand inappropriate links penalize the Web users and their Web communities.",
keywords = "MSC-68U35, MSC-60J20, IR-65897, EWI-3532, METIS-216975, MSC-60J22",
author = "Konstatin Avrachenkov and Nelli Litvak",
note = "Imported from MEMORANDA",
year = "2004",
language = "Undefined",
series = "Memorandum Faculty of Mathematical Sciences",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1712",

}

Avrachenkov, K & Litvak, N 2004, Decomposition of the Google pagerank and optimal linking strategy. Memorandum Faculty of Mathematical Sciences, no. 1712, University of Twente, Department of Applied Mathematics, Enschede.

Decomposition of the Google pagerank and optimal linking strategy. / Avrachenkov, Konstatin; Litvak, Nelli.

Enschede : University of Twente, Department of Applied Mathematics, 2004. 13 p. (Memorandum Faculty of Mathematical Sciences; No. 1712).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Decomposition of the Google pagerank and optimal linking strategy

AU - Avrachenkov, Konstatin

AU - Litvak, Nelli

N1 - Imported from MEMORANDA

PY - 2004

Y1 - 2004

N2 - We provide the analysis of the Google PageRank from the perspective of the Markov Chain Theory. First we study the Google PageRank for a Web that can be decomposed into several connected components which do not have any links to each other. We show that in order to determine the Google PageRank for a completely decomposable Web, it is sufficient to compute a subPageRank for each of the connected components separately. Then, we study incentives for the Web users to form connected components. In particular, we show that there exists an optimal linking strategy that benefits a user with links inside its Web community and on the other hand inappropriate links penalize the Web users and their Web communities.

AB - We provide the analysis of the Google PageRank from the perspective of the Markov Chain Theory. First we study the Google PageRank for a Web that can be decomposed into several connected components which do not have any links to each other. We show that in order to determine the Google PageRank for a completely decomposable Web, it is sufficient to compute a subPageRank for each of the connected components separately. Then, we study incentives for the Web users to form connected components. In particular, we show that there exists an optimal linking strategy that benefits a user with links inside its Web community and on the other hand inappropriate links penalize the Web users and their Web communities.

KW - MSC-68U35

KW - MSC-60J20

KW - IR-65897

KW - EWI-3532

KW - METIS-216975

KW - MSC-60J22

M3 - Report

T3 - Memorandum Faculty of Mathematical Sciences

BT - Decomposition of the Google pagerank and optimal linking strategy

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Avrachenkov K, Litvak N. Decomposition of the Google pagerank and optimal linking strategy. Enschede: University of Twente, Department of Applied Mathematics, 2004. 13 p. (Memorandum Faculty of Mathematical Sciences; 1712).