This repository contains the code implementation for the research conducted on analyzing the metric dimension of graphs. The code provides various notebooks to investigate and understand the metric dimension of different graph types.
The research conducted in this project aims to analyze the metric dimension of graphs and provides insights into their characteristics. The code implementation covers different aspects discussed in the report, including:
- Analysis of metric dimension for Erdős-Rényi random graphs
- Simulations with the Stochastic Block Model to determine optimal inter-community edge probability for minimal metric dimension
- Investigation of resolving set structures in different graph types
- Implementation of two proposed algorithms to identify small resolving sets
The code in this repository requires the following dependencies:
- Python 3.7 or above
- NetworkX library
- NumPy library
- Matplotlib library
- Plotly library
- SciPy library
- tqdm library
- pickle library
Ensure that these dependencies are installed before running the code.
Code structure:
.
├── Erdős–Rényi simulations
│ ├── MD_vs_n_with_fixed_p.ipynb
│ ├── MD_vs_p_with_constant_n.ipynb
│ ├── Simulations_non_monotonous.ipynb
│ ├── non_monotonous_sim_results
│ ├── proba_of_resolving_vs_subset_size.ipynb
│ └── proba_of_resolving_vs_subset_size_sim_results
├── ICH-algo
│ ├── LICENSE
│ ├── README.md
│ ├── multilateration.py
│ └── multilateration_tests.py
├── Nodes selection strategies
│ ├── Nodes_to_include_in_resolving_set.ipynb
│ ├── Sampling the subsets using different centrality measures.ipynb
│ └── simulations
├── README.md
├── Real graphs simulations
│ ├── Copenhagen - hardest nodes to resolve.ipynb
│ ├── Copenhagen - monotonicity of metric dimension in real graphs.ipynb
│ ├── Copenhagen graphs
│ └── proba_of_resolving_vs_subset_size-realgraph.ipynb
├── Stochastic Block Model simulations
│ └── SBM_simulations.ipynb
└── helpers.py
To run the code and replicate the experiments and simulations mentioned in the report, follow these steps:
- Clone this repository to your local machine.
- Install the required dependencies using the package manager of your choice (e.g., pip).
- Navigate to the appropriate directory and run the desired Jupyter notebooks.
- Adjust the parameters and configurations as necessary to experiment with different graph types, sizes, and number of iterations.
- Analyze the output and results generated by the code to gain insights into the metric dimension of the graphs.
The main results obtained from running the code are included in the report.
Contributions to this research project and code implementation are welcome. If you encounter any issues, have suggestions for improvements, or would like to contribute new features, please submit a pull request or open an issue on this repository.
This project is licensed under the MIT License, which allows for open collaboration and sharing of the code. Please review the license file for more details.