  The community detection problem requires to cluster the nodes of a network
into a small number of well-connected "communities". There has been substantial
recent progress in characterizing the fundamental statistical limits of
community detection under simple stochastic block models. However, in
real-world applications, the network structure is typically dynamic, with nodes
that join over time. In this setting, we would like a detection algorithm to
perform only a limited number of updates at each node arrival. While standard
voting approaches satisfy this constraint, it is unclear whether they exploit
the network information optimally. We introduce a simple model for networks
growing over time which we refer to as streaming stochastic block model
(StSBM). Within this model, we prove that voting algorithms have fundamental
limitations. We also develop a streaming belief-propagation (StreamBP)
approach, for which we prove optimality in certain regimes. We validate our
theoretical findings on synthetic and real data.
