Optimal Scale-Free Small-World Graphs with Minimum Scaling of Cover Time

Abstract

The cover time of random walks on a graph has found wide practical applications in different fields of computer science, such as crawling and searching on the World Wide Web and query processing in sensor networks, with the application effects dependent on the behavior of cover time: the smaller the cover time, the better the application performance. It was proved that over all graphs with $N$ nodes, complete graphs have the minimum cover time $N\log N$. However, complete graphs cannot mimic real-world networks with small average degree and scale-free small-world properties, for which the cover time has not been examined carefully, and its behavior is still not well understood. In this paper, we first experimentally evaluate the cover time for various real-world networks with scale-free small-world properties, which scales as $N\log N$. To better understand the behavior of the cover time for real-world networks, we then study the cover time of three scale-free small-world model networks by using the connection between cover time and resistance diameter. For all the three networks, their cover time also behaves as $N\log N$. This work indicates that sparse networks with scale-free and small-world topology are favorable architectures with optimal scaling of cover time. Our results deepen understanding the behavior of cover time in real-world networks with scale-free small-world structure, and have potential implications in the design of efficient algorithms related to cover time.

References in corpus (16)

• Emergence of scaling in random networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Resolution limit in community detection
• Search in Power-Law Networks
• Intermittent search strategies
• Random walks and diffusion on networks
• Pseudofractal Scale-free Web
• Self-similar disk packings as model spatial scale-free networks
• Evolving Apollonian Networks with Small-world Scale-free topologies
• Statistics of Cycles: How Loopy is your Network?
• Current Flow Group Closeness Centrality for Complex Networks
• Mean first-passage time for random walks in general graphs with a deep trap
• Kirchhoff Index As a Measure of Edge Centrality in Weighted Networks: Nearly Linear Time Algorithms
• Statistics of cycles in large networks
• Coherence Scaling of Noisy Second-Order Scale-Free Consensus Networks