Conducted as part of the Algorithmics course at UPC.
Graph percolation is a fascinating study of how connectivity evolves in a network as edges or nodes are probabilistically removed. This project aimed to explore percolation behavior in different graph types, analyzing how the number and size of connected components change as the percolation probability \\(p\\) varies.
The graphs studied included 2D and 3D grids, Random Geometric Graphs (RGGs), and Connected Caveman Graphs. These diverse graph types provided insights into how structure affects percolation dynamics.
The project employed Python and NetworkX to generate graph instances and simulate percolation processes. For each graph type, nodes or edges were randomly removed with survival probability \\(p\\), and the number of connected components was calculated. These steps were repeated across multiple trials to ensure statistical reliability.
Computational challenges arose with larger graph sizes, necessitating the use of Google Cloud servers equipped with 32 virtual cores and 150 GB of RAM. This allowed for parallelized simulations and efficient handling of massive datasets.
These findings underscore the importance of graph structure in determining resilience and connectivity under probabilistic failure scenarios.
Access the full project details through the following resources: