University of Twente Student Theses

Login

Influence of short cycles on the PageRank distribution in scale-free random graphs

Ghasemieh, H. (2016) Influence of short cycles on the PageRank distribution in scale-free random graphs.

[img]
Preview
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 out-degree distributions. We will investigate how the number short cycles including self-loops 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 out-degree 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 self-loops, 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