Advertisement
Published in:
2011 | OriginalPaper | Chapter
Path Queries on Massive Graphs Based on Multi-granular Graph Partitioning
Authors : Fu-gui He, Yan-ping Zhang, Jie Chen, Ling Zhang
Published in: Rough Sets and Knowledge Technology
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The quotient space theory can represent the world at different granularities and deal with complicated problems hierarchically. In this paper, we introduce a method for finding shortest path on massive graphs based on multi-granular graph partitioning. Path queries into two parts: preprocessing and query step. In preprocessing, we introduce a heuristic local community structure discovery algorithm to decompose massive graphs into some local communities and construct a sequence of hierarchical quotient spaces to describe hierarchy structure on massive graphs. In query, we improve evaluation function of heuristic search method in path query. The implementation works on massive networks. From experimental results, it can be stated that proposed algorithm is effective and efficient in transportation road networks of US.