Please use this identifier to cite or link to this item:
Title: The performance of page rank algorithm under degree preserving perturbations
Authors: Senanayake, U
Szot, P
Piraveenan, M
Kasthurirathna, D
Keywords: performance
page rank algorithm
under degree
preserving perturbations
Issue Date: 9-Dec-2014
Publisher: IEEE
Citation: U. Senanayake, P. Szot, M. Piraveenan and D. Kasthurirathna, "The performance of page rank algorithm under degree preserving perturbations," 2014 IEEE Symposium on Foundations of Computational Intelligence (FOCI), 2014, pp. 24-29, doi: 10.1109/FOCI.2014.7007803.
Series/Report no.: 2014 IEEE Symposium on Foundations of Computational Intelligence (FOCI);Pages 24-29
Abstract: Page rank is a ranking algorithm based on a random surfer model which is used in Google search engine and many other domains. Because of its initial success in Google search engine, page rank has become the de-facto choice when it comes to ranking nodes in a network structure. Despite the ubiquitous utility of the algorithm, little is known about the effect of topology on the performance of the page rank algorithm. Hence this paper discusses the performance of page rank algorithm under different topological conditions. We use scale-free networks and random networks along with a custom search engine we implemented in order to experimentally prove that the performance of page rank algorithm is deteriorated when the random network is perturbed. In contrast, scale-free topology is proven to be resilient against degree preserving perturbations which aids the page rank algorithm to deliver consistent results across multiple networks that are perturbed to varying proportions. Not only does the top ranking results emerge as stable nodes, but the overall performance of the algorithm is proven to be remarkably resilient which deepens our understanding about the risks in applying page rank algorithm without an initial analysis on the underlying network structure. The results conclusively suggests that while page rank algorithm can be applied to scale-free networks with relatively low risk, applying page rank algorithm to other topologies can be risky as well as misleading. Therefore, the success of the page rank algorithm in real world in search engines such as Google is at least partly due to the fact that the world wide web is a scale-free network. Since the world wide web is constantly evolving, we postulate that if the topological structure of the world wide web changes significantly so that it loses its scale-free nature to some extent, the page rank algorithm will not be as effective.
ISBN: 978-1-4799-4491-0
Appears in Collections:Research Papers - Dept of Computer Science and Software Engineering
Research Papers - IEEE
Research Papers - SLIIT Staff Publications

Files in This Item:
File Description SizeFormat 
  Until 2050-12-31
726.93 kBAdobe PDFView/Open Request a copy

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.