AMP–BP

Implementation of the AMP–BP algorithm to solve cSBM, as described in the article "Optimal Inference in Contextual Stochastic Block Models". It performs optimal estimation of communities in the balanced cSBM, in the unsupervised and semi-supervised cases.

Requirements

python3, numpy

For N=10^4 nodes, a few gigabits of RAM are necessary, depending on \alpha. It runs on a single CPU core.

Use

Launch the following command:

python AMP-BP.py N alpha mu_to_the_square lambda rho

It outputs the performances of AMP–BP averaged over many experiments in this format:

N, alpha, mu_to_the_square, lambda, rho, mean of q_U, error on q_U, mean of q_V, error on q_V, average number of times the algorithm converged well

Other parameters are defined in the file AMP-BP.py itself. They are:

• d, float average degree;
• maxIter, int maximal number of iterations;
• varInit, float initial variation to break the symmetry;
• err, float convergence criterion;
• doParameterEstimation, bool true for doing parameter estimation;
• Nexp, int number of independant experiments.