Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Simplified algorithms for order-based core maintenance

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

Graph analytics attract much attention from both research and industry communities. Due to its linear time complexity, the k-core decomposition is widely used in many real-world applications such as biology, social networks, community detection, ecology, and information spreading. In many such applications, the data graphs continuously change over time. The changes correspond to edge insertion and removal. Instead of recomputing the k-core, which is time-consuming, we study how to maintain the k-core efficiently. That is, when inserting or deleting an edge, we need to identify the affected vertices by searching for more vertices. The state-of-the-art order-based method maintains an order, the so-called k-order, among all vertices, which can significantly reduce the searching space. However, this order-based method is complicated to understand and implement, and its correctness is not formally discussed. In this work, we propose a simplified order-based approach by introducing the classical Order Data Structure to maintain the k-order, which significantly improves the worst-case time complexity for both edge insertion and removal algorithms. Also, our simplified method is intuitive to understand and implement; it is easy to argue the correctness formally. Additionally, we discuss a simplified batch insertion approach. The experiments evaluate our simplified method over 12 real and synthetic graphs with billions of vertices. Compared with the existing method, our simplified approach achieves high speedups up to 7.7× and 9.7× for edge insertion and removal, respectively.

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Fig. 1
Algorithm 2
Algorithm 3
Algorithm 4
Fig. 2
Algorithm 5
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Data availability

