# Graph Partitioning Techniques and Applications in Community Detection

## Introduction
Networks are fundamental structures in various domains, representing relationships between entities such as social connections, biological interactions, or technological links. Analyzing these networks provides insights into their organization, function, and dynamics. Graph partitioning is a crucial technique for understanding complex networks by dividing them into smaller, more manageable clusters or communities. This process simplifies analysis, reveals underlying structures, and enables the identification of important nodes or groups.

This study evaluates the effectiveness of three graph partitioning methods: Louvain, Walktrap, and spectral clustering. The Louvain method is a greedy algorithm that iteratively optimizes modularity, a metric quantifying the quality of network partitions. The Walktrap method utilizes random walks to assess community structure, grouping nodes based on their visitation probabilities. Spectral clustering leverages the eigenvectors of the graph Laplacian to identify clusters with minimal connections between them.

To assess the performance of these methods, we employ two evaluation metrics: modularity and Variation of Information (VI). Modularity measures the strength of division into clusters, while VI quantifies the similarity between different partitions. We apply these methods to two practical examples: clustering synthetic datasets and classifying Persian cats from Boxer dogs using image-based graph representations.

Our analysis provides insights into the strengths and weaknesses of each method, guiding the selection of appropriate techniques for specific network analysis tasks. The findings contribute to a better understanding of graph partitioning and its applications in community detection.

## Graph Partitioning
Graph partitioning is the process of dividing a graph into distinct clusters or communities of nodes. This is achieved by identifying groups of nodes with denser connections to each other than to nodes in other clusters. Effective partitioning reveals the graph's underlying structure and simplifies analysis by breaking it down into smaller, more manageable components.

### Modularity
Modularity is a widely used quality measure for evaluating graph partitions. It quantifies the difference between the observed connectivity within clusters and the expected connectivity if edges were randomly distributed. A higher modularity score indicates a stronger community structure, with denser internal connections within clusters than between clusters. The modularity score ranges from -1 to 1, with positive values suggesting a meaningful partition.

To be more precise, the modularity $Q$ is defined as:

$$
Q = \frac{1}{2m} \sum_{i,j} \left( A_{ij} - \frac{k_i k_j}{2m} \right) \delta(c_i, c_j),
$$

where:
- $A_{ij}$ is the adjacency matrix of the network,
- $k_i$ and $k_j$ are the degrees of nodes $i$ and $j$,
- $m$ is the total number of edges,
- $\delta(c_i, c_j)$ is 1 if nodes $i$ and $j$ belong to the same community, otherwise $0$.

### Methods

#### Louvain Method
The Louvain method is a greedy algorithm that iteratively optimizes modularity to identify the best graph partition. It aims to find the community structure that maximizes the modularity score.

##### Key Features
1. Greedy optimization
2. Iterative refinement
3. Modularity maximization

##### Algorithm Steps

FUNCTION Louvain_Method(G):
    REPEAT
        # Step 1: Initialize
        FOR each vertex n in G DO:
            Assign n to its own community
        END FOR
        Save initial modularity Q_initial

        # Step 2: Local Optimization
        moved_vertices <- True
        WHILE moved_vertices DO:
            moved_vertices <- False
            FOR each vertex n in G DO:
                c <- Find neighboring community maximizing modularity increase
                IF moving n to c results in positive modularity increase THEN:
                    Move n to community c
                    moved_vertices <- True
                END IF
            END FOR
        END WHILE

        # Step 3: Check modularity improvement
        Q_new <- Compute_Modularity(G)
        IF Q_new > Q_initial THEN:
            end <- False
            Display current partition
            Transform G into the graph between communities
        ELSE:
            end <- True
        END IF
    UNTIL end
    RETURN final partition and modularity
END FUNCTION

##### Advantages
1. Efficiency: The Louvain method is computationally efficient, with complexity approximately $𝑂(n \log n)$, where $𝑛$ is the number of nodes.
2. Multi-Scale Detection: It provides a hierarchical view of the network, revealing communities at different resolutions.
3. Flexibility: It works for weighted, unweighted, directed, and undirected graphs.
4. High Modularity: Often achieves modularity scores close to the theoretical maximum.

