University of Twente Student Theses
Influence of short cycles on the PageRank distribution in scalefree random graphs
Ghasemieh, H. (2016) Influence of short cycles on the PageRank distribution in scalefree random graphs.

PDF
4MB 
Abstract:  PageRank algorithms are widely used for ranking/scoring the nodes of a network, e.g for world wide web or citation networks. In this project we will consider directed networks, generated using configuration models, with fixed in and outdegree distributions. We will investigate how the number short cycles including selfloops will affect the distribution of PageRank in such networks. For this, we firstly propose an algorithm to control the number of short cycles in the artificially generated networks with fixed in and outdegree distribution. Afterward we examine how the PageRank distribution is affected by varying the number of short cycles in such networks. As we will see, by increasing the fraction of selfloops, the number of nodes with high PageRank increases. However, the effect of cycles of size larger than one, is in contrast with this observation, i.e., the fraction of nodes with high PageRank decreases by increasing the number of these cycles. We will explain and prove the former observation by asymptotic analysis of stochastic equations as a representation of PageRanks, and for the latter we discuss an analytical example to provide an insight about what is happening. 
Item Type:  Essay (Master) 
Faculty:  EEMCS: Electrical Engineering, Mathematics and Computer Science 
Subject:  31 mathematics, 54 computer science 
Programme:  Applied Mathematics MSc (60348) 
Link to this item:  http://purl.utwente.nl/essays/71417 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page