All real graphs are downloaded from KONECT (http://konect.cc/networks/) and SNAP (http://snap.stanford.edu/data/index.html). All synthetic graphs are generated by using the graph generator of SANP (http://snap.stanford.edu/snappy/doc/reference/generators.html). The source code for this paper is available on GitHub (https://github.com/Itisben/SimplifiedCoreMaint.git).

Notes

  1. https://github.com/Itisben/SimplifiedCoreMaint.git.

  2. http://snap.stanford.edu/data/index.html.

  3. http://konect.cc/networks/.

  4. http://snap.stanford.edu/snappy/doc/reference/generators.html.

References

  1. Batagelj V, Zaversnik M (2003). An o(m) algorithm for cores decomposition of networks. CoRR cs.DS/0310049

  2. Kong YX, Shi GY, Wu RJ, Zhang YC (2019) k-core: theories and applications. Tech Rep. https://doi.org/10.1016/j.physrep.2019.10.004 (http://doc.rero.ch)

    Article  Google Scholar 

  3. Burleson-Lesser K, Morone F, Tomassone MS, Makse HA (2020) K-core robustness in ecological and financial networks. Sci Rep 10(1):1–14

    Article  Google Scholar 

  4. Malliaros FD, Giatsidis C, Papadopoulos AN, Michalis V (2020) The core decomposition of networks: theory, algorithms and applications. VLDB J 29, 61–92. https://doi.org/10.1007/s00778-019-00587-4

  5. Cheng J, Ke Y, Chu S, Özsu M.T (2011). Efficient core decomposition in massive networks. In: 2011 IEEE 27th international conference on data engineering, 51–62 . IEEE

  6. Khaouid W, Barsky M, Srinivasan V, Thomo A (2015) K-core decomposition of large networks on a single pc. Proceed VLDB Endowment 9(1):13–23

    Article  Google Scholar 

  7. Montresor A, De Pellegrini F, Miorandi D (2012) Distributed k-core decomposition. IEEE Trans Parallel Distrib Syst 24(2):288–300

    Article  Google Scholar 

  8. Wen D, Qin L, Zhang Y, Lin X, Yu J.X (2016). I/o efficient core graph decomposition at web scale. In: 2016 IEEE 32nd international conference on data engineering (ICDE), 133–144 . IEEE

  9. Miorandi D, De Pellegrini F (2010) K-shell decomposition for dynamic complex networks. In: 8th international symposium on modeling and optimization in mobile, Ad Hoc, and wireless networks, 488–496 . IEEE

  10. Pei S, Muchnik L, Andrade JS Jr, Zheng Z, Makse HA (2014) Searching for Superspreaders of information in real-world social media. Sci Rep 4:5547

    Article  Google Scholar 

  11. Sarıyüce AE, Gedik B, Jacques-Silva G, Wu K-L, Çatalyürek ÜV (2016) Incremental k-core decomposition: algorithms and evaluation. VLDB J 25(3):425–447

    Article  Google Scholar 

  12. Zhang Y, Yu J.X, Zhang Y, Qin L (2017). A fast order-based approach for core maintenance. In: Proceedings—international conference on data engineering, 337–348 . https://doi.org/10.1109/ICDE.2017.93

  13. Wu H, Cheng J, Lu Y, Ke Y, Huang Y, Yan D, Wu H (2015). Core decomposition in large temporal graphs. In: 2015 IEEE international conference on big data (Big data), 649–658 . IEEE

  14. Saríyüce AE, Gedik B, Jacques-Silva G, Wu K-L, Çatalyürek ÜV (2013) Streaming algorithms for k-core decomposition. Proceed VLDB Endowment 6(6):433–444

    Article  Google Scholar 

  15. Dietz P, Sleator D (1987) Two algorithms for maintaining order in a list. In: Proceedings of the nineteenth annual ACM symposium on theory of computing, 365–372

  16. Bender M.A, Cole R, Demaine E.D, Farach-Colton M, Zito J (2002) Two simplified algorithms for maintaining order in a list. In: European symposium on algorithms, 152–164 . Springer

  17. Seidman SB (1983) Network structure and minimum degree. Soc Netw 5(3):269–287

    Article  MathSciNet  Google Scholar 

  18. Dasari N.S, Desh R, Zubair M (2014). Park: An efficient algorithm for k-core decomposition on multicore processors. In: 2014 IEEE international conference on big data (Big Data), 9–16. IEEE

  19. Kabir H, Madduri K (2017) Parallel k-core decomposition on multicore platforms. In: 2017 IEEE international parallel and distributed processing symposium workshops (IPDPSW), 1482–1491. IEEE

  20. Chan THH, Sozio M, Sun B (2021) Distributed approximate k-core decomposition and min-max edge orientation: Breaking the diameter barrier. J Parallel Distrib Comput 147:87–99

    Article  Google Scholar 

  21. Zhang Y, Yu JX (2019) Unboundedness and efficiency of truss maintenance in evolving graphs. In: Proceedings of the ACM SIGMOD international conference on management of data, 1024–1041. Association for computing machinery. https://doi.org/10.1145/3299869.3300082

  22. Li RH, Yu JX, Mao R (2013) Efficient core maintenance in large dynamic graphs. IEEE Trans Know Data Eng 26(10):2453–2465

    Article  Google Scholar 

  23. Wang N, Yu D, Jin H, Qian C, Xie X, Hua QS (2017) Parallel algorithm for core maintenance in dynamic graphs. In: 2017 IEEE 37th international conference on distributed computing systems (ICDCS), 2366–2371. IEEE

  24. Jin H, Wang N, Yu D, Hua Q.S, Shi X, Xie X (2018). Core maintenance in dynamic graphs: a parallel approach based on matching. IEEE Trans Parallel Distrib Syst 29(11), 2416–2428 https://doi.org/10.1109/TPDS.2018.2835441arXiv:1703.03900

  25. Yu M, Wen D, Qin L, Zhang Y, Zhang W, Lin X (2021) On querying historical k-cores. Proceed VLDB Endowment 14(11):2033–2045

    Article  Google Scholar 

  26. Sun B, Chan THH, Sozio M (2020) Fully dynamic approximate k-core decomposition in hypergraphs. ACM Trans Know Discov Data (TKDD) 14(4):1–21

    Article  Google Scholar 

  27. Liu Q.C, Shi J, Yu S, Dhulipala L, Shun J (2021). Parallel batch-dynamic algorithms for \(k\)-core decomposition and related graph problems. arXiv preprint arXiv:2106.03824

  28. Lin Z, Zhang F, Lin X, Zhang W, Tian Z (2021) Hierarchical core maintenance on large dynamic graphs. Proceed VLDB Endowment 14(5):757–770

    Article  Google Scholar 

  29. Liu B, Liu Z, Zhang F (2021). An order approach for the core maintenance problem on edge-weighted graphs. In: Algorithmic aspects in information and management: 15th international conference, AAIM 2021, virtual event, 2021, Proceedings, 426–437. Springer

  30. Yang H, Wang K, Sun R, Wang X (2020) Fast algorithms for spatial k-core discovery and maintenance. In: 2020 IEEE 22nd international conference on high performance computing and communications; IEEE 18th international conference on smart city; IEEE 6th international conference on data science and systems (HPCC/SmartCity/DSS), 841–846. IEEE

  31. Watts DJ, Strogatz SH (1998) Collective dynamics of small-world networks. Nature 393(6684):440–442

    Article  Google Scholar 

  32. Guo B, Sekerinski E (2022) Parallel order-based core maintenance in dynamic graphs. arXiv preprint arXiv:2210.14290

Download references

Funding

NSERC (Natural Sciences and Engineering Research Council of Canada) discovery.

Author information

Authors and Affiliations

  1. Department of Computing & Information Systems, Trent University, 1600 West Bank Drive, Peterborough, ON, K9L0G2, Canada

    Bin Guo

  2. Department of Computing and Software, McMaster University, Main St. W., Hamilton, ON, L8S4L8, Canada

    Emil Sekerinski

Authors
  1. Bin Guo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Emil Sekerinski
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

Bin Guo writes the paper and does the experiments. As the supervisor, Emil Sekerinski reviews the paper.

Corresponding author

Correspondence to Bin Guo.

Ethics declarations

Conflict of interest

Not applicable.

Ethical approval

Not applicable.

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

Guo, B., Sekerinski, E. Simplified algorithms for order-based core maintenance. J Supercomput 80, 19592–19623 (2024). https://doi.org/10.1007/s11227-024-06190-x

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-024-06190-x

Keywords

Search

Navigation