Abstract: Distance querying is one of the most fundamental operations in many graph data mining applications. However， most of the previous methods cannot handle large graphs， especially those with more than a hundred thousand vertices. To solve this problem， a multilevel community center labels index structure was proposed. Firstly， the vertices of the original graph were divided into different communities. Then a weighted query sub-graph was constructed by each community center. Finally， a tree-like label set was built for every vertex. The query efficiency could be improved greatly with small time and storage cost. The experimental result showed that the overall efficiency of this approach is significantly better than those of the-state-of-the-art algorithms.

Key words: multilevel community center, label, large graphs, distance query, weighted query