Local algorithms for community detection

Overview

The idea of community detection based on the local information (local neighborhood) is wide spread in analysis of graphs. Recently several theoretically inspired algorithms were proposed [1,3], which solve the community detection problem by message passing between graph nodes. The paper [2] is based on similar ideas, but starts from certain testing-based iterative procedure. The goal of the project is to develop coherent framework for the graph analysis based on local information allowing for community detection and node classification with node labels and side information at nodes possibly available. The project is strongly correlated with project Community detection with adaptive weights.

Tasks

  1. Study the paper [1] and get familiar with the approximate message passing for community detection.
  2. Study the paper on adaptive weights community detection [2].
  3. Compare the approaches from [1], [2] and [3].
  4. Choose the approach and extend to the situation with partially observed labels and side information.

References

[1]  Cristopher Moore (2017) The Computer Science and Physics of Community  Detection: Landscapes, Phase Transitions, and Hardness. arXiv:1702.00467
[2] Efimov, Adamyan, Spokoiny (2017) Adaptive nonparametric clustering. arxiv 1709.09102.
[3] Cai, T. T., Liang, T., & Rakhlin, A. (2017). Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information. arXiv preprint arXiv:1709.03907.