SpringerLink
Log in

Efficient algorithms for reachability and path queries on temporal bipartite graphs

  • Regular Paper
  • Published:
The VLDB Journal Aims and scope Submit manuscript

Abstract

Bipartite graphs are naturally used to model relationships between two types of entities, such as people-location, user-post, and investor-stock. When modeling real-world applications like disease outbreaks, edges are often enriched with temporal information, leading to temporal bipartite graphs. While reachability has been extensively studied on (temporal) unipartite graphs, it remains largely unexplored on temporal bipartite graphs. To fill this research gap, we study the reachability problem on temporal bipartite graphs in this paper. Specifically, a vertex u reaches a vertex w in a temporal bipartite graph G if u and w are connected through a series of consecutive wedges with time constraints. To efficiently answer if a vertex can reach the other vertex, we propose an index-based method by adapting the idea of 2-hop labeling. Effective optimization strategies and parallelization techniques are devised to accelerate the index construction process. To better support real-life scenarios, we further show how the index is leveraged to efficiently answer other types of queries, e.g., single-source reachability and earliest-arrival path queries. In addition, we propose an efficient method to handle incremental maintenance of the index structure. Extensive experiments on 16 real-world graphs demonstrate the effectiveness and efficiency of our proposed techniques.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16

Similar content being viewed by others

Notes

  1. There are also some other vertex ordering schemes, e.g., betweenness-based scheme and significant path-based scheme. Please see [32] for more details.

