You Peng
Skip Abstract Section
Abstract
Graph is a ubiquitous structure representing entities and their relationships applied in many areas such as social networks, web graphs, and biological networks. One of the fundamental tasks in graph analytics is to investigate the relations between two vertices (e.g., users, items and entities) such as how a vertex A influences another vertex B, or to what extent A and B are similar to each other, based on the graph topology structure. For this purpose, we study the problem of hop-constrained s-t simple path enumeration in this paper, which aims to list all simple paths from a source vertex s to a target vertex t with hop-constraint k. We first propose a polynomial delay algorithm, namely BC-DFS, based on barrier-based pruning technique. Then a join-oriented algorithm, namely JOIN, is designed to further enhance the query response time. On the theoretical side, BC-DFS is a polynomial delay algorithm with O(km) time per output where m is the number of edges in the graph. This time complexity is the same as the best known theoretical result for the polynomial delay algorithms of this problem. On the practical side, our comprehensive experiments on 15 real-life networks demonstrate the superior performance of the BC-DFS algorithm compared to the state-of-the-art techniques. It is also reported that the JOIN algorithm can further significantly enhance the query response time.
- J. E. Beasley and N. Christofides. An algorithm for the resource constrained shortest path problem. Networks, 19(4):379--394, 1989.Google Scholar
Cross Ref
- A. Bernstein and S. Chechik. Incremental topological sort and cycle detection in expected total time. In SODA, pages 21--34, 2018.Google ScholarDigital Library
- E. Birmelé, R. A. Ferreira, R. Grossi, A. Marino, N. Pisanti, R. Rizzi, and G. Sacomoto. Optimal listing of cycles and st-paths in undirected graphs. In SODA, pages 1884--1896, 2013.Google ScholarCross Ref
- K. Böhmová, L. Häfliger, M. Mihalák, T. Pröger, G. Sacomoto, and M.-F. Sagot. Computing and listing st-paths in public transportation networks. Theory of Computing Systems, 62(3):600--621, 2018.Google ScholarDigital Library
- G. G. Cash. The number of n-cycles in a graph. Applied Mathematics and Computation, 184(2):1080--1083, 2007.Google ScholarCross Ref
- L. Chang, X. Lin, L. Qin, J. X. Yu, and J. Pei. Efficiently computing top-k shortest path join. In EDBT 2015-18th International Conference on Extending Database Technology, Proceedings, 2015.Google Scholar
- Y. Chen, Y. Fang, R. Cheng, Y. Li, X. Chen, and J. Zhang. Exploring communities in large profiled graphs. IEEE Transactions on Knowledge and Data Engineering, 2018.Google Scholar
- G. L. D. and K. N. P. Identifying certain types of parts of a graph and computing their number. Ukrainian Mathematical Journal, 24(3):313--321, 1972.Google Scholar
- E. de Queirós Vieira Martins and M. M. B. Pascoal. A new implementation of yen's ranking loopless paths algorithm. 4OR, 1(2):121--133, 2003.Google Scholar
- D. Eppstein. Finding the k shortest paths. SIAM Journal on computing, 28(2):652--673, 1998.Google Scholar
- Y. Fang, R. Cheng, Y. Chen, S. Luo, and J. Hu. Effective and efficient attributed community search. The VLDB Journal The International Journal on Very Large Data Bases, 26(6):803--828, 2017.Google ScholarDigital Library
- Y. Fang, R. Cheng, X. Li, S. Luo, and J. Hu. Effective community search over large spatial graphs. Proceedings of the VLDB Endowment, 10(6):709--720, 2017.Google ScholarDigital Library
- Y. Fang, R. Cheng, S. Luo, and J. Hu. Effective community search for large attributed graphs. Proceedings of the VLDB Endowment, 9(12):1233--1244, 2016.Google ScholarDigital Library
- Y. Fang, R. Cheng, S. Luo, J. Hu, and K. Huang. C-explorer: browsing communities in large graphs. Proceedings of the VLDB Endowment, 10(12):1885--1888, 2017.Google ScholarDigital Library
- Y. Fang, X. Huang, L. Qin, Y. Zhang, W. Zhang, R. Cheng, and X. Lin. A survey of community search over big graphs. The VLDB Journal, Jul 2019.Google ScholarCross Ref
- Y. Fang, Z. Wang, R. Cheng, X. Li, S. Luo, J. Hu, and X. Chen. On spatial-aware community search. IEEE Transactions on Knowledge and Data Engineering, 31(4):783--798, 2018.Google ScholarDigital Library
- Y. Fang, Z. Wang, R. Cheng, H. Wang, and J. Hu. Effective and efficient community search over large directed graphs. IEEE Transactions on Knowledge and Data Engineering, 2018.Google Scholar
- Y. Fang, K. Yu, R. Cheng, L. V. S. Lakshmanan, and X. Lin. Efficient algorithms for densest subgraph discovery. Proc. VLDB Endow., 12(11):1719--1732, July 2019.Google ScholarDigital Library
- A. Freitas, J. C. P. da Silva, E. Curry, and P. Buitelaar. A distributional semantics approach for selective reasoning on commonsense graph knowledge bases. In International Conference on Applications of Natural Language to Data Bases/Information Systems, pages 21--32. Springer, 2014.Google ScholarCross Ref
- J. Gao, R. Jin, J. Zhou, J. X. Yu, X. Jiang, and T. Wang. Relational approach for shortest path discovery over large graphs. Proceedings of the VLDB Endowment, 5(4):358--369, 2011.Google ScholarDigital Library
- J. Gao, H. Qiu, X. Jiang, T. Wang, and D. Yang. Fast top-k simple shortest paths discovery in graphs. In Proceedings of the 19th ACM international conference on Information and knowledge management, pages 509--518. ACM, 2010.Google ScholarDigital Library
- P. Giscard, N. Kriege, and R. C. Wilson. A general purpose algorithm for counting simple cycles and simple paths of any length. CoRR, abs/1612.05531, 2016.Google Scholar
- Z. Gotthilf and M. Lewenstein. Improved algorithms for the k simple shortest paths and the replacement paths problems. Information Processing Letters, 109(7):352--355, 2009.Google ScholarDigital Library
- R. Grossi, A. Marino, and L. Versari. Efficient algorithms for listing k disjoint st-paths in graphs. In Latin American Symposium on Theoretical Informatics, pages 544--557. Springer, 2018.Google ScholarCross Ref
- G. Y. Handler and I. Zang. A dual algorithm for the constrained shortest path problem. Networks, 10(4):293--309, 1980.Google ScholarCross Ref
- J. Hershberger, M. Maxel, and S. Suri. Finding the k shortest simple paths: A new algorithm and its implementation. ACM Transactions on Algorithms (TALG), 3(4):45, 2007.Google Scholar
- D. S. Hochbaum. The pseudoflow algorithm: A new algorithm for the maximum-flow problem. Operations Research, 56(4):992--1009, 2008.Google ScholarDigital Library
- J. Hu, R. Cheng, K. C.-C. Chang, A. Sankar, Y. Fang, and B. Y. Lam. Discovering maximal motif cliques in large heterogeneous information networks. In 2019 IEEE 35th International Conference on Data Engineering (ICDE), pages 746--757. IEEE, 2019.Google ScholarCross Ref
- S. Irnich and G. Desaulniers. Shortest path problems with resource constraints. In Column generation, pages 33--65. Springer, 2005.Google ScholarCross Ref
- R. Jin and N. Ruan. Shortest path computation in large networks, Dec. 19 2013. US Patent App. 13/899,124.Google Scholar
- D. B. Johnson. Finding all the elementary circuits of a directed graph. SIAM J. Comput., 4(1):77--84, 1975.Google ScholarDigital Library
- D. S. Johnson, C. H. Papadimitriou, and M. Yannakakis. On generating all maximal independent sets. Inf. Process. Lett., 27(3):119--123, 1988.Google ScholarDigital Library
- C. V. Karsten, D. Pisinger, S. Ropke, and B. D. Brouer. The time constrained multi-commodity network flow problem and its application to liner shipping network design. Transportation Research Part E: Logistics and Transportation Review, 76:122--138, 2015.Google ScholarCross Ref
- N. Katoh, T. Ibaraki, and H. Mine. An efficient algorithm for k shortest simple paths. Networks, 12(4):411--427, 1982.Google ScholarCross Ref
- A. A. Khan and H. Singh. Petri net approach to enumerate all simple paths in a graph. Electronics Letters, 16(8):291--292, 1980.Google ScholarCross Ref
- D. E. Knuth. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms. Addison-Wesley Professional, 2011.Google Scholar
- S. R. Kosaraju and G. F. Sullivan. Detecting cycles in dynamic graphs in polynomial time (preliminary version). In STOC, pages 398--406, 1988.Google ScholarDigital Library
- R. Kumar and T. Calders. 2scent: An efficient algorithm to enumerate all simple temporal cycles. PVLDB, 11(11):1441--1453, 2018.Google Scholar
- J. Kunegis. Konect: the koblenz network collection. In Proceedings of the 22nd International Conference on World Wide Web, pages 1343--1350. ACM, 2013.Google ScholarDigital Library
- K. L, J. Nadeau, G. Ozsoyoglu, Z. Ozsoyoglu, G. Schaeffer, M. Tasan, and W. Xu. Pathways database system: An integrated system for biological pathways. Bioinformatics, 19:930--7, 06 2003.Google ScholarCross Ref
- L. Lai, Z. Qing, Z. Yang, X. Jin, Z. Lai, R. Wang, K. Hao, X. Lin, L. Qin, W. Zhang, et al. Distributed subgraph matching on timely dataflow. Proceedings of the VLDB Endowment, 12(10):1099--1112, 2019.Google ScholarDigital Library
- N. Lao and W. W. Cohen. Relational retrieval using a combination of path-constrained random walks. Machine Learning, 81(1):53--67, 2010.Google ScholarDigital Library
- U. Leser. A query language for biological networks. Bioinformatics, 21:ii33--9, 10 2005.Google Scholar
- J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014.Google Scholar
- B. Liu, L. Yuan, X. Lin, L. Qin, W. Zhang, and J. Zhou. Efficient (a, β)-core computation: an index-based approach. In The World Wide Web Conference, pages 1130--1141. ACM, 2019.Google ScholarDigital Library
- B. Liu, F. Zhang, C. Zhang, W. Zhang, and X. Lin. Corecube: Core decomposition in multilayer graphs. In International Conference on Web Information Systems Engineering, pages 694--710. Springer, 2019.Google ScholarDigital Library
- H. Liu, C. Jin, B. Yang, and A. Zhou. Finding top-k shortest paths with diversity. IEEE Transactions on Knowledge and Data Engineering, 30(3):488--502, 2017.Google ScholarCross Ref
- E. Q. Martins and M. M. Pascoal. A new implementation of yens ranking loopless paths algorithm. Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 1(2):121--133, 2003.Google Scholar
- S. Mazumder and B. Liu. Context-aware path ranking for knowledge base completion. In IJCAI, pages 1195--1201, 2017.Google ScholarCross Ref
- M. Nishino, N. Yasuda, S. Minato, and M. Nagata. Compiling graph substructures into sentential decision diagrams. In AAAI, pages 1213--1221, 2017.Google Scholar
- Y. Peng, Y. Zhang, W. Zhang, X. Lin, and L. Qin. Efficient probabilistic k-core computation on uncertain graphs. In 2018 IEEE 34th International Conference on Data Engineering (ICDE), pages 1192--1203. IEEE, 2018.Google ScholarCross Ref
- X. Qiu, W. Cen, Z. Qian, Y. Peng, Y. Zhang, X. Lin, and J. Zhou. Real-time constrained cycle detection in large dynamic graphs. PVLDB, 11(12):1876--1888, 2018.Google ScholarDigital Library
- J. C. Rivera, H. M. Afsar, and C. Prins. Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem. European Journal of Operational Research, 249(1):93--104, 2016.Google ScholarCross Ref
- R. Rizzi, G. Sacomoto, and M. Sagot. Efficiently listing bounded length st-paths. In IWOCA, pages 318--329, 2014.Google Scholar
- L. Roditty and U. Zwick. Replacement paths and k simple shortest paths in unweighted directed graphs. In International Colloquium on Automata, Languages, and Programming, pages 249--260. Springer, 2005.Google Scholar
- R. A. Rossi and N. K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015.Google ScholarCross Ref
- J.-J. Salazar-González. Approaches to solve the fleet-assignment, aircraft-routing, crew-pairing and crew-rostering problems of a regional carrier. Omega, 43:71--82, 2014.Google ScholarCross Ref
- N. Shi, S. Zhou, F. Wang, Y. Tao, and L. Liu. The multi-criteria constrained shortest path problem. Transportation Research Part E: Logistics and Transportation Review, 101:13--29, 2017.Google ScholarCross Ref
- O. Shmueli. Dynamic cycle detection. Inf. Process. Lett., 17(4):185--188, 1983.Google ScholarCross Ref
- C. Sommer. Shortest-path queries in static networks. ACM Comput. Surv., 46(4):45:1--45:31, 2014.Google ScholarDigital Library
- L. Talarico, K. Sörensen, and J. Springael. The k-dissimilar vehicle routing problem. European Journal of Operational Research, 244(1):129--140, 2015.Google ScholarCross Ref
- Y. Tao, C. Sheng, and J. Pei. On k-skip shortest paths. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, pages 421--432. ACM, 2011.Google ScholarDigital Library
- C. Voss, M. Moll, and L. E. Kavraki. A heuristic approach to finding diverse short paths. In 2015 IEEE International Conference on Robotics and Automation (ICRA), pages 4173--4179. IEEE, 2015.Google ScholarCross Ref
- K. Wang, X. Cao, X. Lin, W. Zhang, and L. Qin. Efficient computing of radius-bounded k-cores. In 2018 IEEE 34th International Conference on Data Engineering (ICDE), pages 233--244. IEEE, 2018.Google ScholarCross Ref
- K. Wang, X. Lin, L. Qin, W. Zhang, and Y. Zhang. Vertex priority based butterfly counting for large-scale bipartite networks. Proceedings of the VLDB Endowment, 12(10):1139--1152, 2019.Google ScholarDigital Library
- L. Wang, L. Yang, and Z. Gao. The constrained shortest path problem with stochastic correlated link travel times. European Journal of Operational Research, 255(1):43--57, 2016.Google ScholarCross Ref
- S. Wang, X. Xiao, Y. Yang, and W. Lin. Effective indexing for approximate constrained shortest path queries on large road networks. Proceedings of the VLDB Endowment, 10(2):61--72, 2016.Google ScholarDigital Library
- N. Yasuda, T. Sugaya, and S. Minato. Fast compilation of s-t paths on a graph for counting and enumeration. In Proceedings of the 3rd Workshop on Advanced Methodologies for Bayesian Networks, AMBN, pages 129--140, 2017.Google Scholar
- J. Y. Yen. Finding the k shortest loopless paths in a network. Management Science, 17(11):712--716, 1971.Google ScholarDigital Library
- J. X. Yu and J. Cheng. Graph reachability queries: A survey. In Managing and Mining Graph Data, pages 181--215. 2010.Google ScholarCross Ref
- D. Yue, X. Wu, Y. Wang, Y. Li, and C. Chu. A review of data mining-based financial fraud detection research. In International Conference on Wireless Communications, Networking and Mobile Computing, pages 5519 -- 5522, 10 2007.Google ScholarCross Ref
- A. D. Zhu, X. Xiao, S. Wang, and W. Lin. Efficient single-source shortest path and distance queries on large graphs. In ACM SIGKDD, pages 998--1006, 2013.Google ScholarDigital Library
Index Terms
- Towards bridging theory and practice: hop-constrained s-t simple path enumeration
Index terms have been assigned to the content through auto-classification.
Recommendations
Chromatic Ramsey Theory
Let G be a countable graph which has infinite chromatic number. If is a coloring of G2with two colors, is there then a subsetH Gsuch that is constant on H2andG|H,the graph induced by G onH,has infinite chromatic number__ __ As edges and non-edges can be ...
On two problems in graph Ramsey theory
We study two classical problems in graph Ramsey theory, that of determining the Ramsey number of bounded-degree graphs and that of estimating the induced Ramsey number for a graph with a given number of vertices.
The Ramsey number r ( H ) of a graph ...
All-Path bridging
Display Omitted Today, link-state routing protocols that compute multiple shortest paths predominate in data center and campus networks, where routing is performed either in layer three or in layer two using link-state routing protocols. But current ...
Comments