Belief Propagation and Community Detection

Belief propagation is a message passing algorithm applied over a network. The algorithm iteratively passes messages along the edges in order to calculate the marginal distribution of unobserved nodes. Filippo et al. used this idea in order to detect communities in networks by passing edge status as messages. We introduce an computationally less expensive approximation and test it on various graphs including GN, LFR, and real graphs.