@misc{GuoSekerinski22OrderBasedCoreMaintenancePreprint,
	title = {Simplified {Algorithms} for {Order}-{Based} {Core} {Maintenance}},
	doi = {10.48550/arXiv.2201.07103},
	abstract = {Graph analytics attract much attention from both research and
industry communities. Due to the linear time complexity, the 𝑘-
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 𝑘-core,
which is time-consuming, we study how to maintain the 𝑘-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 𝑘-order, among all vertices, which can significantly reduce
the searching space. However, this order-based method is compli-
cated for understanding and implementation, 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 𝑘-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 imple-
ment; 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.7x and 9.7x for
edge insertion and removal, respectively.},
	publisher = {arXiv},
	author = {Guo, Bin and Sekerinski, Emil},
	month = jan,
	year = {2022},
	note = {Pages: 1-13},
}

{"_id":"mFriSME2quYM7z5qY","bibbaseid":"guo-sekerinski-simplifiedalgorithmsfororderbasedcoremaintenance-2022","author_short":["Guo, B.","Sekerinski, E."],"bibdata":{"bibtype":"misc","type":"misc","title":"Simplified Algorithms for Order-Based Core Maintenance","doi":"10.48550/arXiv.2201.07103","abstract":"Graph analytics attract much attention from both research and industry communities. Due to the linear time complexity, the 𝑘- 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 𝑘-core, which is time-consuming, we study how to maintain the 𝑘-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 𝑘-order, among all vertices, which can significantly reduce the searching space. However, this order-based method is compli- cated for understanding and implementation, 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 𝑘-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 imple- ment; 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.7x and 9.7x for edge insertion and removal, respectively.","publisher":"arXiv","author":[{"propositions":[],"lastnames":["Guo"],"firstnames":["Bin"],"suffixes":[]},{"propositions":[],"lastnames":["Sekerinski"],"firstnames":["Emil"],"suffixes":[]}],"month":"January","year":"2022","note":"Pages: 1-13","bibtex":"@misc{GuoSekerinski22OrderBasedCoreMaintenancePreprint,\n\ttitle = {Simplified {Algorithms} for {Order}-{Based} {Core} {Maintenance}},\n\tdoi = {10.48550/arXiv.2201.07103},\n\tabstract = {Graph analytics attract much attention from both research and\nindustry communities. Due to the linear time complexity, the 𝑘-\ncore decomposition is widely used in many real-world applications\nsuch as biology, social networks, community detection, ecology,\nand information spreading. In many such applications, the data\ngraphs continuously change over time. The changes correspond\nto edge insertion and removal. Instead of recomputing the 𝑘-core,\nwhich is time-consuming, we study how to maintain the 𝑘-core\nefficiently. That is, when inserting or deleting an edge, we need to\nidentify the affected vertices by searching for more vertices. The\nstate-of-the-art order-based method maintains an order, the so-\ncalled 𝑘-order, among all vertices, which can significantly reduce\nthe searching space. However, this order-based method is compli-\ncated for understanding and implementation, and its correctness is\nnot formally discussed. In this work, we propose a simplified order-\nbased approach by introducing the classical Order Data Structure to\nmaintain the 𝑘-order, which significantly improves the worst-case\ntime complexity for both edge insertion and removal algorithms.\nAlso, our simplified method is intuitive to understand and imple-\nment; it is easy to argue the correctness formally. Additionally,\nwe discuss a simplified batch insertion approach. The experiments\nevaluate our simplified method over 12 real and synthetic graphs\nwith billions of vertices. Compared with the existing method, our\nsimplified approach achieves high speedups up to 7.7x and 9.7x for\nedge insertion and removal, respectively.},\n\tpublisher = {arXiv},\n\tauthor = {Guo, Bin and Sekerinski, Emil},\n\tmonth = jan,\n\tyear = {2022},\n\tnote = {Pages: 1-13},\n}\n\n","author_short":["Guo, B.","Sekerinski, E."],"key":"GuoSekerinski22OrderBasedCoreMaintenancePreprint","id":"GuoSekerinski22OrderBasedCoreMaintenancePreprint","bibbaseid":"guo-sekerinski-simplifiedalgorithmsfororderbasedcoremaintenance-2022","role":"author","urls":{},"metadata":{"authorlinks":{}},"downloads":2},"bibtype":"misc","biburl":"https://api.krunk.cn/emil/bib.php","dataSources":["HEdahWqKBpmSGmDwq","N2pLmFa7tezaioGCg","MF5eGzpJnqf6bSAoG","Qrg38B3HrfoKD7g5k","ienufKdnmJs49AsjR","So4gmSWFmbQRNEuFs","ezsmw4w22u9JFLNYJ","CvQYP6Tmpapx74Mgr","RWydLHbBJqgdeh5jr"],"keywords":[],"search_terms":["simplified","algorithms","order","based","core","maintenance","guo","sekerinski"],"title":"Simplified Algorithms for Order-Based Core Maintenance","year":2022,"downloads":2}