I/O efficient structural clustering and maintenance of clusters for large-scale graphs

作者：

Highlights：

• We study clustering and cluster maintenance for graphs larger than main memory.

• Clustering is performed on several memory-sized subgraphs to avoid thrashing.

• Cluster membership of nodes is correctly updated for changes in dynamic graphs.

• Real-world graphs with billions of edges can be processed when lack of memory.

摘要

•We study clustering and cluster maintenance for graphs larger than main memory.•Clustering is performed on several memory-sized subgraphs to avoid thrashing.•Cluster membership of nodes is correctly updated for changes in dynamic graphs.•Real-world graphs with billions of edges can be processed when lack of memory.

论文关键词：Graph,Structural graph clustering,I/O-efficient algorithm,Cluster maintenance,Dynamic graph

论文评审过程：Received 12 April 2019, Revised 29 September 2020, Accepted 1 November 2020, Available online 4 November 2020, Version of Record 24 January 2021.

论文官网地址：https://doi.org/10.1016/j.eswa.2020.114221