Junzhou Zhao, Pinghui Wang, John C.S. Lui, Don Towsley, Xiaohong Guan

Random walk-based sampling methods are gaining popularity and importance incharacterizing large networks. While powerful, they suffer from the slow mixingproblem when the graph is loosely connected, which results in poor estimationaccuracy. Random walk with jumps (RWwJ) can address the slow mixing problem butit is inapplicable if the graph does not support uniform vertex sampling (UNI).In this work, we develop methods that can efficiently sample a graph withoutthe necessity of UNI but still enjoy the similar benefits as RWwJ. We observethat many graphs under study, called target graphs, do not exist in isolation.In many situations, a target graph is related to an auxiliary graph and abipartite graph, and they together form a better connected {\em two-layerednetwork structure}. This new viewpoint brings extra benefits to graph sampling:if directly sampling a target graph is difficult, we can sample it indirectlywith the assistance of the other two graphs. We propose a series of new graphsampling techniques by exploiting such a two-layered network structure toestimate target graph characteristics. Experiments conducted on both syntheticand real-world networks demonstrate the effectiveness and usefulness of thesenew techniques.