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

Two-stage stochastic optimization is a widely used framework for modeling uncertainty, where we have a probability distribution over possible realizations of the data, called scenarios, and decisions are taken in two stages: we make first-stage decisions knowing only the underlying distribution and before a scenario is realized, and may take additional second-stage recourse actions after a scenario is realized. The goal is typically to minimize the total expected cost. A common criticism levied at this model is that the underlying probability distribution is itself often imprecise! To address this, an approach that is quite versatile and has gained popularity in the stochastic-optimization literature is the distributionally robust 2-stage model: given a collection D of probability distributions, our goal now is to minimize the maximum expected total cost with respect to a distribution in D.

We consider the MST-interdiction problem: given a multigraph G = (V, E), edge weights {w_e >= 0}_{e in E}, interdiction costs {c_e >= 0}_{e in E}, and an interdiction budget B >= 0, the goal is to remove a subset R of edges of total interdiction cost at most B so as to maximize the w-weight of an MST of G-R:=(V,E-R). Our main result is a 4-approximation algorithm for this problem. This improves upon the previous-best 14-approximation [Zenklusen, FOCS 2015]. Notably, our analysis is also significantly simpler and cleaner than the one in [Zenklusen, FOCS 2015]. Whereas Zenklusen uses a greedy algorithm with an involved analysis to extract a good interdiction set from an over-budget set, we utilize a generalization of knapsack called the tree knapsack problem that nicely captures the key combinatorial aspects of this "extraction problem." We prove a simple, yet strong, LP-relative approximation bound for tree knapsack, which leads to our improved guarantees for MST interdiction. Our algorithm and analysis are nearly tight, as we show that one cannot achieve an approximation ratio better than 3 relative to the upper bound used in our analysis (and the one in [Zenklusen, FOCS 2015]). Our guarantee for MST-interdiction yields an 8-approximation for metric-TSP interdiction (improving over the 28-approximation in [Zenklusen, FOCS 2015]). We also show that maximum-spanning-tree interdiction is at least as hard to approximate as the minimization version of densest-k-subgraph.