Error-Correcting Decoders for Communities in Networks

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. We showed the approximation worked comparably to many popular methods and even outperformed with some graphs with metadata.

Accepted at Applied Network Science.

Krishna Bathina
Decision Science Associate Consultant

Data scientists interested in complexity and systems science