References

  1. Coronavirus Research Center: https://coronavirus.jhu.edu/

  2. KONECT: http://konect.cc/

  3. SNAP: http://snap.stanford.edu/data

  4. https://covid.cdc.gov/covid-data-tracker/#trends_dailytrendscases

  5. Wolfram Mathworld: https://mathworld.wolfram.com/RandomNumber.html

  6. Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.F.: Hierarchical hub labelings for shortest paths. In European Symposium on Algorithms, pages 24–35, (2012)

  7. Ahmed, H., Zhang, Y., Zafar, M.S., Sheikh, N., Tai, Z.: Node embedding over attributed bipartite graphs. In International Conference on Knowledge Science, Engineering and Management, pages 202–210. Springer, (2020)

  8. Akiba, T., Iwata, Y., Yoshida, Y.: Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pages 349–360, (2013)

  9. Barabasi, A.-L.: The origin of bursts and heavy tails in human dynamics. Nature 435(7039), 207–211 (2005)

    Article  Google Scholar 

  10. Beamer, S., Asanovic, K., Patterson, D.: Direction-optimizing breadth-first search. In SC’12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, pages 1–10. IEEE, (2012)

  11. Bramandia, R., Choi, B., Ng, W.K.: Incremental maintenance of 2-hop labeling of large graphs. IEEE Trans. Knowl. Data Eng. 22(5), 682–698 (2010)

    Article  Google Scholar 

  12. Bui-Xuan, B., Ferreira, A., Jarry, A.: Computing shortest, fastest, and foremost journeys in dynamic networks. Int. J. Found. Comput. Sci. 14(2), 267–285 (2003)

    Article  MathSciNet  Google Scholar 

  13. Casteigts, A., Himmel, A., Molter, H., Zschoche, P.: The computational complexity of finding temporal paths under waiting time constraints. CoRR, abs/1909.06437, (2019)

  14. Chen, L., Gupta, A., Kurul, M.E.: Stack-based algorithms for pattern matching on dags. In Proceedings of the VLDB Endowment, pages 493–504, (2005)

  15. Chen, X., Wang, K., Lin, X., Zhang, W., Qin, L., Zhang, Y.: Efficiently answering reachability and path queries on temporal bipartite graphs. Proc. VLDB Endow. 14(10), 1845–1858 (2021)

    Article  Google Scholar 

  16. Chen, Y., Chen, Y.: Decomposing dags into spanning trees: A new way to compress transitive closures. In 2011 IEEE 27th International Conference on Data Engineering, pages 1007–1018, (2011)

  17. Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. SIAM J. Comput. (2002). https://doi.org/10.1137/S0097539702403098

    Article  Google Scholar 

  18. Eubank, S., Guclu, H., Kumar, V.A., Marathe, M.V., Srinivasan, A., Toroczkai, Z., Wang, N.: Modelling disease outbreaks in realistic urban social networks. Nature 429(6988), 180–184 (2004)

    Article  Google Scholar 

  19. Huang, S., Fu, A.W.-C., Liu, R.: Minimum spanning trees in temporal graphs. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, SIGMOD ’15, page 419–430, New York, NY, USA, (2015). Association for Computing Machinery

  20. Jagadish, H.V.: A compression technique to materialize transitive closure. ACM Trans. Database Syst. (TODS) 15(4), 558–598 (1990)

    Article  MathSciNet  Google Scholar 

  21. Jiang, M., Fu, A.W.-C., Wong, R.C.-W., Xu, Y.: Hop doubling label indexing for point-to-point distance querying on scale-free networks. Proceedings of the VLDB Endowment 7(12), 1203–1214 (2014)

    Article  Google Scholar 

  22. Jiang, Z.-Q., Zhou, W.-X.: Complex stock trading network among investors. Phys. A 389(21), 4929–4941 (2010)

    Article  Google Scholar 

  23. **, R., **ang, Y., Ruan, N., Fuhry, D.: 3-hop: a high-compression indexing scheme for reachability query. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pages 813–826, (2009)

  24. Kasukawa, T., Sugimoto, M., Hida, A., Minami, Y., Mori, M., Honma, S., Honma, K.-I., Mishima, K., Soga, T., Ueda, H.R.: Human blood metabolite timetable indicates internal body time. Proc. Natl. Acad. Sci. 109(37), 15036–15041 (2012)

    Article  Google Scholar 

  25. Kempe, D., Kleinberg, J. M., Kumar, A.: Connectivity and inference problems for temporal networks. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pages 504–513, (2000)

  26. Kleinberg, J.: Bursty and hierarchical structure in streams. Data Min. Knowl. Disc. 7(4), 373–397 (2003)

    Article  MathSciNet  Google Scholar 

  27. Kleinberg, J.: Cascading behavior in networks: algorithmic and economic issues. Algorithmic game theory 24, 613–632 (2007)

    Article  MathSciNet  Google Scholar 

  28. Ley, M.: The dblp computer science bibliography: Evolution, research issues, perspectives. In International symposium on string processing and information retrieval, pages 1–10. Springer, (2002)

  29. Li, W., Qiao, M., Qin, L., Zhang, Y., Chang, L., Lin, X.: Scaling distance labeling on small-world networks. In Proceedings of the 2019 International Conference on Management of Data, pages 1060–1077, (2019)

  30. Li, Y., Fang, J., Zeng, Y., Maag, B., Tong, Y., Zhang, L.: Two-sided online bipartite matching in spatial data: experiments and analysis. GeoInformatica 24(1), 175–198 (2020)

    Article  Google Scholar 

  31. Li, Y., Lou, Z., Shi, Y., Han, J.: Temporal motifs in heterogeneous information networks. In MLG Workshop@ KDD, (2018)

  32. Li, Y., U, L.H., Yiu, M.L., Kou, N.M.: An experimental study on hub labeling based shortest path algorithms. Proc.VLDB Endow. 11(4), 445–457 (2017)

    Article  Google Scholar 

  33. Malik, H.A.M., Mahesar, A.W., Abid, F., Waqas, A., Wahiddin, M.R.: Two-mode network modeling and analysis of dengue epidemic behavior in gombak, malaysia. Appl. Math. Model. 43, 207–220 (2017)

    Article  MathSciNet  Google Scholar 

  34. O’Connor, C.M., Adams, J.U., Fairman, J.: Essentials of cell biology. Cambridge, MA: NPG Education 1, 54 (2010)

    Google Scholar 

  35. Pavlopoulos, G.A., Kontou, P.I., Pavlopoulou, A., Bouyioukos, C., Markou, E., Bagos, P.G.: Bipartite graphs in systems biology and medicine: a survey of methods and applications. GigaScience 7(4), giy014 (2018)

    Article  Google Scholar 

  36. Pikies, T., Kubale, M.: Chromatic cost coloring of weighted bipartite graphs. Appl. Math. Comput. 375, 125073 (2020)

    MathSciNet  Google Scholar 

  37. Sariyüce, A. E., Pinar, A.: Peeling bipartite networks for dense subgraph discovery. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pages 504–512, (2018)

  38. Semertzidis, K., Pitoura, E., Lillis, K.: Timereach: Historical reachability queries on evolving graphs. In Proceedings of the 18th International Conference on Extending Database Technology, EDBT, pages 121–132, (2015)

  39. Seufert, S., Anand, A., Bedathur, S. J, Weikum, G.: FERRARI: flexible and efficient reachability range assignment for graph indexing. In 2013 IEEE 29th International Conference on Data Engineering (ICDE), pages 1009–1020, (2013)

  40. Simon, K.: An improved algorithm for transitive closure on acyclic digraphs. Theoret. Comput. Sci. 58, 325–346 (1988)

    Article  MathSciNet  Google Scholar 

  41. Smart, A.G., Amaral, L.A., Ottino, J.M.: Cascading failure and robustness in metabolic networks. Proc. Natl. Acad. Sci. 105(36), 13223–13228 (2008)

    Article  Google Scholar 

  42. Sun, X.Q., Shen, H.W., Cheng, X.Q.: Trading network predicts stock price. Sci. Rep. 4(1), 3711–3711 (2014)

    Article  Google Scholar 

  43. Tong, Y., Zeng, Y., Ding, B., Wang, L., Chen, L.: Two-sided online micro-task assignment in spatial crowdsourcing. IEEE Trans. Knowl. Data Eng. 33(5), 2295–2309 (2019)

    Google Scholar 

  44. Trißl, S., Leser, U.: Fast and practical indexing and querying of very large graphs. In Proceedings of the 2007 ACM SIGMOD international conference on Management of data, pages 845–856, (2007)

  45. Valstar, L. D., Fletcher, G. H., Yoshida, Y.: Landmark indexing for evaluation of label-constrained reachability queries. In Proceedings of the 2017 ACM International Conference on Management of Data, pages 345–358, (2017)

  46. van Schaik, S. J., de Moor, O.: A memory efficient reachability data structure through bit vector compression. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, pages 913–924, (2011)

  47. Wang, H., He, H., Yang, J., Yu, P.S., Yu, J.X.: Dual labeling: Answering graph reachability queries in constant time. In 2006 IEEE 22nd International Conference on Data Engineering (ICDE), page 75, (2006)

  48. Wang, J., de Vries, A.P., Reinders, M.J.T.: Unifying user-based and item-based collaborative filtering approaches by similarity fusion. In Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, pages 501–508, (2006)

  49. Wang, S. Lin, W. Yang, Y., **ao, X., Zhou, S.: Efficient route planning on public transportation networks: A labelling approach. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pages 967–982, (2015)

  50. Wei, H., Yu, J.X., Lu, C., **, R.: Reachability querying: an independent permutation labeling approach. Proceedings of the VLDB Endowment 7(12), 1191–1202 (2014)

  51. Wei, H., Yu, J.X., Lu, C., **, R.: Reachability querying: an independent permutation labeling approach. VLDB J. 27(1), 1–26 (2018)

    Article  Google Scholar 

  52. Wen, D., Huang, Y., Zhang, Y., Qin, L., Zhang, W., Lin, X.: Efficiently answering span-reachability queries in large temporal graphs. In 2020 IEEE 36th International Conference on Data Engineering (ICDE), pages 1153–1164, (2020)

  53. Wen, D., Yang, B., Zhang, Y., Qin, L., Cheng, D., Zhang, W.: Span-reachability querying in large temporal graphs. VLDB J. 31(4), 629–647 (2022)

    Article  Google Scholar 

  54. Wu, H., Cheng, J., Lu, Y., Ke, Y., Huang, Y., Yan, D., Wu, H.: Core decomposition in large temporal graphs. In 2015 IEEE International Conference on Big Data (Big Data), pages 649–658, (2015)

  55. Wu, H., Huang, Y., Cheng, J., Li, J., Ke, Y.: Reachability and time-based path queries in temporal graphs. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE), pages 145–156, (2016)

  56. Wu, H., Zhao, Y., Cheng, J., Yan, D.: Efficient processing of growing temporal graphs. In: Candan, S., Chen, L., Pedersen, T.B., Chang, L., Hua, W. (eds.) Database Syst. Adv. Appl., pp. 387–403. Springer, Cham (2017)

    Chapter  Google Scholar 

  57. Wu, T., Yu, S., Liao, W., Chang, C.: Temporal bipartite projection and link prediction for online social networks. In 2014 IEEE International Conference on Big Data (Big Data), pages 52–59, (2014)

  58. **e, N., Zhou, W., Shen, C., Li, T., Chen, S., Wei, J.: City disaster susceptibility comparisons using weighted bipartite graphs. International Journal of Next-Generation Computing, 9(1), (2018)

  59. Yan, H., Jiang, Y., Liu, G.: Telecomm fraud detection via attributed bipartite network. In 2018 15th International Conference on Service Systems and Service Management (ICSSSM), pages 1–6. IEEE, (2018)

  60. Yildirim, H., Chaoji, V., Zaki, M.J.: GRAIL: scalable reachability index for large graphs. Proc. VLDB Endow. 3(1), 276–284 (2010)

    Article  Google Scholar 

  61. Yildirim, H., Chaoji, V., Zaki, M.J.: DAGGER: A scalable index for reachability queries in large dynamic graphs. CoRR, abs/1301.0977, (2013)

  62. Yu, J.X., Cheng, J.: Graph reachability queries: A survey. In Managing and Mining Graph Data, pages 181–215. (2010)

  63. Zhang, T., Gao, Y., Chen, L., Guo, W., Pu, S., Zheng, B., Jensen, C.S.: Efficient distributed reachability querying of massive temporal graphs. VLDB J. 28(6), 871–896 (2019)

    Article  Google Scholar 

  64. Zignani, M.: Human mobility model based on time-varying bipartite graph. In 2011 IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks, pages 1–4, (2011)

Download references

Acknowledgements

Kai Wang is supported by NSFC 62302294, Wenjie Zhang is supported by ARC DP230101445 and ARC FT210100303.

Author information

Authors and Affiliations

  1. Antai College of Economics and Management, Shanghai Jiao Tong University, Shanghai, China

    Kai Wang & Xuemin Lin

  2. University of New South Wales, Sydney, NSW, Australia

    Minghao Cai & Wenjie Zhang

  3. Data Principles (Bei**g) Technology Co., Ltd., Bei**g, China

    **aoshuang Chen

  4. University of Technology Sydney, Sydney, NSW, Australia

    Lu Qin

  5. Zhejiang Gongshang University, Hangzhou, Zhejiang, China

    Ying Zhang

Authors
  1. Kai Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Minghao Cai
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. **aoshuang Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Xuemin Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Wenjie Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Lu Qin
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Ying Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to **aoshuang Chen.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Wang, K., Cai, M., Chen, X. et al. Efficient algorithms for reachability and path queries on temporal bipartite graphs. The VLDB Journal (2024). https://doi.org/10.1007/s00778-024-00854-z

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00778-024-00854-z

Keywords

Search

Navigation