Skip to main content

Authors in a Markov matrix: Which author do people find most inspiring? (24)


Google PageRank

PageRank [2] is a method to compute a ranking of web pages. Sergey Brin and Lawrence Page modeled the adjacency relationship of web pages via link and analyzed the importance of web pages using eigenanalysis. They proposed to use eigenvector as a criterion of the web search. Soon, they established a company called ``Google'' that used this method for their search engine. In their paper, the basic idea had already been proposed by Jon Kleinberg, who considered the web environment can be analyzed by eigenanalysis. Eigenanalysis itself has been studied from 18 century and it is fundamental in linear algebra. Then, the PageRank is not new and these two are just lucky? I don't think so. Maybe many people thought eigenanalysis to use web search at that time, but, these two really implemented this simple and solid idea. Also the size of web is huge and it is not trivial to compute the eigenvector of the web matrix. I think there is a huge difference between just think about and really implemented the method and proved it works.

In this article, my notation is based on Strang's book [9]. However, the PageRank paper [2]'s notation is different.
In PageRank paper [2], page 4, 2nd paragraph explains eigenvalue \(c\) is \(R=cAR\). I use \(\lambda\) of \(Mx = \lambda x\). Therefore, \(\lambda = \frac{1}{c}\).
In the paper, web graph is not ideal or quite incomplete, therefore, it is hard to compute the eigenanalysis. For instance, many link doesn't have the page, or there are loops of the links. They describe these problems and explain how to solve them. Their model is based on the following user: a user clicks links of a web page randomly, but the user also jumps to a totally irrelevant web page sometimes. In principle, PageRank method scans the web, generates the adjacency matrix, processes dangling links and link loops, adds random jumping term to the adjacency matrix, generates Markov matrix, compute the eigenvector. It is easy to say compute the eigenvector, but since the size of web is huge, they proposed the algorithm to efficiently compute it.

When I read this paper first time a few years ago, I was fascinated. It is elegant, simple, solid beauty linear algebra. Moreover, the theory is not only beautiful, but also practically useful. I recommend to read the paper and I think you will enjoy that. I think that impression kept somewhere in my mind, that is the reason when my friend asked me how to analyze the writer's relationship, I was immediately recall this paper. I heard nowadays search engine algorithm is more complex and sophisticated to adapt the spam and other factors, though, I believe this idea is still in the base.

Conclusion of Part1

In this article, we show the following:

  • We can formulate the authors relationship as a graph.
  • We can use mathematical tools, graph theory and linear algebra, to analyze the graph.
  • One of the powerful tool of linear algebra is called eigenanalysis. We can apply this tool to analyze the author relationship. This is the same method that Google does the web search. Google uses it to find the most influential page to show the best search result.

However, this is not the complete story. The Part 2 of this article will answer the first question, ``Which author inspire the people most?''

See you in the Part 2.

Labels:

Comments

Post a Comment

Popular posts from this blog

Why parallelogram area is |ad-bc|?

Here is my question. The area of parallelogram is the difference of these two rectangles (red rectangle - blue rectangle). This is not intuitive for me. If you also think it is not so intuitive, you might interested in my slides. I try to explain this for hight school students. Slides:  A bit intuitive (for me) explanation of area of parallelogram  (to my site, external link) . 
Post a Comment
Read more

Geometric Multiplicity: eignvectors (2)

If eigenvectors of a matrix A are independent, it is a happy property. Because the matrix A can be diagonalized with a matrix S that column vectors are eigenvectors of A . For example, Why this is a happy property of A? Because I can find A's power easily. A^{10} is not a big deal. Because Λ is a diagonal matrix and power of a diagonal matrix is quite simple. A^{10} = SΛ^{10} S^{-1} Then, why if I want to compute power of A ? That is the same reason to find eigenvectors. Eigenvectors are a basis of a matrix. A matrix can be represented by a single scalar. I repeat this again. This is the happy point, a matrix becomes a scalar. What can be simpler than a scalar value. But, this is only possible when the matrix S's columns are independent. Because S^{-1} must be exist. Now I come back to my first question. Is the λ's multiplicity related with the number of eigenvectors? This time I found this has the name. Geometric multiplicity (GM): the number of in...
Post a Comment
Read more

Tezuka Osamu's Black Jack, "Shrinking"

I like several novel authors. My first favorite author is probably Teduka, Osamu. I still love him. The list grows by adding Hoshi, Shinichi, Agatha Christie, Hermann Hesse, and so forth. My first favorite article of Tezuka was Atom as most of the (boy's) Tezuka fans did. But my favorite is Black Jack. I try to summarize one story, it is still quite vivid in my memory. I first read this story when I was 13 - 15 years old. I re-read it at least several times since Black Jack is composed of many short episodes. The title should be "ちぢむ (SHRINKING)" or it might be "縮む(Shrinking)". (It is not so convenient to translate this to English, since English does not have a system to say the exact same word in several ways. So I just simulate it with capital letters.) Black Jack is a genius surgeon, but he does not have the license. In short, his medical activity is illegal. His skill is top level in the world, but, the fee is also out-of-law expensive. In the story ...
Post a Comment
Read more