1
$\begingroup$

According to the example on page in the text book, the graph of documents is as follows:
$1\rightarrow2, 3\rightarrow2, 2\rightarrow1, 2\rightarrow3$
with $\lambda = 0.5$ which would form an adjacency matrix as follows:

Then if we multiply the $\lambda$ by $$A = \begin{bmatrix} 0&1 &0 \\ 1&0 &1 \\ 0&1 &0 \end{bmatrix}$$ we would get a matrix:

$$A = \begin{bmatrix} 0&1/2 &0 \\ 1/2&0 &1/2 \\ 0&1/2 &0 \end{bmatrix}$$

Now if we add $\frac{1 - \lambda}{N}$ to the matrix A, we would get a transition matrix
$$P = \begin{bmatrix} 1/6&2/3 &1/6 \\ 2/3&1/6 &2/3 \\ 1/6&2/3 &1/6 \end{bmatrix}$$ According to the book, the transition probability matrix of surfer's walk with teleportation is: $$P = \begin{bmatrix} 1/6&2/3 &1/6 \\ 5/12&1/6 &5/12 \\ 1/6&2/3 &1/6 \end{bmatrix}$$

I got the answer by:

  • Dividing each 1 in A by the number of 1s in its row.
  • Multiply the resulting matrix by $1 - \lambda$
  • Add $\frac{\lambda}{N}$

My transition matrix and one form book are a bit different. What are the calculations behind the books matrix?

$\endgroup$
0
$\begingroup$

I think I know where I went wrong. This is how the graph looks like: enter image description here

Now we need to create an adjacency matrix based on the number of outgoing links of a page. so the graph looks something like:

enter image description here

We assign each outgoing link of node 2, a probability of $0.5$ since each link has an equal chance of the emission. In simple words, we assign $\frac{1}{L}$ to each outgoing link of the particular node, where $L$ is the number of outgoing links of that node. The matrix $A$ would look something like:

$$ A = \begin{bmatrix} 0 & 1 &0 \\ 1/2 & 0 & 1/2 \\ 0 & 1 & 0 \end{bmatrix} $$ This would give the correct answer.

$\endgroup$
1
  • 1
    $\begingroup$ See also (right) stochastic matrix: row sums should be one. (Since $P_{ij}=\Pr[i\to{j}]$, and each $i$ must go somewhere then $\sum_jP_{ij}=1$.) $\endgroup$
    – GeoMatt22
    Dec 19 '16 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.