Question

Given the following adjacency matrix, what is the approximate rank vector after one iteration of the power iteration method (use PageRank model with beta=1)?
a) [5/18, 5/18, 4/9]'
b) [1, 0, 0]'
c) [1, 2, 3]'
d) [1/2, 1/3, 0]'

Answer 1

Note: The matrix referred to in the question is: $M = \left[\begin{array}{ccc}1/2&1/3&0\\1/2&1/3&0\\0&1/3&1\end{array}\right]$

Answer:

a) [5/18, 5/18, 4/9]'

Explanation:

The adjacency matrix is  $M = \left[\begin{array}{ccc}1/2&1/3&0\\1/2&1/3&0\\0&1/3&1\end{array}\right]$

To start the power iteration, let us start with an initial non zero approximation,

$X_o = \left[\begin{array}{ccc}1\\1\\1\end{array}\right]$

To get the rank vector for the first Iteration:

$X_1 = MX_0$

$X_1 = \left[\begin{array}{ccc}1/2&1/3&0\\1/2&1/3&0\\0&1/3&1\end{array}\right]\left[\begin{array}{ccc}1\\1\\1\end{array}\right] \\\\X_1 = \left[\begin{array}{ccc}5/6\\5/6\\4/3\end{array}\right]$

Multiplying the above matrix by 1/3

$X_1 = \left[\begin{array}{ccc}5/18\\5/18\\4/9\end{array}\right]$