Adjacency Matrix A and Markov Matrix S
In order to generate the Google matrix G, we must first generate an adjacency matrix A which represents the relations between pages or nodes.
Assuming there are N pages, we can fill out A by doing the following:
- A matrix element is filled with 1 if node has a link to node, and 0 otherwise; this is the adjacency matrix of links.
- A related matrix S corresponding to the transitions in a Markov chain of given network is constructed from A by dividing the elements of column "j" by a number of where is the total number of outgoing links from node j to all other nodes. The columns having zero matrix elements, corresponding to dangling nodes, are replaced by a constant value 1/N. Such a procedure adds a link from every sink, dangling state to every other node.
- Now by the construction the sum of all elements in any column of matrix S is equal to unity. In this way the matrix S is mathematically well defined and it belongs to the class of Markov chains and the class of Perron-Frobenius operators. That makes S suitable for the PageRank algorithm.
Read more about this topic: Google Matrix
Famous quotes containing the word matrix:
““The matrix is God?”
“In a manner of speaking, although it would be more accurate ... to say that the matrix has a God, since this being’s omniscience and omnipotence are assumed to be limited to the matrix.”
“If it has limits, it isn’t omnipotent.”
“Exactly.... Cyberspace exists, insofar as it can be said to exist, by virtue of human agency.””
—William Gibson (b. 1948)