Tutorial Slides (KDD 2018 version)
- Part I: Streaming, Sampling, and Sketching Andrew McGregor
- Part II: Space-Efficient Optimization Sudipto Guha
Other General Resources
- A survey about graph stream algorithms.
- Extended Tutorial Slides (3hrs) from Porto Winter School on Network Science 2018.
- Ten lectures on graph streams:
- Graphs-1: Connectivity, k-connectivity, Spanners, Sparsification
- Graphs-2: Connectivity via Sketching
- Graphs-3: Sparsification via Sketching
- Graphs-4: Insert-Only (Weighted) Matchings
- Graphs-5: Planar Matchings
- Graphs-6: Small Matchings
- Graphs-7: Multiple-Pass Matchings via Multiplicative Weights
- Graphs-8: Submodular Maximization
- Graphs-9: Set-Cover and Max Coverage
- Graphs-10: Correlation Clustering
Bibliography
The following is not an exhaustive list of papers that are relevant to the topic but should include the most relevant and recent papers.
- Vertex and Edge Connectivity and Graph Sparsification
- Single Pass Spectral Sparsification in Dynamic Streams FOCS 2014 (M. Kapralov, Y. T. Lee, C. Musco, C. Musco, A. Sidford)
- Vertex and Hyperedge Connectivity in Dynamic Graph Streams PODS 2015 (S. Guha, A. McGregor, D. Tench)
- Graph Sketches: Sparsfiers, Spanners, and Subgraphs PODS 2012 (K. Ahn, S. Guha, A. McGregor)
- Analyzing Graph Structure via Linear Measurements SODA 2012 (K. Ahn, S. Guha, A. McGregor)
- Spectral Sparsification of Dynamic Graph Streams APPROX 2013 (K. Ahn, S. Guha, A. McGregor)
- Matchings and Vertex Cover
- Kernelization via Sampling with Applications to Dynamic Graph Streams SODA 2016 (R. Chitnis, G. Cormode, H. Esfandiari, M. Hajiaghayi, A. McGregor, M. Monemizadeh, S. Vorotnikova)
- Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem SODA 2016. S. Assadi, S. Khanna, Y. Li.
- Triangle Counting, Frequent Subgraphs, Clustering Coefficients
- Better Algorithms for Counting Triangles in Data Streams PODS 2016 (A. McGregor, S. Vorotnikova, H. Vu)
- Colorful Triangle Counting and a MapReduce Implementation. Rasmus Pagh, Charalampos E. Tsourakakis
- Set Cover
- Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem FOCS 2016. S. Assadi, S. Khanna, Y. Li.
- Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover SODA 2016. A. Chakrabarti, A. Wirth.
- Towards Tight Bounds for the Streaming Set Cover Problem PODS 2016. S. Har-Peled, P. Indyk, S. Mahabadi, A. Vakilian.
- Graph Coloring
- Sublinear Algorithms for (Delta+1) Vertex Coloring ArXiv 2018 (S. Assadi, Y. Chen, S. Khanna)
- SColoring in Graph Streams ArXiv 2018 (S. K. Bera, P. Ghosh)
- Densest Subgraph
- Densest Subgraph in Dynamic Graph Streams MFCS 2015 (A. McGregor, D. Tench, S. Vorotnikova, H. Vu)
- See also: Dense subgraph discovery Tutorial KDD 2015. A. Gionis, C. Tsourakakis,
- Correlation Clustering
- Correlation Clustering in Data Streams ICML 2015 (K. Ahn, G. Cormode, S. Guha, A. McGregor, A. Wirth)
- See also: Correlation Clustering: from Theory to Practice KDD 2014. F. Bonchi, D. Garcia-Soriano, E. Liberty
- Bayesian Networks
- Evaluating Bayesian Networks via Data Streams COCOON 2015. A. McGregor, H. T. Vu.
- Graphical Model Sketch. B. Kveton, H. Bui, M. Ghavamzadeh, G. Theocharous, S. Muthukrishnan, S. Sun
- Other
- Dynamic Graphs in the Sliding-Window Model ESA 2013 (M. Crouch, A. McGregor, D. Stubbs)