Webpage rank using Bayes' rule and connected components

[ACCESS RESTRICTED TO THE UNIVERSITY OF MISSOURI-COLUMBIA AT AUTHOR'S REQUEST.] The PageRank is one of the most famous link-structure based webpage ranking algorithm adopted by Google which measures the importance of the webpages by their probability of being visited. However, the bottleneck of the PageRank computing speed is the power iteration process applied on the huge webgraph of WWW, which involves approximately 50 billion webpages. In this thesis a novel method named CCRank is proposed. The CCRank first decomposes the webgraph into mutually disconnected sub-webgraphs, each called a connected component (CC) or simply a block. A Bayes' theorem based block-wise local PageRank computation and weighting scheme are then used to compute the final ranking vector of CCRank, which approximates the one of PageRank algorithm. The computation can be accelerated through distribute the local PageRank computation to multiple processors. Further, unlike PageRank, the updating process for local perturbations is less computational expensive in CCRank. In order to evaluate our approach, the webgraph data is simulated based on real web characteristics. Experimental results indicate that the CCRank computing process is 92% faster on average than PageRank. Moreover, the orders of the top ranked pages in the two approaches are matched above 99%.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Computer science (MU)

Grantor dc:publisher

University of Missouri--Columbia

Year dc:date.issued

2012

Author dc:creator

• Song, Bo

Advisor dc:contributor.advisor

• Zhuang, Xinhua

• ranking algorithm
• webgraph
• connected component

Statement dc:rights

• Access to files is limited to the University of Missouri--Columbia with SSO login.

Language dc:language.iso

eng, English

Handle dc:identifier.uri

http://hdl.handle.net/10355/35442

OAI identifier oai:identifier

oai:mospace.umsystem.edu:10355/35442