Graph Ranking Algorithms in Python

This project implements and analyzes graph-based ranking algorithms, including multiple methods for PageRank, TextRank for keyword extraction, and Personalized PageRank.

The focus of this project is to understand the mathematical foundations, convergence behavior, and practical applications of ranking algorithms from a linear algebra perspective.

---

Implementations

1. PageRank (P1 -- P1-PageRank.ipynb)

Three different implementations are provided:

• Eigen Decomposition -- Computes PageRank using eigenvector analysis of the transition matrix.
• Power Method -- Iterative computation of the stationary distribution until convergence.
• Random Walk Simulation -- Empirical approximation using stochastic random walks.

These approaches are compared to highlight theoretical equivalence and practical differences.

---

2. TextRank (P2 -- P2-TextRank.ipynb)

Application of PageRank to Natural Language Processing:

• Construct word co-occurrence graphs
• Apply PageRank to rank words
• Extract important keywords from text files

Input datasets (e.g., Cinderella.txt, Beauty_and_the_Beast.txt) are located in the data/ directory.

---

3. Personalized PageRank (P3 -- P3_PersonalizedPageRank.ipynb)

Extension of standard PageRank using a custom teleportation (preference) vector.

This demonstrates how biasing the teleportation distribution affects the final ranking and stationary distribution.

---

Project Structure

.
├── data/                              # Text datasets for TextRank
│   ├── Cinderella.txt
│   ├── Beauty_and_the_Beast.txt
│   └── ...
│
├── src/                               # Core Python implementations
│   ├── pagerank.py
│   └── textrank.py
│
├── P1-PageRank.ipynb
├── P2-TextRank.ipynb
├── P3_PersonalizedPageRank.ipynb
└── README.md

---

Requirements

• Python 3.x
• numpy
• networkx (if used)

Install dependencies:

pip install numpy networkx

---

Running the Code

From the project root directory:

python src/pagerank.py
python src/textrank.py

Ensure the required text files are available inside the data/ directory.

---

Academic Context

This project was developed as part of the Linear Algebra course at K. N. Toosi University of Technology (KNTU).