谷歌的Pagerank算法详解.pptVIP

* * * * * * * * * * * * * * * * PageRank Algorithm 牧马城市 PageRank Finding Important Nodes PageRank Relative Importance Discovering Network Modules Inferring Important Paths PageRank Web pages are organized in a network. Each webpage is represented as a node. Each hyperlink is a directed edge The entire web can be viewed as a directed graph. PageRank PageRank is a numeric value that represents how important a page is on the web. Webpage importance One page links to another page = A vote for the other page A link from page A to page B is a vote on A to B. If page A is more important itself, then the vote of A to B should carry more weight. More votes = More important the page must be How can we model this importance? The Random Surfer Model PageRank = A model of user behaviour A surfer clicks on links at random with no regard towards content. PageRank Importance Computation The importance of a page is distributed to pages that it points to. The importance of a page is the aggregation of the importance shares of the pages that points to it. If a page has 5 outlinks, the importance of the page is divided into 5 and each link receives one fifth share of the importance. PageRank Algorithm PR(A) = (1-d) + d (PR(T1) / C(T1) + ….. + PR(Tn) / C(Tn) ) Now we refer PageRank as “PR” PR(A) is the PageRank of page A PR(Ti) is the PageRank of pages Ti which link to page A C(Ti) is the number of outbound links on page Ti d is a damping factor which can be set between 0 and 1 (usually set to 0.85) A page’s PageRank = 0.15 + 0.85 * (a “share” of the PageRank of every page that links to it) “share” = the linking page’s PageRank divided by the number of outbound links on the page Page A Page B PR = 1 PR = 1 PR(A) = 0.15 + 0.85 * PR(B) PR(B) = 0.15 + 0.85 * PR(A) We cant work out As PageRank until we know Bs PageRank, and we cant work out Bs PageRank until we know As PageRank. Iterations are necessary to calculate the most accurate values by using inaccurate values