Spectral properties of the Google matrix of the World Wide Web and other directed networks

Olivier Giraud

LPT Toulouse et LPTMS Orsay

Mon, Dec. 13th 2010, 14:00

Salle Claude Itzykson, Bât. 774, Orme des Merisiers

Information retrieval in the world wide web is a challenging task. The PageRank algorithm, put forward by Brin and Page in 1998, yields a relevant ranking of webpages and forms the basis of the Google search engine. This algorithm is based on the construction of the Google matrix G, whose principal eigenvector (the PageRank vector) gives a ranking of webpages. \par Here we study the localization properties of eigenvectors of the Google matrix. We consider both real directed networks, such as vocabulary networks of dictionaries and university World Wide Web networks, and network models. We show that the PageRank vector undergoes a delocalization transition when parameters are varied. Another delocalization transition occurs for eigenvectors in the complex plane of eigenvalues. For networks with delocalized PageRank, we expect the efficiency of information retrieval by such algorithms to be strongly affected since the PageRank values have no clear hierarchical structure in this case.

Contact : Gregoire
MISGUICH