Google matrix

Abstract

The Google matrix G of a directed network is a stochastic square matrix with nonnegative matrix elements and the sum of elements in each column being equal to unity. This matrix describes a Markov chain (Markov, 1906-a) of transitions of a random surfer performing jumps on a network of nodes connected by directed links. The network is characterized by an adjacency matrix Aij with elements Aij=1 if node j points to node i and zero otherwise. The matrix of Markov transitions Sij is constructed from the adjacency matrix Aij by normalization of the sum of column elements to unity and replacing columns with only zero elements (dangling nodes) with equal elements 1/N where N is the matrix size (number of nodes). Then the elements of the Google matrix are defined as Gij=αSij+(1−α)/N.