An Improvement Direction for the Simple Random Walk Sampling: Adding Multi-homed Nodes and Reducing Inner Binate Nodes

Graph sampling is an important technology for the network visualization. In this paper, we use the normalized Laplacian spectrum to evaluate diverse biased sampling algorithms on Internet topologies, and numerically find that the simple random walk (SRW) sampling performs much better than other sampling algorithms (e.g., breadth first search, forest fire and random jump). Moreover, we analyze the deficiency of the SRW using the physical meaning of the normalized Laplacian spectrum on the size-independent Internet structure. Finally, we indicate that more multi-homed nodes should be added and more inner binate nodes should be reduced for better performance of the SRW sampling graphs on the normalized Laplacian spectrum which is a powerful tool for the study of size-independent structure embedded in evolving systems.