Real-World Networks Are Not Always Fast Mixing. (14th December 2020)

• Record Type: Journal Article
• Authors: Qi, Yi; Xu, Wanyue; Zhu, Liwang; Zhang, Zhongzhi
• Is Part Of: Computer journal. Volume 64:Number 2(2021)
• Page Start: 236
• Page End: 244
• Publication Date: 2020-12-14
• Subjects: random walk -- mixing time -- normalized Laplacian -- social networks -- fast mixing; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxaa150
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: The mixing time of random walks on a graph has found broad applications across both theoretical and practical aspects of computer science, with the application effects depending on the behavior of mixing time. It is extensively believed that real-world networks, especially social networks, are fast mixing with their mixing time at most $O(\log N)$ where $N$ is the number of vertices. However, the behavior of mixing time in the real-life networks has not been examined carefully, and exactly analytical research for mixing time in models mimicking real networks is still lacking. In this paper, we first experimentally evaluate the mixing time of various real-world networks with scale-free small-world properties and show that their mixing time is much higher than anticipated. To better understand the behavior of the mixing time for real-world networks, we then analytically study the mixing time of the Apollonian network, which is simultaneously scale-free and small-world. To this end, we derive the recursive relations for all eigenvalues, especially the second largest eigenvalue modulus of the transition matrix, based on which we deduce a lower bound for the mixing time of the Apollonian network, which approximately scales sublinearly with $N$ . Our results indicate that real-world networks are not always fast mixing, which has potential implications in the design of algorithms related to mixing time.