## WelCome To The Network Security (Pen Testing) Blog..!

Credit : David Austin

### How to tell who's important

with stationary vector
This shows that page 8 wins the popularity contest. Here is the same figure with the web pages shaded in such a way that the pages with higher PageRanks are lighter.

### Computing I

There are many ways to find the eigenvectors of a square matrix. However, we are in for a special challenge since the matrix H is a square matrix with one column for each web page indexed by Google. This means that H has about n = 25 billion columns and rows. However, most of the entries in H are zero; in fact, studies show that web pages have an average of about 10 links, meaning that, on average, all but 10 entries in every column are zero. We will choose a method known as the power method for finding the stationary vector I of the matrix H. How does the power method work? We begin by choosing a vector I 0 as a candidate for I and then producing a sequence of vectors I k by  The method is founded on the following general principle that we will soon investigate.
 General principle: The sequence I k will converge to the stationary vector I.
We will illustrate with the example above.
 I 0 I 1 I 2 I 3 I 4 ... I 60 I 61 1 0 0 0 0.0278 ... 0.06 0.06 0 0.5 0.25 0.1667 0.0833 ... 0.0675 0.0675 0 0.5 0 0 0 ... 0.03 0.03 0 0 0.5 0.25 0.1667 ... 0.0675 0.0675 0 0 0.25 0.1667 0.1111 ... 0.0975 0.0975 0 0 0 0.25 0.1806 ... 0.2025 0.2025 0 0 0 0.0833 0.0972 ... 0.18 0.18 0 0 0 0.0833 0.3333 ... 0.295 0.295
It is natural to ask what these numbers mean. Of course, there can be no absolute measure of a page's importance, only relative measures for comparing the importance of two pages through statements such as "Page A is twice as important as Page B." For this reason, we may multiply all the importance rankings by some fixed quantity without affecting the information they tell us. In this way, we will always assume, for reasons to be explained shortly, that the sum of all the popularities is one.

### Three important questions

Three questions naturally come to mind:
• Does the sequence I k always converge?
• Is the vector to which it converges independent of the initial vector I 0?
• Do the importance rankings contain the information that we want?
Given the current method, the answer to all three questions is "No!" However, we'll see how to modify our method so that we can answer "yes" to all three. Let's first look at a very simple example. Consider the following small web consisting of two web pages, one of which links to the other:with matrixHere is one way in which our algorithm could proceed:

 I 0 I 1 I 2 I 3=I 1 0 0 0 0 1 0 0
In this case, the importance rating of both pages is zero, which tells us nothing about the relative importance of these pages. The problem is that P2 has no links. Consequently, it takes some of the importance from page P1 in each iterative step but does not pass it on to any other page. This has the effect of draining all the importance from the web. Pages with no links are called dangling nodes, and there are, of course, many of them in the real web we want to study. We'll see how to deal with them in a minute, but first let's consider a new way of thinking about the matrix H and stationary vector I.

### A probabilitistic interpretation of H

with matrix  and eigenvector .In other words, page P2 has twice the importance of page P1, which may feel about right to you. The matrix S has the pleasant property that the entries are nonnegative and the sum of the entries in each column is one. In other words, it is stochastic. Stochastic matrices have several properties that will prove useful to us. For instance, stochastic matrices always have stationary vectors. For later purposes, we will note that S is obtained from H in a simple way. If A is the matrix whose entries are all zero except for the columns corresponding to dangling nodes, in which each entry is 1/n, then S = H + A
and therefore  , an eigenvector corresponding to the eigenvalue 1. It is important to note here that the rate at which  is determined by  . When  is .How does the power method work.In general, the power method is a technique for finding an eigenvector of a square matrix corresponding to the eigenvalue with the largest magnitude. In our case, we are looking for an eigenvector of S corresponding to the eigenvalue 1. Under the best of circumstances, to be described soon, the other eigenvalues ofS will have a magnitude smaller than one; that is,  and that  We will also assume that there is a basis vj of eigenvectors forS with corresponding eigenvalues  . This assumption is not necessarily true, but with it we may more easily illustrate how the power method works. We may write our initial vector I 0 as  Then  Since the eigenvalues  with  have magnitude smaller than one, it follows that  if relatively close to 0, then  relatively quickly. For instance, consider the matrix  The eigenvalues of this matrix are  and  . In the figure below, we see the vectors I k, shown in red, converging to tionary vector I shown in green.Now consider the matrix  Here the eigenvalues are  and  . Notice how the vectors I k converge more slowly to the stationary vector I in this example in which the second eigenvalue has a largermagnitude

### things go wrong

In our discussion above, we assumed that the matrix S had the property that  and Then we see
 I 0 I 1 I 2 I 3 I 4 I 5 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0
In this case, the sequence of vectors I k fails to converge. Why is this? The second eigenvalue of the matrix S satisfies  and so the argument we gaveify the power method no longer holds. To guarantee thatwith stationary vector that the PageRanks assigned to the first four web pages are zero. However, this doesn't feel right: each of these pages has links coming to them from other pages. Clearly, somebody likes these pages! Generally speaking, we want the importance rankings of all pages to be positive. The problem with this example is that it contains a smaller web within it, shown in the blue box below. Links come into this box, but none go out. Just as in the example of the dangling node we discussed above, these pages form an "importance sink" that drains the importance out of the other four pages. This happens when the matrix S is reducible; that is, S can be written in block form as  Indeed, if the matrix S is irreducible, we can guarantee that there is a stationary vector with all positive entries. A web is called strongly connected if, given any two pages, there is a way to follow links from the first page to the second. Clearly, our most recent example is not strongly connected. However, strongly connected webs provide irreducible matrices S. To summarize, the matrix S is stochastic, which implies that it has a stationary vector. However, we need S to also be (a) primitive so that  between 0 and 1. Now suppose that our random surfer moves in a slightly different way. With probability  , he is guided by S. With probability  , he chooses the next page at random. If we denote by 1the  matrix whose entries are all one, we obtain the Google matrix Notice now that G is stochastic as it is a combination of stochastic matrices. Furthermore, all the entries of G are positive, which implies that G is both primitive and irreducible. Therefore, G has a unique stationary vector I that may be found using the power method. The role of the parameter  is an important one. Notice that if  , then G = S. This means that we are working with the original hyperlink structure of the web. However, if  , then  . In other words, the web we are considering has a link between any two pages and we have lost the original hyperlink structure of the web. Clearly, we would like to take  close to 1 so that we hyperlink structure of the web is weighted heavily into the computation. However, there is another consideration. Remember that the rate of convergence of the power method is governed by the magnitude of the second eigenvalue  . For the Google matrix, it has been proven that the magnitude of the second eigenvalue  . This means that when  is close to 1 the convergence of the power method will be very slow. As a compromise between these two competing interests, Serbey Brin and Larry Page, the creators of PageRank, chose  .