Application of the Google matrix methods for characterization of directed networks

Overview & Synopsis

The complex network theory is a recent field of great importance to study various systems under a graph perspective by considering a collection of interdependent objects. Among the different aspects of the complex networks, this thesis is focused on the analysis of structural properties of directed networks. The primary tool used in this work is the Google matrix method which is derived from the Markov chain theory. The construction of this matrix and its link with Markov chains are explored and the spectral properties of the eigenvalues are discussed with an emphasis on the dominant eigenvalue with its associated eigenvector (PageRank vector). The ranking system given by the PageRank is explained in detail and illustrated through several examples. The systems considered here are the DNA sequences of some animal species, the neural system of the \emph{C.elegans} worm and the ancient strategy board game : the game of Go. In the first case, the statistical properties of symbolic chains are analyzed through a directed network viewpoint and a similarity measure of species based on PageRank is proposed. In the second case, the complementary ranking system (CheiRank vector) is introduced to provide a two dimensional characterization of the directed networks. In the third case, the dominant eigenvectors are used to highlight the most important moves during a game of Go and it is shown that those eigenvectors contain more information than mere frequency counts of the moves. It is also discussed that eigenvectors other than the dominant ones might contain information about some community structures of moves. These applications show how the information brought by the PageRank can be useful in various situations to gain some interesting or original insight about the studied system and how it is helping to understand the organization of the underlying directed network.