Efficiently indexing shortest paths by exploiting symmetry in graphs

ABSTRACT

Shortest path queries (SPQ) are essential in many graph analysis and mining tasks. However, answering shortest path queries on-the-fly on large graphs is costly. To online answer shortest path queries, we may materialize and index shortest paths. However, a straightforward index of all shortest paths in a graph of N vertices takes O(N²) space. In this paper, we tackle the problem of indexing shortest paths and online answering shortest path queries. As many large real graphs are shown richly symmetric, the central idea of our approach is to use graph symmetry to reduce the index size while retaining the correctness and the efficiency of shortest path query answering. Technically, we develop a framework to index a large graph at the orbit level instead of the vertex level so that the number of breadth-first search trees materialized is reduced from O(N) to O(|Δ|), where |Δ| ≤ N is the number of orbits in the graph. We explore orbit adjacency and local symmetry to obtain compact breadth-first-search trees (compact BFS-trees). An extensive empirical study using both synthetic data and real data shows that compact BFS-trees can be built efficiently and the space cost can be reduced substantially. Moreover, online shortest path query answering can be achieved using compact BFS-trees.

REFERENCES

• 1: Rakesh Agrawal , H. V. Jagadish, Direct Algorithms for Computing the Transitive Closure of Database Relations, Proceedings of the 13th International Conference on Very Large Data Bases, p.255-266, September 01-04, 1987
• 2: R. Agrawal , H. V. Jagadish, Algorithms for Searching Massive Graphs, IEEE Transactions on Knowledge and Data Engineering, v.6 n.2, p.225-238, April 1994 [doi>10.1109/69.277767]
• 3: A.-L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286, 1999.
• 4: N. Biggs. Algebraic Graph Theory. Cambridge University Press, 1974.
• 5: S. Boccalettia, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang. Complex networks: Structure and dynamics. Physics Reports, 424, 2006.
• 6: Edward P. F. Chan , Ning Zhang, Finding shortest paths in large network systems, Proceedings of the 9th ACM international symposium on Advances in geographic information systems, November 09-10, 2001, Atlanta, Georgia, USA [doi>10.1145/512161.512197]
• 7: Li Chen , Amarnath Gupta , M. Erdem Kurul, Stack-based algorithms for pattern matching on DAGs, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 8: Boris V. Cherkassky , Andrew V. Goldberg , Tomasz Radzik, Shortest paths algorithms: theory and experimental evaluation, Mathematical Programming: Series A and B, v.73 n.2, p.129-174, May 31, 1996 [doi>10.1007/BF02592101]
• 9: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 10: E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1959.
• 11: Ben D. MacArthur , Rubén J. Sánchez-García , James W. Anderson, Note: Symmetry in complex networks, Discrete Applied Mathematics, v.156 n.18, p.3525-3531, November, 2008 [doi>10.1016/j.dam.2008.04.008]
• 12: C. Godsil and G. Royle. Algebraic Graph Theory, volume 207 of Graduate Texts in Mathematics. Springer, 2001.
• 13: Hao He , Haixun Wang , Jun Yang , Philip S. Yu, Compact reachability labeling for graph-structured data, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099708]
• 14: David S. Johnson, The genealogy of theoretical computer science: a preliminary report, ACM SIGACT News, v.16 n.2, p.36-49, Summer 1984 [doi>10.1145/1008959.1008960]
• 15: J. Lauri and R. Scapellato. Topics in Graph Automorphisms and Reconstruction. Cambridge University Press, 2003.
• 16: Hongjun Lu, New Strategies for Computing the Transitive Closure of a Database Relation, Proceedings of the 13th International Conference on Very Large Data Bases, p.267-274, September 01-04, 1987
• 17: B. D. McKay. Practical graph isomorphism. Congressus Numerantium, 30.
• 18: Romualdo Pastor-Satorras , Alessandro Vespignani, Evolution and Structure of the Internet: A Statistical Physics Approach, Cambridge University Press, New York, NY, 2004
• 19: Syed Asad Rahman , Dietmar Schomburg, Observing local and global properties of metabolic pathways: 'load points' and 'choke points' in the metabolic networks, Bioinformatics, v.22 n.14, p.1767-1774, July 2006 [doi>10.1093/bioinformatics/btl181]
• 20: J. J. Rotman. An Introduction to the Theory of Groups, Fourth Edition. Springer, 1999.
• 21: Hanan Samet , Jagan Sankaranarayanan , Houman Alborzi, Scalable network distance browsing in spatial databases, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376623]
• 22: Ralf Schenkel , Anja Theobald , Gerhard Weikum, Efficient Creation and Incremental Maintenance of the HOPI Index for Complex XML Document Collections, Proceedings of the 21st International Conference on Data Engineering, p.360-371, April 05-08, 2005 [doi>10.1109/ICDE.2005.57]
• 23: J. Scott. Social Network Analysis: A Handbook, Second Edition. Sage Publications, London, 2000.
• 24: G. Tinhofer and M. Klin. Algebraic combinatorics in mathematical chemistry. Methods and algorithms. III. Graph Invariants and Stabilization Methods (Preliminary Version). Technical Report, TUM-M9902, Technische Universitat Munchen, 1999.
• 25: Silke Trißl , Ulf Leser, Fast and practical indexing and querying of very large graphs, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247573]
• 26: Haixun Wang , Hao He2 , Jun Yang , Philip S. Yu , Jeffrey Xu Yu, Dual Labeling: Answering Graph Reachability Queries in Constant Time, Proceedings of the 22nd International Conference on Data Engineering, p.75, April 03-07, 2006 [doi>10.1109/ICDE.2006.53]
• 27: S. Wasserman and K. Faust. Social Networks Analysis. Cambridge University Press, Cambridge, 1994.
• 28: Y. Xiao, B. D. MacArthur, H. Wang, M. Xiong, and W. Wang. Network quotients: Structural skeletons of complex systems. Physical Review E, 78.
• 29: Y. Xiao, W. Wu, H. Wang, M. Xiong, and W. Wang. Symmetry-based structure entropy of complex networks. Physica A, 387.
• 30: Y. Xiao, M. Xiong, W. Wang, and H. Wang. Emergence of symmetry in complex networks. Physical Review E, 77.