Network Analysis Based on Statistical-Thermodynamical Formalism

Random walk on a graph is analyzed on the basis of the statistical-thermodynamics formalism to find phase transitions in network structure. Each phase can be related to a characteristic local structure of the network. For this purpose, the generalized transition matrix or the generalized Frobenius-Perron operator is introduced, whose largest eigenvalue yields statistical structure functions. The weighted visiting frequency related to the Gibbs probability measure, which turn out to be useful to extract characteristic local structures, is obtained from the inner product of the right and left eigenvectors corresponding to the largest eigenvalue. An algorithm to extract the characteristic local structure of each phase is also suggested based on this weighted visiting frequency.