Página Inicial CNEA Laboratorio TANDAR Página Inicial TANDAR Historia del acelerador TANDAR Web interno Web mail
artículo con referato
"Google matrix"
Leonardo Ermann, Klaus Frahm and Dima L. Shepelyansky
Scholarpedia 11(11):30944 (2016) (artículo electrónico con referato)
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, where the damping factor 0 < α < 1 is the probability that a random surfer follows a link according to the stochastic matrix S while with probability 1-α he may jump to any network node. In this form the Google matrix was introduced by Brin and Page in 1998 (Brin, 1998-a) for the description of the World Wide Web (WWW). The right eigenvector of G with the largest (by modulus) unit eigenvalue is the PageRank vector whose non-negative elements correspond to the stationary probability to find a random surfer on a given node. The product of two Google matrices is also a Google matrix. The above construction of S can be directly generalized to the case of weighted transitions with the sum of elements in each column of S equal to unity. The general spectral properties of G matrix are described below with concrete examples of various real networks. An example image of G is shown in Figure 1 for the Wikipedia network. The Google matrix belongs to the class of Perron-Frobenius operators which appear in the description of dynamical chaotic systems (Brin, 2002-b) and related Ulam networks (Ulam, 1960-b,Ermann, 2010-a).
DEPARTAMENTO FISICA TEORICA
Contacto
Av. Gral Paz y Constituyentes, San Martín, Pcia. de Buenos Aires, Argentina
Tel: (54-11) 6772-7007 - Fax: (54-11) 6772-7121