Taro Takaguchi* and Syuji Miyazaki
Graduate School of Informatics, Kyoto University, Kyoto 606-8501, Japan
*E-mail address: takaguchi@acs.i.kyoto-u.ac.jp
(Received December 2, 2008; Accepted March 17, 2009)
Abstract. Spectral properties of the transition matrix of a small-world network model are studied, and how those properties are relevant to the network structure is elucidated. The distribution of the nearest neighbor eigenvalue spacings changes from a level-crossing to an avoided-crossing type as the rewiring probability p is varied from 0 to 1, which agrees with the known result for the network Laplacian of this model. It is found that the spacing between the largest eigenvalue and the second largest one is proportional to p in the small-world state. This relation is derived by equating the correlation decay time with a mean arrival time for reaching a shortcut end, and is a verification example of the relationship between spectra properties of the transition matrix and structural characteristics of the network.
Keywords: Transition Matrix, Spectrum, Small-World Network