posteruole/randomized_greedy_algorithm

The implementation of algorithms described in the "Cluster Cores and Modularity Maximization" research paper for the purpose of Scientific Computing master studies course.

Randomized greedy algorithm

This repository contains the student project that has been created for the purpose of Scientific Computing course on the master studies at the Faculty of Mathematics, University of Belgrade.

About the project

In this project we have tried to implement every algorithm that is mentioned and described in the "Cluster Cores and Modularity Maximization" research paper written by Michael Ovelgonne and Andreas Geyer-Schulz. Those algorithms are: plain greedy algorithm, randomized greedy algorithm and the fast randomized greedy algorithm. We have also implemented some terms and definitions that are used for validating the quality of graph clustering like modularity function.

Files and folders within repository

The repository consist of the following items. Every single one of them will be listed and briefly explained below:

• Instances - a folder that contains graph instances with which we were working with;

• Scripts - a folder that contains two short Python scripts that actually represent unoptimized implementation of plain greedy and randomized greedy algorithm;

• randomized_greedy_algorithm.ipynb - the most important file in the repository. It contains short explanation and implementation of the algorithms mentioned in the research paper we refer to in previous section;

• notes.md - just a file from which we generate output.pdf file;

• output.pdf - a file that contains all of our understandings of the things discussed in the paper.

Team members

• Andrija Urošević
• Petar Tešić

References

Everything implemented in the randomized_greedy_algorithm.ipynb Jupyter notebook is based on the, already couple of times mentioned, research paper that you can find on this link https://ieeexplore.ieee.org/document/5693431.