title: Eigenvalues for the transition matrix of a small-world scale-free network: Explicit expressions and applications.
abstract: The eigenvalues of the transition matrix for random walks on a network play a significant role in the structural and dynamical aspects of the network. Nevertheless, it is still not well understood how the eigenvalues behave in small-world and scale-free networks, which describe a large variety of real systems. In this paper, we study the eigenvalues for the transition matrix of a network that is simultaneously scale-free, small-world, and clustered. We derive explicit simple expressions for all eigenvalues and their multiplicities, with the spectral density exhibiting a power-law form. We then apply the obtained eigenvalues to determine the mixing time and random target access time for random walks, both of which exhibit unusual behaviors compared with those for other networks, signaling discernible effects of topologies on spectral features. Finally, we use the eigenvalues to count spanning trees in the network.
authors.affiliation: School of Computer Science, Fudan University, Shanghai 200433, China and Shanghai Key Laboratory of Intelligent Information Processing, Fudan University, Shanghai 200433, China.
authors.forename: Zhongzhi
authors.initials: Z
authors.lastname: Zhang
authors.affiliation: School of Computer Science, Fudan University, Shanghai 200433, China and Shanghai Key Laboratory of Intelligent Information Processing, Fudan University, Shanghai 200433, China.
authors.forename: Yuan
authors.initials: Y
authors.lastname: Lin
authors.affiliation: School of Computer Science, Fudan University, Shanghai 200433, China and Shanghai Key Laboratory of Intelligent Information Processing, Fudan University, Shanghai 200433, China.
authors.forename: Xiaoye
authors.initials: X
authors.lastname: Guo