Sublinear update time randomized algorithms for dynamic graph regression

作者：

Highlights：

• We present two sublinear update time randomized algorithms for the regression of general dynamic graphs.

• Our first algorithm is based on subsampled randomized Hadamard transform and supports edge insertion/deletion.

• Our second algorithm is based on CountSketch and supports all the update operations.

摘要

•We present two sublinear update time randomized algorithms for the regression of general dynamic graphs.•Our first algorithm is based on subsampled randomized Hadamard transform and supports edge insertion/deletion.•Our second algorithm is based on CountSketch and supports all the update operations.

论文关键词：Dynamic networks,Dynamic graph regression,Least squares regression,Sublinear update time,Subsampled randomized Hadamard transform,CountSketch

论文评审过程：Received 8 July 2020, Revised 29 May 2021, Accepted 3 June 2021, Available online 23 June 2021, Version of Record 23 June 2021.

论文官网地址：https://doi.org/10.1016/j.amc.2021.126434