Code and results for a research project studying the detectability phase transition in the network alignment problem, using a Bayesian / statistical-physics approach solved with MCMC parallel tempering.
Given a "blueprint" graph and several noisy, unlabeled copies of it, network alignment tries to recover the node correspondence (alignment) between the copies. This project models the problem as finding the alignment that minimizes an energy function
There is a temperature threshold
This study builds on the probabilistic network alignment model and MCMC parallel-tempering algorithm from Lázaro, Guimerà & Sales-Pardo, "Probabilistic alignment of multiple networks", Nature Communications 16, 3949 (2025). There, an unknown blueprint graph
This study uses the same model and sampler, but restricted to a single-error-rate noise model: remove_only=True throughout configs/). This is a meaningful special case since, in the
The detectability transition is, at its core, about whether the ground-truth energy
For a graph with
-
While
$H_{true} < H_{1/N!}$ (lower noise), the true alignment sits below the floor: it is a genuine, statistically rare minimum. Replicas at temperatures below$T_{crit}$ can equilibrate there, and the true alignment is detectable. -
Once
$H_{1/N!}$ crosses below$H_{true}$ (higher noise), the floor itself becomes lower than the ground truth.$H_{true}$ is no longer an exceptional minimum — an equally good or better energy is expected to be reachable by chance alone. From this point on,$H_{true}$ becomes undetectable by any replica at any temperature, i.e. lowering the temperature no longer helps, because the problem isn't thermal escape, it's that the signal itself has been swamped by the noise floor. Replicas below$T_{crit}$ stabilize around$H_{1/N!}$ instead of$H_{true}$ .
In other words, plots/theor_H_true.dat, plots/theor_H_lowend_gauss.dat / plots/theor_H_lowend_hypergeom.dat, and plots/avg_H_lowend_fit.dat, and visualized in figures/lowend_energs.pdf.
| Path | Description |
|---|---|
functions.py |
Core library: noisy-copy generation, energy function |
run_mcmc.py |
CLI entry point to run the MCMC parallel-tempering algorithm from a JSON config. |
sample_energy_distribution.py |
CLI entry point to sample the energy distribution of random (uninformed) alignments, used to estimate the noise floor |
configs/ |
Configuration files for each experiment (noise level, graph size, replica count, etc.). default_config.json is the template — see configs/README.md for a full parameter reference. |
plotting.ipynb |
Notebook that generates every figure in the study from the precomputed summary data in plots/. |
plots/ |
Precomputed summary statistics (.dat) — theoretical/empirical accuracy, critical temperature, energy vs. temperature, etc. Sufficient to reproduce all main figures without the raw sweep data. |
figures/ |
Final result figures (PDF): alignment accuracy, energy statistics per temperature. |
test_run.csv |
Example output of a single MCMC run, for reference on the results format. |
requirements.txt |
Python dependencies. |
The raw parameter-sweep output (LowTemp/, one CSV per noise level/replica/seed, ~10 GB total) and intermediate energy-distribution samples (Dists/, ~80 MB) are not included in this repository due to their size. They can be:
- regenerated locally with
run_mcmc.py/sample_energy_distribution.pyand the configs inconfigs/, or - made available on request (dadi.svet@gmail.com).
The .dat files in plots/ already contain the summary statistics extracted from that raw data, so all figures in plotting.ipynb are reproducible without it.
python -m venv .venv && source .venv/bin/activate
pip install -r requirements.txtRun a single MCMC parallel-tempering experiment, after setting up its parameters inside a config file:
python run_mcmc.py -config configs/default_config.json -filename my_run.csvTo estimate the energy distribution for a given configuration, run the following command after setting up the corresponding config file:
python sample_energy_distribution.py -config configs/default_config.json -filename my_dist.csvModify or create a config file in configs/ to change the noise level, graph size, number of replicas, or number of MCMC steps. Results are written as CSV to the output_dir specified in the config, details on every parameter can be found in the .md file inside configs/.
Set load_pkl/pkl_path in the config to reuse the exact blueprint and observations pickled by a prior run, so the sampled distribution is directly comparable to that run's
To explore results and regenerate figures, open plotting.ipynb.
MIT — see LICENSE.