Finding Short Cycles in Private Networks

This is the code I used to test the algorithm as described in my thesis¹. Paper is WIP.

User instructions

Requirements

To run the experiments, ensure you have CMake, GNU Make, and GCC version 8 or newer installed. On Linux systems that use apt (e.g. Debian, Ubuntu), you can install these programs with

sudo apt install -y cmake make gcc

To plot the experiments, ensure you have Python version 3.10 or newer installed. You can then install the Python packages with

pip install .

As usual for Python, it is recommended that you do so inside a virtualenv.

Usage

To compile and run the experiments, execute the commands

cmake .
make
./cycle_detection_experiments

Results are written to the directory out/. Each time you re-run the experiments, a separate log file is written to out/.

To plot the results contained in <filename.log>, run (inside your virtualenv, if you created one)

cd src/
python3 -m plotcreator <filename.log>

To automatically select the most recent file in out/, run (inside your virtualenv, if you created one)

cd src/
python3 -m plotcreator "$(find ../out/ -type f -printf "%T@ %p\n" | sort -n | cut -d' ' -f 2- | tail -n 1)"

Figures are stored in out/fig/.

Inspecting published results

If you want to inspect the outputs generated by the authors for the paper without running the experiments yourself, you can download the pre-generated results from 4TU.ResearchData. Download the file bounded-private-cycle-detection.out.zip and extract it so that the directory out/ is in the same directory as this README.md file. The directory out/ should itself contain the directory log/, which contains the .csv file describing the experiments' outputs. You can then either inspect that .csv file manually, or you can run (inside your virtualenv, if you created one)

cd src/
python3 -m plotcreator ../out/log/all-results.log

to generate the plots seen in the paper, and store them in out/fig/.

Footnotes

1. J. Jense, Finding Bounded-Length Cycles in Decentralised Networks under Privacy Constraints, M.Sc. thesis, Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, Delft, Netherlands, 2024. Online ↩