How to Reach: Discovering Multi-resolution Paths on Large Scale Networks

Reachability query is a fundamental problem which has been studied extensively due to its important role in various application domains, such as social networks, communication networks, biological networks, etc. However, few existing works pay attention to the problem of how two vertices are connected. In this paper, we investigate the problem of discovering paths of multiple resolutions connecting two vertices in large scale networks. We propose a new structure, called Muti-Resolution Path (MRP), to describe how two vertices are connected at different resolution levels. To facilitate the building of MRPs on a network of large scale, we propose a new search structure, called Hierarchical Compressed Network (HCN), which can represent a network at multiple resolution levels and can be built offline. At last, extensive experiments conducted on real-world datasets verify the effectiveness and efficiency of the proposed approach.