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:
“As all historians know, the past is a great darkness, and filled with echoes. Voices may reach us from it; but what they say to us is imbued with the obscurity of the matrix out of which they come; and try as we may, we cannot always decipher them precisely in the clearer light of our day.”
—Margaret Atwood (b. 1939)