摘要 距离查询是图数据挖掘应用中的最基本的操作之一，但是目前的现存查询算法均无法高效处理大规模图数据.针对这个问题，提出建立多级社区中心的标签机制，即首先在原图中将结点按社区划分为多个集合，然后再将各集合中的中心结点建成带权查询子图，经过多次递归操作，最终为各结点建立一个基于社区中心的树状结构标签集，该标签集可以实现利用较短的创建时间和较小的存储代价大幅度提高距离查询的效率.从实验结果可以看出，该方法综合效率明显优于现存的高效算法.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.
References
[1]
Jin R M，Ruan N，Dey S，et al.SCARAB:scaling reachability computation on large graphs［C］//ACM International Conference on Management of Data.Scottsdale，2012:169-180.
[2]
Jin R M，Xiang Y，Ruan N，et al.Path-tree:an efficient reachability indexing scheme for large directed graphs［J］.ACM Transactions on Database Systems，2011，36(1):1-44.
[3]
Wang H X，He H，Yang J，et al.Dual labeling:answering graph reachability queries in constant time［C］//International Conference on Data Engineering.Munich，2006:961-979.
[4]
Bast H，Funke S，Sanders P，et al.Fast routing in road networks with transit nodes［J］.Science，2007，316(5824):316-566.
[5]
Akiba T，Iwata Y，Yoshida Y.Fast exact shortest-path distance queries on large networks by pruned landmark labeling［C］//ACM International Conference on Management of Data.New York，2013:349-360.［7 ］Jin R M，Ruan N，Xiang Y，et al.A highway-centric labeling approach for answering distance queries on large sparse graphs［C］∥ACM International Conference on Management of Data.Scottsdale，2012:445-456.
[6]
Cohen E，Halperin E，Kaplan H，et al.Reachability and distance queries via 2-hop labels［J］.SIAM Journal on Computing，2003，32(5):1338-1355.
[7]
Wei F.Tedi:efficient shortest path query answering on graphs［C］//ACM International Conference on Management of Data.Indianapolis，2010:99-110.
[8]
Zhang Y F，Wang G R，Zhao C K，et al.Utilizing community centers to answer reachability queries for large graphs［C］∥Web Information System and Application Conference.Yangzhou，2013:205-210.
[9]
Milgram S.The small world problem［J］.Psychology Today，1967，67(1):60-67.
[10]
Zhang Y F，Wang G R，Zhao C K，et al.SPTI:efficient answering the shortest path query on large graphs［C］∥IEEE International Congress on Big Data.Santa Clara，2013:195-202.
[11]
Aggarwal C C，Wang H X.Managing and mining graph data［M］.London:Springer-Verlag，2010:181-216.
