🌍 A-T-L-A-S: Graph Theory Meets the Game of Geography

"India" ➜ "Australia" ➜ "Austria" ➜ "Albania"... can you trap your opponent using the power of graph theory?

This project reimagines the classic word game ATLAS as a directed graph problem. We explore how concepts from graph theory, community detection, and machine learning can provide strategies and predictive insight into the game using real-world datasets of countries and cities.

📘 Project Summary

• Constructed 3 ATLAS-style graphs:
  1. Country Only
  2. City Only (top 500 by population)
  3. Country + City Combined
• Analyzed key properties using NetworkX to uncover gameplay strategies
• Performed community detection using Louvain and Girvan–Newman algorithms
• Built a link prediction model using Node2Vec and GNNs to anticipate valid transitions
• Created visualizations and strategic insights based on node connectivity

🗂️ File Overview

File	Description
atlas.ipynb	Main notebook with graph creation, EDA, and strategy logic
observations.ipynb	Visualizations and exploratory insights
AtlasBONUS.ipynb	BONUS: Link prediction with Node2Vec & GNN
observations.pptx	Strategic insights in presentation format
precog.pptx	Final presentation for submission

▶️ How to Run

1. Install dependencies:

   pip install -r requirements.txt

2. Open each notebook in Jupyter or Colab:
   • Run the first code cell
   • Restart the kernel
   • Run all cells again
3. AtlasBONUS.ipynb was developed on Colab; others were built locally.
4. Some interactive graphs are exported as .html and should be opened using Live Server in VSCode or a local browser.

📈 Graph Analysis & Strategy

We used 6 graph theory concepts to extract insights from gameplay:

• Degree & Out-degree centrality
• PageRank
• Strongly Connected Components
• Diameter & Density
• Terminal nodes (Dead Ends)
• Clustering coefficient

These were evaluated across all 3 graphs to understand how the game evolves with dataset complexity.

🔎 Community Detection

• Algorithms: Louvain, Girvan–Newman
• Evaluated via: Modularity score
• Communities showed alignment with geographic and linguistic groupings
• Strategic insight: Jumping across communities can isolate opponents

🤖 BONUS: Link Prediction

Aspect	Approach
Model	Node2Vec embeddings + Logistic Regression
Optional	Graph Neural Network via PyTorch Geometric
Features	Start & end characters, character embeddings
Training	Unsupervised on masked edges
Objective	Predict future transitions in gameplay

📂 Dataset Sources

• Countries: Britannica – List of Countries
• Cities: World Population Review

📚 Resources & References

Graph Theory

• Professor Foote – Intro to NetworkX (YouTube)
• Wikipedia – Graph Centrality
• Wikipedia – Graph Properties

Community Detection

• Community Detection Algorithms (Medium)
• Stanford CS224W – ML with Graphs
• From Louvain to Leiden – Scientific Reports
• YouTube – Louvain, Girvan-Newman, Modularity

Link Prediction

• StellarGraph Node2Vec Tutorial
• Kaggle: Node2Vec + ML
• MovieLens GNN Notebook (Colab)

Inspiration

• I Made a Graph of Wikipedia…

🛠 Tools & Libraries

• Python 3.x
• networkx, matplotlib, plotly, pandas, numpy
• community (Louvain method)
• scikit-learn, gensim
• PyTorch, PyTorch Geometric
• StellarGraph

🙌 External Support

This project utilized ChatGPT to:

• Refine grammar and clarity in written explanations
• Debug syntactic errors in code
• Suggest modeling changes in GNN training
• Maintain library compatibility and resolve import issues

👨‍💻 Authors

Developed by Siddharth Mago Part of a research-focused study on Graph Algorithms and Machine Learning

---