Pagerank is a method to compute rankings or importances for every web page by creating a graph using links interconnected throughout the web.
PageRank is defined on some intuitions.
With above, pagerank is defined as follows.
Definition 1 Let be some vector over Web pages that corresponds to a source of rank. Then, the PageRank of a set of WEb pages is an assignment , to the Web pages which satisfies
Terms are defined as follows
Terms | Meaning |
---|---|
Set of pages that points to | |
Number of links from | |
User-defined random jump vector |
The PageRank of is sum of average of pagerank of another pages who have links to the . The is a user-defined random walk factor. is a constant with value . There are some links that point a page that does not have any outgoing linkes. In this case weight on the link is lost. is to compensate that.
The damping factor is a vector with particular value. With probability , the user is considered to jump into a totally irrelevent page, without using any link in the page. This forcefully ejects a user from cycling set of pages where links are formed as a loop.
Using a transition matrix , the equation is written as follows
where is vector of 1. The equation effectively establishes as an eigenvector of .
The was chosen uniformly for calculating pageranks. Value of defines probability to jump to a random page and it is chosen uniformly among all possbile pages.
Personalized pagerank can be obtained by setting to jump into particular set of nodes.
The idea can be used on graphs. For each node , we can create a personlaized by setting to corresponding nodes and to the rest. This will effectively allow a random jump from to particular nodes that has an incoming edge from .
Now the random walk is able to simulate connectivity of a starting node to a node of interest. If two nodes and are geometrically close or have multiple number of paths in between, The pagerank among two will is likely to be higher. To this end, the personalized pagerank over a graph can numerically show how a node is close/similar to another node.
TBA