Introduction to PageRank Algorithm
In the last class we built the intuitions and notions for understanding Google's
PageRank algorithm, using Linear Algebra and Graph Theory tools.
For this, it was essential the idea of auto reference: this is when items in a network
can interact in a circular manner:
An example for this can be found in many areas: in bibliometric can refer to the fact
that an author can cite another author which can cite the first author as well. Of course in the
realm of Internet architecture: hyperlinks can have a circular pattern where sites lead to
sites which can link to the first ones.
Two main ideas were used to understand the PageRank algorithm: the first idea was
explained using the analogy of ranking different football teams after a cup. In this situation,
different wins are going to have different qualities, where winning a team with more
prestige is going to mean more prestige for the victory.
Here, the strength attributed to a team depends on all the teams it has played
with. This problem, of comparing different teams with each other, was expressed as a matrix
problem, where we defined a matrix that took into account the different wins and ties all the
teams had with each other and another matrix that ranked all these results.
This expressed a linear algebra formulation that allowed us to compare all teams and
obtain a ranking of them in the form of an eigenvalue problem (Keener’s method).
Then, the second core idea was presented as an analogy in geography: if you
randomly travel across a network of cities, there are cities you are forced to visit or
get through more often. This can be used as a measurement of the importance of nodes in
a network.
Larry Page and Sergey Brin (authors of Google's PageRank) used this idea and
called it the random surfer: a web surfer travels along randomly following various hyperlinks
in each web page he encounters. Eventually, if he has spent more time on a page it means
that many other web pages link to this page, and this is a measure of the importance of each
node in the network.
To express this situation, we denote an Adjacency Matrix (A), in which each
element represents the presence or not (a 1 or a 0) of a direct path between every node in
𝑘
the network. Then, the different powers of the matrix (𝐴 ) counts the number of paths
between each node of length k.
In this way, we can find a way to measure the number of paths leading to every node,
and this is a possible way to rank how accessible each node is.
So, we can define several and important intuitions of the PageRank algorithm:
1. My reputation depends on the reputation of the ones that endorse me (links leading
to my webpage).
2. Accessibility provides reputation.
3. Reputation flows through the network (nodes with more connections receives more
reputation)
We can define a first approximation to Page Rank as:
𝑟(𝑃𝑗 )
𝑟(𝑃𝑖 ) = ∑
𝑃𝑗 ∈ 𝐵𝑝𝑖
|𝑃𝑗 |
Where:
● 𝑟(𝑃𝑖 ) is the reputation of page 𝑖.
● 𝐵𝑝𝑖 is the list of all the pages that backlinks to 𝑖.
● 𝑟(𝑃𝑗 ) is the reputation of each page 𝑗.
● |𝑃𝑗 | is the total number of outlinks of 𝑗.
Is clearly that the equation states that the reputation (ranking) of a web page 𝑖 is the
sum of the ranking of all the web pages that points to 𝑖. The intuition behind the term |𝑃𝑗 | is
that if a page 𝑗 links to 𝑖, the contribution for the ranking will be higher if 𝑃𝑗 has fewer links
to other pages (as if the links are more prestigious). On the contrary, if 𝑃𝑗 contains many
links to many pages, the contribution will be lower.
Luis Alejandro Vivas Colmenares.