Error-Correcting Decoders for Communities in Networks

Though an unclear problem, community detection is a popular research topic. One example is the use of statistical inference to classify nodes into communities. Typically, the community assignments are passed as a message through a noisy channel and then decoded once received. Radicchi [1], instead, used a stochastic model to add noise that introduced community structure into the graph. He also produced an iterative quadratic time algorithm for decoding, based on the Gallagher decoder, and tested it on graphs produced by the stochastic block model. We introduce a reduced approximation that is also run iteratively. In this version, a changing messages is passed between edges that exist, while a constant message is passed among unconnected nodes.
We implemented both the original and reduced algorithm each with two version. In the Regular version, a random node is given a large belief for its community while in the Random version, all nodes are given a random value between -1 and 1. Each run of the algorithm splits the network into two communities. The algorithm is rerun on each split until no new further communities are formed. We show the results of the reduced algorithm in Figure 1. In all cases of the LFR benchmark, the Random initial condition outperformed the Regular condition. In the real networks, the algorithm performed the best on the NCAA football network. This is expected as football teams play more teams within the same conference rather than between conferences. In most cases, the algorithm either perfectly found the communities or grouped all nodes into one community.