Maximum Clique Project

A comprehensive implementation and analysis of various maximum clique algorithms.

Project Structure

MaximumClique/
├── algorithms/                          # Core algorithm implementations
│   ├── bron_kerbosch.py
│   ├── greedy.py
│   ├── local_random.py
│   ├── local_search.py
│   ├── randomized.py
│   └── simulated_annealing.py
├── bonus/                               # Additional features and analysis
│   ├── bk_runtime_analysis.png
│   ├── desc_ree.py
│   ├── estimate_bk.py
│   ├── my_logic_tree.png
│   └── recommend.py
├── data/                                # Graph datasets
│   ├── download_graphs.py
│   ├── small_graphs/                   # < 100 nodes
│   ├── medium_graphs/                  # 100-400 nodes
│   └── large_graphs/                   # > 400 nodes
├── experiments/                         # Jupyter notebooks for testing
│   ├── small_graphs.ipynb
│   ├── medium_graphs.ipynb
│   ├── large_graphs.ipynb
│   └── random.ipynb
├── results/                             # Generated outputs and visualizations
│   ├── experiment_log.csv
│   ├── graphs/                         # Graph visualizations by size
│   ├── plots/                          # Analysis charts
│   ├── scripts/                        # Plot generation scripts
│   └── std_analysis/                   # Statistical analysis
├── README.md
└── requirements.txt

---

Setup

Before running any code, install the required dependencies:

pip install -r requirements.txt

---

Running Algorithms

Individual Algorithm Execution

Navigate to the algorithms directory and run any algorithm:

cd MaximumClique/algorithms
python3 bron_kerbosch.py
python3 greedy.py
python3 local_random.py
python3 local_search.py
python3 randomized.py
python3 simulated_annealing.py

Each file contains example graphs in its main() function.

---

Bonus Features

1. Algorithm Recommender

Get intelligent algorithm recommendations based on graph properties:

cd MaximumClique/bonus
python3 recommend.py

2. Bron-Kerbosch Runtime Estimator

Warning: This analysis takes days to complete!

cd MaximumClique/bonus
python3 estimate_bk.py

View results:

• bk_runtime_analysis.png - Runtime analysis visualization
• my_logic_tree.png - Decision tree logic

---

Data Management

Download New Graphs

1. Add a (name, link) tuple to the datasets list in download_graphs.py
2. Ensure compatibility with current loading and conversion formats
3. Run:

cd MaximumClique/data
python3 download_graphs.py

Available Datasets

• Small Graphs (data/small_graphs/)

  • Karate club, Dolphins, Florentine families, Les Miserables, etc.

• Medium Graphs (data/medium_graphs/)

  • Brock200 series, C125.9, C250.9, MANN_a27, Johnson16-2-4, etc.

• Large Graphs (data/large_graphs/)

  • Brock400/800 series, C500.9, C1000.9, Facebook combined, DSJC series, etc.

---

Experiments

Run experiments using Jupyter notebooks:

cd MaximumClique/experiments
# Open and run:
# - small_graphs.ipynb
# - medium_graphs.ipynb
# - large_graphs.ipynb
# - random.ipynb

---

Viewing Results

Graph Visualizations

Browse graph visualizations organized by size:

cd MaximumClique/results/graphs/
# View subdirectories:
# - small_graphs/
# - medium_graphs/
# - large_graphs/

Each graph includes:

• {graph_name}.png - Visual representation
• {graph_name}_stats.png - Statistical analysis

Analysis Plots

View comparative analysis charts:

cd MaximumClique/results/plots/

Available plots:

• algorithm_comparison_bars.png
• accuracy_comparison_chart.png
• runtime_comparison_chart.png
• memory_comparison_chart.png
• runtime_vs_quality_scatter.png
• accuracy_sparse_vs_dense.png
• runtime_sparse_vs_dense.png

Statistical Analysis

View stability and variance analysis:

cd MaximumClique/results/std_analysis/

Includes:

• coefficient_of_variation.png
• variability_heatmap.png
• accuracy_stability_by_size.png
• runtime_stability_by_size.png
• clique_size_std_by_algorithm.png
• comprehensive_comparison.csv
• summary_report.txt

---

🔧 Analysis Scripts

Generate plots and perform analysis:

cd MaximumClique/results/scripts/

# Individual scripts:
python3 accuracy_chart.py              # Generate accuracy comparisons
python3 runtime_chart.py               # Generate runtime comparisons
python3 density_accuracy.py            # Analyze density vs accuracy
python3 plot_density_runtime.py        # Plot density vs runtime
python3 runtime_vs_quality.py          # Quality-runtime tradeoff analysis
python3 std_deviation_analysis.py      # Statistical variance analysis
python3 generate_bar_graphs.py         # Generate bar chart comparisons
python3 plot_from_logs.py              # Generate plots from experiment logs
python3 save_graphs.py                 # Save graph visualizations
python3 debug_algorithms.py            # Debug and test algorithms

---

Experiment Logs

All experiment results are logged to:

MaximumClique/results/experiment_log.csv

---

🛠️ Setup

Install required dependencies:

pip install -r requirements.txt

---

Algorithm Overview

Algorithm	Type	Best For
Bron-Kerbosch	Exact	Small to medium graphs, finding all cliques
Greedy	Heuristic	Fast approximations, large graphs
Local Search	Optimization	Medium graphs, quality solutions
Local Random	Randomized	Diverse solution space exploration
Randomized	Probabilistic	Large graphs with time constraints
Simulated Annealing	Metaheuristic	Complex graphs, avoiding local optima

---

Notes

• Results are automatically saved with timestamps
• All visualizations are PNG format
• CSV files contain raw data for further analysis
• Use the algorithm recommender for optimal algorithm selection based on your graph properties