Characterizing Branching Processes from Sampled Data

Repository for the course on Monte Carlo Algorithms and Markov Chains at PESC - Programa de Engenharia de Sistemas e Computação from UFRJ - Federal University of Rio de Janeiro, taught by Prof. Daniel Ratton Figueiredo.

Developed by Ronald Albert.

The project

The project is an implementation of the approach taken by the article from Fabricio Murai, Bruno Ribeiro, Don Towsley e Krista Gile, where the authors estimate the offspring distribution of a branching process from observed nodes of the generated tree. This project is a mere implementation of the methodology developed by the authors of the article mentioned above.

It's entirely implemented in python and requires several python libraries to be executed. All of the required libraries are listed at requirements.txt as well as their respective versions. In order to install all the necessary package one could run the following command

pip install -r requirements.txt

File list

• run.py

Script that runs the entire project. It's the main file of the project, and generates the results available at the results folder.

• experiment.py

Script where the function for a single experiment is defined as well as the evaluation function for the results obtained.

• sampling_model.py

Script for functions related to sampling and doing inference on Galton-Watson processes. They are mostly used as auxiliary function for the MCMC algorithm.

• graph_mcmc.py

Script where the MCMC algorithm is defined, the transition and acceptance probability functions serve as auxiliary for the main function of generating a path in the Markov Chain constructed.

• optimization.py

Script for the optimization fo the likelihood function in order to estimate the offspring distribution of the desired Branching Proccess.

Execution

After installing all the necessary packages, one can run the project by executing the following command

python run.py

Results

The results obtained by running the project are available at the results folder. The results are in pickle format and can de loaded into a python Dictionary object by perfoming the command

with open('results/<result_file_name>.pkl', 'rb') as f:
    results = pickle.load(f)