{"id":{"repo_id":"missouri","oai_identifier":"oai:mospace.umsystem.edu:10355/35442"},"canonical_url":"https://search.dev.ndltd.org/etd/missouri/oai:mospace.umsystem.edu:10355/35442","repository":{"repo_id":"missouri","name":"University of Missouri","base_url":"https://mospace.umsystem.edu/oai/request"},"display":{"title":"Webpage rank using Bayes' rule and connected components","abstract":"[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%.","abstract_html":"[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%.","abstract_has_math":false,"creators":["Song, Bo"],"institution":"University of Missouri--Columbia","degree_name":"M.S.","degree_level":"Masters","degree_discipline":"Computer science (MU)","degree_department":null,"school":null,"contributors":[],"advisors":["Zhuang, Xinhua"],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012","date_published":"2012","updated_at":"2026-07-24T03:07:57Z","subjects":["ranking algorithm","webgraph","connected component"],"languages":["eng","English"],"rights":["Access to files is limited to the University of Missouri--Columbia with SSO login."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/10355/35442","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Zhuang, Xinhua"]},{"key":"dc:creator","label":"Author","values":["Song, Bo"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2013-05-31T14:09:54Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2013-05-31T14:09:54Z"]},{"key":"dc:date.issued","label":"Date","values":["2012"]},{"key":"dc:publisher","label":"Institution","values":["University of Missouri--Columbia"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer science (MU)"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Missouri--Columbia"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["ranking algorithm","webgraph","connected component"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]},{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Access to files is limited to the University of Missouri--Columbia with SSO login."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10355/35442"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Title from PDF of title page (University of Missouri--Columbia, viewed on May 31, 2013).","The entire thesis text is included in the research.pdf file; the official abstract appears in the short.pdf file; a non-technical public abstract appears in the public.pdf file.","Thesis advisor: Dr. Xinhua Zhuang","Includes bibliographical references.","M. S. University of Missouri--Columbia 2012.","\"May 2012\""]},{"key":"dc:description.abstract","label":"Abstract","values":["[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%."]},{"key":"dc:title","label":"Title","values":["Webpage rank using Bayes' rule and connected components"]}]}],"canonical_facts":{"dc:contributor.advisor":["Zhuang, Xinhua"],"dc:creator":["Song, Bo"],"dc:date.accessioned":["2013-05-31T14:09:54Z"],"dc:date.available":["2013-05-31T14:09:54Z"],"dc:date.issued":["2012"],"dc:description":["Title from PDF of title page (University of Missouri--Columbia, viewed on May 31, 2013).","The entire thesis text is included in the research.pdf file; the official abstract appears in the short.pdf file; a non-technical public abstract appears in the public.pdf file.","Thesis advisor: Dr. Xinhua Zhuang","Includes bibliographical references.","M. S. University of Missouri--Columbia 2012.","\"May 2012\""],"dc:description.abstract":["[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%."],"dc:identifier.uri":["http://hdl.handle.net/10355/35442"],"dc:language":["English"],"dc:language.iso":["eng"],"dc:publisher":["University of Missouri--Columbia"],"dc:rights":["Access to files is limited to the University of Missouri--Columbia with SSO login."],"dc:subject":["ranking algorithm","webgraph","connected component"],"dc:title":["Webpage rank using Bayes' rule and connected components"],"dc:type":["Thesis"],"thesis:degree_discipline":["Computer science (MU)"],"thesis:degree_level":["Masters"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Missouri--Columbia"]},"updated_at":"2026-07-24T03:07:57Z"}