##### Disadvantages
1. Modularity Resolution Limit: The algorithm may fail to detect small communities in large networks due to the resolution limit of modularity.
2. Non-Deterministic: The outcome can vary depending on the order of node processing, making it sensitive to initial conditions.

#### Walktrap Method
The Walktrap method uses random walks to assess community structure. It is based on the idea that random walks tend to stay within communities due to the higher density of internal connections.

##### Key Concepts
1. **Random Walks:**
* For each node, the algorithm computes the probability distribution of a random walker over a fixed number of steps (usually 2 or 3).
* This involves matrix multiplications for the transition matrix $P$: \begin{align*}P=D^{−1}A, \end{align*} where $A$ is the adjacency matrix and $D$ is the degree matrix.
2. **Community Proximity:**
* The algorithm calculates the distance between communities based on the random walk distributions: $$d(C_i,C_j) = \sqrt{\sum_{k=1}^{n}\frac{P^{t}_{C_ik}-P^{t}_{C_jk}}{D_{kk}}},$$
* This step is repeated for all pairs of communities.
3. **Hierarchical Merging:**
* Communities are iteratively merged based on their proximity (distance), starting with each node as its own community.
* At each step, the algorithm identifies and merges the closest pair of communities.

##### Algorithm Steps

FUNCTION walktrap_clustering(graph, t, num_clusters)
    # Step 1: Initialize Communities
    communities <- INITIALIZE_COMMUNITIES(graph)  # Each node is its own community

    # Step 2: Random Walk Similarity
    FOR each node i in graph DO
        P[i] <- RANDOM_WALK_PROBABILITY(graph, start_node=i, steps=t)

    # Step 3: Distance Metric
    FOR each pair of communities (Ci, Cj) DO
        distance(Ci, Cj) <- L2_NORM(P[Ci] - P[Cj])  # Average random walk distribution

    # Step 4: Merge Closest Communities
    WHILE NUMBER_OF_COMMUNITIES > num_clusters DO
        (Ci, Cj) <- FIND_CLOSEST_COMMUNITIES(distance)
        Ci <- MERGE_COMMUNITIES(Ci, Cj)

        # Step 5: Update Distributions
        P[Ci] <- AVERAGE_DISTRIBUTION(P[Ci], P[Cj])
        REMOVE_COMMUNITY(Cj)

    # Step 6: Repeat Until Convergence
    END WHILE

    RETURN COMMUNITIES
END FUNCTION

* Output
The algorithm generates a dendrogram (a tree-like structure) representing the hierarchical clustering of nodes. By cutting the dendrogram at different levels, communities at various resolutions can be identified.

##### Advantages
1. **Multi-Scale Detection:** The algorithm can identify communities at different resolutions by stopping the merging process at various stages.
2. **Dynamic Sensitivity:** Random walks naturally incorporate network structure and dynamics, making the algorithm robust to variations in edge density.
3. **Flexibility:** It works on weighted, unweighted, directed, and undirected graphs.

##### Disadvantages
1. **Computational Complexity:** Calculating random walk distributions and merging communities can be computationally intensive for large networks.
2. **Fixed Walk Length:** The performance of the algorithm depends on the choice of the random walk length 𝑡, which may require tuning.

#### Spectral Clustering
Spectral clustering utilizes the eigenvectors of the graph Laplacian matrix to partition the graph. It aims to find clusters with minimal connections between them.

The graph Laplacian $L$ is defined as:

$$
L = D - A,
$$

