Timezone: »

 
Poster
Streaming Belief Propagation for Community Detection
Yuchen Wu · Jakab Tardos · Mohammadhossein Bateni · André Linhares · Filipe Miguel Goncalves de Almeida · Andrea Montanari · Ashkan Norouzi-Fard

Tue Dec 07 08:30 AM -- 10:00 AM (PST) @
in Poster Session 1 »

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

Keywords:

Author Information

Yuchen Wu (Stanford University)
Jakab Tardos (EPFL)
Mohammadhossein Bateni (Google research)
André Linhares (University of Waterloo)
Filipe Miguel Goncalves de Almeida (Google)
Andrea Montanari (Stanford)
Ashkan Norouzi-Fard (Google Research)

More from the Same Authors