Abstract
Original language  Undefined 

Awarding Institution 

Supervisors/Advisors 

Thesis sponsors  
Award date  24 Apr 2009 
Place of Publication  Zuthpen 
Publisher  
Print ISBNs  9789036528238 
DOIs  
Publication status  Published  24 Apr 2009 
Keywords
 METIS263943
 IR61071
 Multivariate extremes
 Rank aggregation
 Wikipedia
 Extremal dependencies
 Tauberian theorems
 Regular variation
 Web
 PageRank
 Statistical Analysis
 Power laws
 Preferential attachment
 Stochastic equation
 EWI15767
Cite this
}
Stochastic analysis of web page ranking. / Volkovich, Y.
Zuthpen : University of Twente, 2009. 117 p.Research output: Thesis › PhD Thesis  Research UT, graduation UT › Academic
TY  THES
T1  Stochastic analysis of web page ranking
AU  Volkovich, Y.
N1  10.3990/1.9789036528238
PY  2009/4/24
Y1  2009/4/24
N2  Today, the study of the World Wide Web is one of the most challenging subjects. In this work we consider the Web from a probabilistic point of view. We analyze the relations between various characteristics of the Web. In particular, we are interested in the Web properties that affect the Web page ranking, which is a measure of popularity and importance of a page in the Web. Mainly we restrict our attention on two widelyused algorithms for ranking: the number of references on a page (indegree), and Google’s PageRank. For the majority of selforganizing networks, such as the Web and the Wikipedia, the indegree and the PageRank are observed to follow power laws. In this thesis we present a new methodology for analyzing the probabilistic behavior of the PageRank distribution and the dependence between various power law parameters of the Web. Our approach is based on the techniques from the theory of regular variations and the extreme value theory. We start Chapter 2 with models for distributions of the number of incoming (indegree) and outgoing (outdegree) links of a page. Next, we define the PageRank as a solution of a stochastic equation R d= PN i=1 AiRi+B, where Ri’s are distributed as R. This equation is inspired by the original definition of the PageRank. In particular, N models indegree of a page, and B stays for the user preference. We use a probabilistic approach to show that the equation has a unique nontrivial solution with fixed finite mean. Our analysis based on a recurrent stochastic model for the power iteration algorithm commonly used in PageRank computations. Further, we obtain that the PageRank asymptotics after each iteration are determined by the asymptotics of the random variable with the heaviest tail among N and B. If the tails of N and B are equally heavy, then in fact we get the sum of two asymptotic expressions. We predict the tail behavior of the limiting distribution of the PageRank as a convergence of the results for iterations. To prove the predicted behavior we use another techniques in Chapter 3. In Chapter 3 we define the tail behavior for the models of the indegree and the PageRank distribution using LaplaceStieltjes transforms and the Tauberian theorem. We derive the equation for the LaplaceStieltjes transforms, that corresponds to the general stochastic equation, and obtain our main result that establishes the tail behavior of the solution of the stochastic equation. In Chapter 4 we perform a number of experiments on the Web and the Wikipedia data sets, and on preferential attachment graphs in order to justify the results obtained in Chapters 2 and 3. The numerical results show a good agreement with our stochastic model for the PageRank distribution. Moreover, in Section 4.1 we also address the problem of evaluating power laws in the real data sets. We define several state of the art techniques from the statistical analysis of heavy tails, and we provide empirical evidence on the asymptotic similarity between indegree and PageRank. Inspired by the minor effect of the outdegree distribution on the asymptotics of the PageRank, in Section 4.4 we introduce a new ranking scheme, called PAR, which combines features of HITS and PageRank ranking schemes. In Chapter 5 we examine the dependence structure in the power law graphs. First, we analytically define the tail dependencies between indegree and PageRank of a one particular page by using the stochastic equation of the PageRank. We formally establish the relative importance of the two main factors for high ranking: large indegree and a high rank of one of the ancestors. Second, we compute the angular measures for indegrees, outdegrees and PageRank scores in three large data sets. The analysis of extremal dependence leads us to propose a new rank correlation measure which is particularly plausible for power law data. Finally, in Chapter 6 we apply the new rank correlation measure from Chapter 5 to various problems of rank aggregation. From numerical results we conclude that methods that are defined by the angular measure can provide good precision for the top nodes in large data sets, however they can fail in a small data sets.
AB  Today, the study of the World Wide Web is one of the most challenging subjects. In this work we consider the Web from a probabilistic point of view. We analyze the relations between various characteristics of the Web. In particular, we are interested in the Web properties that affect the Web page ranking, which is a measure of popularity and importance of a page in the Web. Mainly we restrict our attention on two widelyused algorithms for ranking: the number of references on a page (indegree), and Google’s PageRank. For the majority of selforganizing networks, such as the Web and the Wikipedia, the indegree and the PageRank are observed to follow power laws. In this thesis we present a new methodology for analyzing the probabilistic behavior of the PageRank distribution and the dependence between various power law parameters of the Web. Our approach is based on the techniques from the theory of regular variations and the extreme value theory. We start Chapter 2 with models for distributions of the number of incoming (indegree) and outgoing (outdegree) links of a page. Next, we define the PageRank as a solution of a stochastic equation R d= PN i=1 AiRi+B, where Ri’s are distributed as R. This equation is inspired by the original definition of the PageRank. In particular, N models indegree of a page, and B stays for the user preference. We use a probabilistic approach to show that the equation has a unique nontrivial solution with fixed finite mean. Our analysis based on a recurrent stochastic model for the power iteration algorithm commonly used in PageRank computations. Further, we obtain that the PageRank asymptotics after each iteration are determined by the asymptotics of the random variable with the heaviest tail among N and B. If the tails of N and B are equally heavy, then in fact we get the sum of two asymptotic expressions. We predict the tail behavior of the limiting distribution of the PageRank as a convergence of the results for iterations. To prove the predicted behavior we use another techniques in Chapter 3. In Chapter 3 we define the tail behavior for the models of the indegree and the PageRank distribution using LaplaceStieltjes transforms and the Tauberian theorem. We derive the equation for the LaplaceStieltjes transforms, that corresponds to the general stochastic equation, and obtain our main result that establishes the tail behavior of the solution of the stochastic equation. In Chapter 4 we perform a number of experiments on the Web and the Wikipedia data sets, and on preferential attachment graphs in order to justify the results obtained in Chapters 2 and 3. The numerical results show a good agreement with our stochastic model for the PageRank distribution. Moreover, in Section 4.1 we also address the problem of evaluating power laws in the real data sets. We define several state of the art techniques from the statistical analysis of heavy tails, and we provide empirical evidence on the asymptotic similarity between indegree and PageRank. Inspired by the minor effect of the outdegree distribution on the asymptotics of the PageRank, in Section 4.4 we introduce a new ranking scheme, called PAR, which combines features of HITS and PageRank ranking schemes. In Chapter 5 we examine the dependence structure in the power law graphs. First, we analytically define the tail dependencies between indegree and PageRank of a one particular page by using the stochastic equation of the PageRank. We formally establish the relative importance of the two main factors for high ranking: large indegree and a high rank of one of the ancestors. Second, we compute the angular measures for indegrees, outdegrees and PageRank scores in three large data sets. The analysis of extremal dependence leads us to propose a new rank correlation measure which is particularly plausible for power law data. Finally, in Chapter 6 we apply the new rank correlation measure from Chapter 5 to various problems of rank aggregation. From numerical results we conclude that methods that are defined by the angular measure can provide good precision for the top nodes in large data sets, however they can fail in a small data sets.
KW  METIS263943
KW  IR61071
KW  Multivariate extremes
KW  Rank aggregation
KW  Wikipedia
KW  Extremal dependencies
KW  Tauberian theorems
KW  Regular variation
KW  Web
KW  PageRank
KW  Statistical Analysis
KW  Power laws
KW  Preferential attachment
KW  Stochastic equation
KW  EWI15767
U2  10.3990/1.9789036528238
DO  10.3990/1.9789036528238
M3  PhD Thesis  Research UT, graduation UT
SN  9789036528238
PB  University of Twente
CY  Zuthpen
ER 