where $D$ is the degree matrix (a diagonal matrix with $D_{ii} = \sum_j A_{ij}$, and $A$ is the adjacency matrix.

##### Cut
A “cut” is a measure used in spectral bisection to quantify the quality of a partition. It calculates the total weight of edges that need to be removed to separate the graph into two parts. Mathematically, the cut value between two sets of nodes $A$ and $B$ is:

\begin{align*}
\text{Cut}(S, T) = \sum_{i \in A, j \in B} A_{ij}.
\end{align*}

Consider index verctor:

$$
s= \begin{cases}
1 & \mbox{for}& i \in A \\
-1 & \mbox{for}& i \in B
\end{cases}
$$

and $ss^T=n$. Since

$$
\frac12(1-s_i s_j)=\begin{cases}
1 & \mbox{for}& i \in A ,j \in B\\
0 & \mbox{for}& i,j\in B \ or\ i,j\in A
\end{cases}
$$

then

\begin{align*}
\text{Cut}(S, T)
&=\frac12\sum_{i,j}(1-s_i s_j)A_{ij} \\
&=\frac12\sum_{i,j}s_i s_j(k_{i}\delta_{ij}-A_{ij})\\
&=\frac12sLs^T
\end{align*}

Minimizing cut corresponds to finding the eigenvector $s$ associated with the second smallest eigenvalue of the matrix $L$

##### Algorithm Steps

FUNCTION spectral_clustering_with_cut(graph, k)
    # Input:
    #   graph: Weighted graph represented by adjacency matrix (n x n)
    #   k: Number of clusters

    # Step 1: Compute the Laplacian matrix
    D <- DEGREE_MATRIX(graph)  # Diagonal matrix of node degrees
    L <- D - graph  # Unnormalized Laplacian matrix

    # Step 2: Eigenvalue decomposition
    vals, vecs <- EIGEN_DECOMPOSITION(L)

    # Step 3: Clustering
    IF k = 2 THEN
        fiedler_vector <- vecs[:, 1]  # Second smallest eigenvector
        labels <- SIGN(fiedler_vector)  # Divide nodes into two groups
    ELSE
        # Use the first k eigenvectors for clustering
        feature_matrix <- vecs[:, 0:k]
        labels <- KMEANS(feature_matrix, k)

    # Output:
    #   labels: Cluster labels for each node
    RETURN labels
END FUNCTION

##### Advantages
1. **Flexibility**: Works well for non-convex clusters and irregular structures.
2. **Global Perspective**: Incorporates the entire graph structure by using eigenvalues and eigenvectors.

#### Disadvantages
1. **Computational Cost**: Computing eigenvalues and eigenvectors can be expensive for large graphs.
2. **Sensitivity to Parameters**: Performance depends on the choice of similarity measure and the number of clusters .

## Variation of Information (VI)

### Why Use VI for Evaluation?
The Variation of Information (VI) metric is used to compare different graph partitions or clusterings. It is a robust and versatile metric rooted in information theory, making it suitable for various applications. Unlike traditional metrics like the Rand index, VI quantifies the information lost and gained when transitioning between two clusterings, capturing both agreement and disagreement in a mathematically sound manner.

#### Advantages of VI
1. **Theoretical Soundness**: VI measures the amount of information lost and gained when transitioning between two clusterings. It captures both agreement and disagreement between clusterings in a mathematically principled way.
2. **Scalability**: VI is independent of the dataset size. This makes it particularly valuable for comparing clusterings across datasets with varying sizes and structures.
3. **Interpretability**: Lower VI values indicate higher similarity between the clusterings, while higher values reflect greater divergence. This aligns with intuitive expectations.
4. **Robust to Overfitting**: Unlike modularity, which can be artificially inflated by splitting clusters, VI provides an unbiased measure of partition quality.

### How VI Works
VI combines two key concepts from information theory: entropy and mutual information.

- **Entropy ($H$)**: Measures the uncertainty in a single clustering. A clustering with highly imbalanced cluster sizes will have lower entropy compared to one with evenly distributed clusters.
* $H(C) = -\sum_k P(k) \log P(k)$, where $P(k)$ is the proportion of data points in cluster $C_k$.
- **Mutual Information $(I)$**: Measures the amount of information shared between two clusterings $C$ and $C'$. It quantifies how much knowing one clustering reduces uncertainty about the other.
* $I(C, C') = \sum_{k, k'} P(k, k') \log \frac{P(k, k')}{P(k)P(k')}$
- **Variation of Information $(VI)$**: Combines entropy and mutual information to evaluate the dissimilarity between two clusterings: $$VI(C, C') = H(C) + H(C') - 2I(C, C')$$ Alternatively, it can be expressed as the sum of conditional entropies: $$VI(C, C') = H(C|C') + H(C'|C)$$ where $H(C|C')$ quantifies the information about $C$ that is not captured by $C'$.

#### Example
- If two clusterings are identical, $H(C|C') = H(C'|C) = 0$, so $VI = 0$.
- If the two clusterings are completely unrelated, $VI$ reaches its maximum value.

## Example

### Synthetic Dataset Clustering
Clustering is an unsupervised machine learning technique used to group data points into clusters based on their similarities. Unlike classification, clustering does not rely on labeled data, making it a powerful tool for exploring and analyzing unstructured datasets. It is widely used in various fields such as image processing, customer segmentation, bioinformatics, and more.

In this study, we utilize the `sklearn.datasets` module from the Scikit-learn library, which provides a variety of datasets for machine learning tasks. Specifically, we focus on synthetic datasets that are well-suited for evaluating clustering algorithms.

#### Import Necessary Libraries

import networkx as nx  
import numpy as np  
import matplotlib.pyplot as plt 
from community import community_louvain  # For Louvain community detection
from sklearn.cluster import SpectralClustering  # For Spectral Clustering
from scipy.spatial.distance import cdist, pdist  # For distance calculations
from scipy.cluster.hierarchy import linkage, fcluster  # For hierarchical clustering
from scipy.stats import entropy
from sklearn.datasets import load_digits  # For loading datasets

#### Helper Functions

##### Modularity Calculation
Calculate the modularity score of a graph given its partition to evaluate clustering quality.

def Modularity(graph, partition):
    """Calculate the modularity score of the graph."""
    A = nx.to_numpy_array(graph)
    m = np.sum(A) / 2
    Q = 0.0
    communities = set(partition.values())

    for c in communities:
        nodes_in_c = [node for node, community in partition.items() if community == c]
        for i in nodes_in_c:
            for j in nodes_in_c:
                Aij = A[i, j]
                ki = np.sum(A[i])
                kj = np.sum(A[j])
                Q += Aij - (ki * kj / (2 * m))

    return Q / (2 * m)

##### Variation of Information (VI)
Calculate the Variation of Information (VI) between true labels and predicted labels.

def compute_vi(true_labels, pred_labels):
    """Calculate Variation of Information (VI)."""
    n_true_labels = len(set(true_labels))
    n_pred_labels = len(set(pred_labels))
    contingency = np.zeros((n_true_labels, n_pred_labels))

    for i, true_label in enumerate(true_labels):
        contingency[true_label, pred_labels[i]] += 1

    n = np.sum(contingency)
    row_sums = np.sum(contingency, axis=1)
    col_sums = np.sum(contingency, axis=0)

    h_true = entropy(row_sums / n, base=2)
    h_pred = entropy(col_sums / n, base=2)

    mutual_info = np.sum(
        [
            (contingency[i, j] / n) * np.log2((contingency[i, j] / n) /
                                            ((row_sums[i] / n) * (col_sums[j] / n)))
            for i in range(len(row_sums)) for j in range(len(col_sums))
            if contingency[i, j] > 0
        ]
    )
    return h_true + h_pred - 2 * mutual_info

#### correct label

def right_label(y,pred_label):
    r=1000
    best_labels=pred_label.copy()
    for i in range(r):
        t=np.random.randint(0,len(pred_label))

        u=pred_label[t]
        v=y[t]
        if u!=v:
            temp=pred_label.copy()
            for j in range(len(pred_label)) :
                if pred_label[j]==u:
                    pred_label[j]=v
            for k in range(len(pred_label)) :
                if temp[k]==v:
                    pred_label[k]=u
        if np.mean(y == pred_labels)>np.mean(y == best_labels) :
            best_labels=pred_label.copy()
            
    return best_labels

#### Main Functionality
1. Load Dataset and Construct Similarity Matrix: Load the dataset from `load_digits`, calculate Euclidean distances, and create a similarity matrix and graph.
* original data 

digits = load_digits()
X = digits.data / 16  # Normalize pixel values
y = digits.target  # True labels

dist = cdist(X, X, "euclidean")
n_neigh = 10  # Number of neighbors
S = np.zeros(dist.shape)
neigh_index = np.argsort(dist, axis=1)[:, 1:n_neigh+1]

for i in range(X.shape[0]):
    S[i, neigh_index[i]] = dist[i, neigh_index[i]]
S = np.maximum(S, S.T)

# Create graph
G_nx = nx.from_numpy_array(S)

2. Perform Clustering Methods: Execute clustering methods: Spectral Clustering, Louvain Method, and Walktrap Method.

* True labels

n_classes = len(np.unique(y))
cmap = plt.get_cmap('cool', n_classes)
pos = nx.spring_layout(G_nx, seed=42)
plt.title("True Labels", fontsize=32)
nx.draw(G_nx, pos, node_color=[cmap(label) for label in y], with_labels=False, node_size=40)
plt.show()

* Spectral Clustering

sc_model = SpectralClustering(n_clusters=10, affinity='precomputed', assign_labels='kmeans', random_state=42)
sc_model.fit(S)
pred_labels = sc_model.labels_
pred_labels=right_label(y,pred_labels)
mod = Modularity(G_nx, {i: label for i, label in enumerate(pred_labels)})
vi = compute_vi(y, pred_labels)
acc = np.mean(y == pred_labels)
print(f"Spectral Clustering - Modularity: {mod:.4f}, VI: {vi:.4f}, Accuracy: {acc:.4f}")
n_classes = len(np.unique(pred_labels))
plt.title("Spectral Clustering", fontsize=32)
nx.draw(G_nx, pos, node_color=[cmap(label) for label in pred_labels], with_labels=False, node_size=40)
plt.show()


Spectral Clustering - Modularity: 0.8385, VI: 0.9391, Accuracy: 0.8080

* Louvain Method

pred_partition = community_louvain.best_partition(G_nx)
pred_labels = [pred_partition[i] for i in range(len(pred_partition))]
pred_labels=right_label(y,pred_labels)
mod = Modularity(G_nx, pred_partition)
vi = compute_vi(y, pred_labels)
print(f"Louvain Method - Modularity: {mod:.4f}, VI: {vi:.4f}")
n_classes = len(np.unique(pred_labels))
plt.title("Louvain Method", fontsize=32)
nx.draw(G_nx, pos, node_color=[cmap(label) for label in pred_labels], with_labels=False, node_size=40)
plt.show()


Louvain Method - Modularity: 0.8597, VI: 0.5616

* Walktrap Method

pred_labels = walktrap(S, steps=5, num_clusters=10)
pred_labels=right_label(y,pred_labels)
mod = Modularity(G_nx, {i: label for i, label in enumerate(pred_labels)})
vi = compute_vi(y, pred_labels)
acc = np.mean(y == pred_labels)
print(f"Walktrap Method - Modularity: {mod:.4f}, VI: {vi:.4f}, Accuracy: {acc:.4f}")
n_classes = len(np.unique(pred_labels))
plt.title("Walktrap Method", fontsize=32)
nx.draw(G_nx, pos, node_color=[cmap(label) for label in pred_labels], with_labels=False, node_size=40)
plt.show()


Walktrap Method - Modularity: 0.8427, VI: 0.7040, Accuracy: 0.8737

#### Result
* Louvain Method achieved the highest modularity (0.8556) and the lowest VI (0.5616), indicating it produced the most accurate clustering in terms of label alignment, although it generated 11 clusters instead of the expected 10.
* Spectral Clustering had a modularity of 0.8385 and a higher VI of 0.9391, which indicates a less accurate alignment with the true labels compared to Louvain.
* Walktrap Method had a modularity of 0.8427 and a VI of 0.7040, performing similarly to Spectral Clustering in terms of modularity and label alignment.

### Clustering Persian Cats and Boxer Dogs
This example focuses on clustering two specific pet breeds — Persian cats and Boxer dogs — using advanced image processing and optimization techniques. The dataset for this study is sourced from the Kaggle'23 Pet Breeds Image Classification competition, which provides a rich collection of labeled images spanning multiple pet breeds.

The approach adopted here builds upon the methodology outlined in the study "Image Classification Using Singular Value Decomposition and Optimization." Singular Value Decomposition (SVD) is employed to extract meaningful features from image data, effectively reducing dimensionality while preserving essential structural information. By leveraging these compressed representations, the model aims to distinguish Persian cats from Boxer dogs with high accuracy.

#### Import Necessary Libraries

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
from scipy.stats import entropy
from community import community_louvain  
from sklearn.cluster import SpectralClustering
from scipy.spatial.distance import cdist
from scipy.cluster.hierarchy import linkage, fcluster
from scipy.spatial.distance import pdist
from skimage.color import rgb2gray
from skimage.transform import resize
from scipy.linalg import svd
from PIL import Image
import os

#### Loading and Preprocessing
The script prepares the data through the following steps:

* **Image Loading**: Images of Persian cats and Boxer dogs are loaded from specified directories.
* boxer dog
* persian cat
* **Preprocessing:** Each image is converted to grayscale, resized to a fixed size (512x512 pixels), cropped, normalized to [0, 1], and compressed using Singular Value Decomposition (SVD) to a rank-30 approximation for dimensionality reduction.

def preprocess_image(image, index=-1):
    """Preprocess an image: grayscale, resize, crop, and normalize."""
    if image.ndim != 3 or image.shape[2] != 3:
        raise ValueError(f"Input image at index {index} must be RGB. Shape: {image.shape}")

    gray_image = rgb2gray(image)
    resized_image = resize(gray_image, IMAGE_SIZE, anti_aliasing=True)
    cropped_image = resized_image[128:-128, 128:-128]
    normalized_image = cropped_image / 255.0

    U, S, Vt = svd(normalized_image, full_matrices=False)
    rank_k_approximation = np.dot(U[:, :RANK], np.dot(np.diag(S[:RANK]), Vt[:RANK, :]))
    return rank_k_approximation

def load_images_from_folder(folder_path):
    """Load and preprocess images from a folder."""
    images = []
    for filename in os.listdir(folder_path):
        if filename.endswith(('.png', '.jpg', '.jpeg')):
            image_path = os.path.join(folder_path, filename)
            image = np.array(Image.open(image_path))
            images.append(image)
    return images

# Load and preprocess data
persian_cat_images = load_images_from_folder(r"archive\Pet_Breeds\persian cat")
boxer_dog_images = load_images_from_folder(r"archive\Pet_Breeds\boxer")

persian_cat_images = np.array([preprocess_image(img) for img in persian_cat_images])
boxer_dog_images = np.array([preprocess_image(img) for img in boxer_dog_images])

X = np.concatenate([persian_cat_images, boxer_dog_images])
y = [0] * persian_cat_images.shape[0] + [1] * boxer_dog_images.shape[0]

X = X.reshape(X.shape[0], -1)
dist = cdist(X, X, "euclidean")


* Rank 30 have lowest VI



#### Main Functionality
* **Graph Construction:**
* A similarity graph is constructed using the pairwise Euclidean distances between feature vectors.
* A k-nearest neighbors approach is applied to retain only the most significant connections.
* **Clustering Methods:** The following methods are applied - Spectral Clustering, Louvain Method, and Walktrap Algorithm.
* **Metrics:** The following metrics are calculated:
* Modularity: Measures the quality of the graph partition.
* Variation of Information (VI): Quantifies the dissimilarity between the true labels and predicted labels.
* Accuracy: Measures how well the predicted labels match the true labels.

n_neigh = 10
S = np.zeros(dist.shape)
neigh_index = np.argsort(dist, axis=1)[:, 1:n_neigh+1]

for i in range(X.shape[0]):
    S[i, neigh_index[i]] = dist[i, neigh_index[i]]
S = np.maximum(S, S.T)

# The similarity matrix S represents the pairwise relationships between data points.
# It is influenced by the distances between points, emphasizing local neighborhoods.

# Create graph
G_nx = nx.from_numpy_array(S)

# # Visualization setup

n_classes = len(np.unique(y))
cmap = plt.get_cmap('cool', n_classes)
pos = nx.spring_layout(G_nx, seed=42)
plt.title("True Labels", fontsize=32)
nx.draw(G_nx, pos, node_color=[cmap(label) for label in y], with_labels=False, node_size=40)
plt.show()

# Spectral Clustering
param_grid = {
    'n_clusters': [num_clusters],
    'gamma': np.linspace(0.1, 1, 1),
    'assign_labels': ['kmeans', 'discretize']
}

best_params, best_model = best_sc_params(G_nx, param_grid)
best_model.fit(S)
pred_labels = best_model.labels_
pred_labels=right_label(y,pred_labels)
mod = Modularity(G_nx, {i: label for i, label in enumerate(pred_labels)})
vi = compute_vi(y, pred_labels)
acc = max(np.mean(y == pred_labels), np.mean(y == 1 - pred_labels))
print(f"Spectral Clustering - Modularity: {mod:.4f}, VI: {vi:.4f}, Accuracy: {acc:.4f}")

n_classes = len(np.unique(pred_labels))
plt.title("Spectral Clustering", fontsize=32)
nx.draw(G_nx, pos, node_color=[cmap(label) for label in pred_labels], with_labels=False, node_size=40)
plt.show()

# Louvain Method
pred_partition = community_louvain.best_partition(G_nx)
pred_labels = [pred_partition[i] for i in range(len(pred_partition))]
pred_labels=right_label(y,pred_labels)
mod = Modularity(G_nx, pred_partition)
vi = compute_vi(y, pred_labels)
#acc = max(np.mean(y == pred_labels), np.mean(y == 1 - pred_labels))
print(f"Louvain Method - Modularity: {mod:.4f}, VI: {vi:.4f}")

n_classes = len(np.unique(pred_labels))
cmap = plt.get_cmap('cool', n_classes)
plt.title("Louvain Method", fontsize=32)
nx.draw(G_nx, pos, node_color=[cmap(label) for label in pred_labels], with_labels=False, node_size=40)
plt.show()

# Walktrap
pred_labels = walktrap(S, steps=5, num_clusters=num_clusters)
pred_labels=right_label(y,pred_labels)
mod = Modularity(G_nx, {i: label for i, label in enumerate(pred_labels)})
vi = compute_vi(y, pred_labels)
acc = max(np.mean(y == pred_labels), np.mean(y == 1 - pred_labels))
print(f"Walktrap Method - Modularity: {mod:.4f}, VI: {vi:.4f}, Accuracy: {acc:.4f}")

n_classes = len(np.unique(pred_labels))
cmap = plt.get_cmap('cool', n_classes)
plt.title("Walktrap Method", fontsize=32)
nx.draw(G_nx, pos, node_color=[cmap(label) for label in pred_labels], with_labels=False, node_size=40)
plt.show()

Spectral Clustering - Modularity: 0.3200, VI: 1.6221, Accuracy: 0.6795
Louvain Method - Modularity: 0.5289, VI: 3.0027
Walktrap Method - Modularity: 0.2902, VI: 1.5876, Accuracy: 0.6528


#### Result
* Louvain Method had the best modularity (0.5068) but produced high VI (3.0604), indicating poor label alignment despite the high modularity.
* Spectral Clustering had a modularity of 0.3200 and a VI of 1.6221, balancing the modularity and label alignment reasonably well.
* Walktrap Method had the lowest modularity (0.2902) but a VI of 1.5876, slightly better than Louvain's VI, indicating better label alignment despite its lower modularity.

## Conclusion
This study examined the effectiveness of three graph partitioning methods — Louvain, Walktrap, and spectral clustering — in identifying communities within networks. Using modularity and Variation of Information (VI) as evaluation metrics, we analyzed the performance of these methods on both synthetic datasets and a real-world image dataset of Persian cats and Boxer dogs.

Our findings demonstrate that the Louvain method excels in achieving high modularity scores, indicating its ability to find strong community structures. However, it may not always align perfectly with predefined labels, as evidenced by the higher VI scores in some cases. Spectral clustering offers a balance between modularity and label alignment, while the Walktrap method, despite lower modularity, often shows better label agreement.

The choice of method depends on the specific application and the desired balance between modularity and label alignment. Graph partitioning remains a vital tool for understanding complex networks across diverse fields. It enables the identification of communities, facilitates efficient analysis, and reveals hidden relationships within data.

## References
* Lambiotte, R. (2020). C5.4 Networks Lecture Notes. Retrieved from https://courses.maths.ox.ac.uk/mod/resource/view.php?id=50765
* Yepes, I. M., & Goyal, M. (2024). Image Classification Using Singular Value Decomposition and Optimization. arXiv preprint arXiv:2412.07288.
* Meilă, M. (2007). Comparing clusterings—an information based distance. Journal of Multivariate Analysis