# Concentration inequalities for correlated network-valued processes with applications to community estimation and changepoint analysis

arXiv: https://arxiv.org/abs/2208.01365 · HTML: https://mlsanity.com/paper/2208.01365/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 43 references that are in the map.
- First posted on arXiv 2 Aug 2022.

## Builds on (most cited first, 18 of 18)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Statistical clustering of temporal networks through a dynamic stochastic block model](https://mlsanity.com/paper/1506.07464/) (2015)
- [Latent Space Models for Dynamic Networks](https://mlsanity.com/paper/2005.08808/) (2020)
- [Dynamic stochastic blockmodels for time-evolving social networks](https://mlsanity.com/paper/1403.0921/) (2014)
- [Nonparametric Bayes dynamic modeling of relational data](https://mlsanity.com/paper/1311.4669/) (2013)
- [Detectability thresholds and optimal algorithms for community structure in dynamic networks](https://mlsanity.com/paper/1506.06179/) (2015)
- [Measuring large-scale social networks with high resolution](https://mlsanity.com/paper/1401.7233/) (2014)
- [Stochastic Block Transition Models for Dynamic Networks](https://mlsanity.com/paper/1411.5404/) (2014)
- [General Community Detection with Optimal Recovery Conditions for Multi-relational Sparse Networks with Dependent Layers](https://mlsanity.com/paper/2004.03480/) (2020)
- [Random graph models for dynamic networks](https://mlsanity.com/paper/1607.07570/) (2016)
- [Euclidean mirrors and dynamics in network time series](https://mlsanity.com/paper/2205.06877/) (2022)
- [Change point localization in dependent dynamic nonparametric random dot product graphs](https://mlsanity.com/paper/1911.07494/) (2019)
- [The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networks](https://mlsanity.com/paper/2008.00163/) (2020)
- [Exact ICL maximization in a non-stationary temporal extension of the stochastic block model for dynamic networks](https://mlsanity.com/paper/1605.02540/) (2016)
- [Assembling thefacebook: Using heterogeneity to understand online social network assembly](https://mlsanity.com/paper/1503.06772/) (2015)
- [Extraction of Temporal Networks from Term Co-occurrences in Online Textual Sources](https://mlsanity.com/paper/1406.5323/) (2014)
- [Consistent detection and optimal localization of all detectable change points in piecewise stationary arbitrarily sparse network-sequences](https://mlsanity.com/paper/2009.02112/) (2020)

## Built on by (most cited first, 1 of 1)

- [Detection of Model-based Planted Pseudo-cliques in Random Dot Product Graphs by the Adjacency Spectral Embedding and the Graph Encoder Embedding](https://mlsanity.com/paper/2312.11054/) (2023)

## Abstract (arXiv)

Network-valued time series are currently a common form of network data. However, the study of the aggregate behavior of network sequences generated from network-valued stochastic processes is relatively rare. Most of the existing research focuses on the simple setup where the networks are independent (or conditionally independent) across time, and all edges are updated synchronously at each time step. In this paper, we study the concentration properties of the aggregated adjacency matrix and the corresponding Laplacian matrix associated with network sequences generated from lazy network-valued stochastic processes, where edges update asynchronously, and each edge follows a lazy stochastic process for its updates independent of the other edges. We demonstrate the usefulness of these concentration results in proving consistency of standard estimators in community estimation and changepoint estimation problems. We also conduct a simulation study to demonstrate the effect of the laziness parameter, which controls the extent of temporal correlation, on the accuracy of community and changepoint estimation.