Graph Clustering Toolkit

A collection of MATLAB/Octave implementations of graph clustering algorithms, with emphasis on spectral methods, dynamical systems (Kuramoto model), and signed/weighted networks.

Author: Keivan Hassani Monfared (k1monfared@gmail.com)

Methods Overview

This repository implements five distinct approaches to graph (network) clustering:

Method	Type	Supports Signed Graphs	Key Idea
Hierarchical Fiedler	Spectral	Via positive part	Recursive bisection using Fiedler eigenvector
Generalized Fiedler	Spectral	Via positive part	Multi-eigenvector sign-pattern partitioning
Spectral Coordinates	Spectral	Yes	K-means on eigenvector embeddings on the unit sphere
Kuramoto Model	Dynamical	Yes	Phase synchronization of coupled oscillators
Simulated Annealing	Optimization	Yes	Stochastic optimization of signed modularity

Additionally, the Newman-Girvan method based on edge betweenness centrality is included.

---

1. Hierarchical Fiedler Clustering

Location: iterative_vs_generalized_fiedler_clustering/ and matlab_octave_graph_routines/

The Fiedler vector is the eigenvector corresponding to the second-smallest eigenvalue (algebraic connectivity) of the graph Laplacian L = D - A. The signs of its entries naturally bipartition the graph.

Algorithm:

1. Compute the Laplacian L = D - A (uses L + I to avoid zero-eigenvalue numerical issues)
2. Find the Fiedler vector (2nd eigenvector)
3. Partition vertices into two groups based on the sign of the Fiedler vector
4. Recursively split the cluster with the lowest normalized algebraic connectivity
5. Track Girvan-Newman modularity at each step to find the optimal number of clusters

A = random_multi_bottleneck_graph([20, 15, 25], [.9 .1 .1; .1 .85 .2; .1 .2 .9]);
[idx_history, Q_history] = hierarchical_partition_with_fiedler(A, 4);
[~, best_k] = max(Q_history);

2. Generalized Fiedler Clustering

Location: iterative_vs_generalized_fiedler_clustering/

Instead of recursively bisecting, this method uses multiple eigenvectors simultaneously:

1. Compute the first k eigenvectors of the Laplacian (k <= ceil(log2(n)))
2. Form a binary sign-pattern vector for each vertex from eigenvectors 2 through k
3. Convert sign patterns to cluster IDs via binary-to-decimal conversion

The iterative method generally outperforms the generalized method, especially when cluster sizes are unequal:

idx = generalized_partition_with_fiedler(A, ceil(log2(4)) + 1);

3. Spectral Coordinates Clustering

Location: matlab_octave_graph_routines/

Based on Wu et al. (2017), this method maps vertices to points on the unit sphere using the largest eigenvectors of the adjacency matrix (not the Laplacian). This naturally supports signed graphs.

Algorithm:

1. Compute the k largest eigenvectors of A
2. For each vertex, form a coordinate vector from the corresponding eigenvector entries
3. Normalize each coordinate vector to lie on the unit sphere
4. Apply k-means clustering in this spectral embedding space
5. Select k that maximizes signed Girvan-Newman modularity

[idx, q, sumd] = best_cluster_with_spectral_coordinates(A);

4. Kuramoto Model Clustering

Location: kuramoto_clustering/ and network_clustering_octave_matlab/

This physics-inspired method treats each vertex as a coupled phase oscillator. The Kuramoto dynamics are:

d(theta_i)/dt = omega_i + (coupling/N) * sum_j A_ij * sin(theta_j - theta_i)

Oscillators in the same community synchronize their phases, while those in different communities settle at different angles. The final phases are clustered using k-means on polar coordinates.

Pipeline: Random initialization -> ODE integration (ode45) -> Convergence check -> Canonical form -> K-means on (cos, sin) -> Elbow method for k selection

run_kuramoto_cluster(A)  % All-in-one with visualization

5. Simulated Annealing on Modularity

Location: matlab_octave_graph_routines/ and network_clustering_octave_matlab/

Uses the Metropolis-Hastings algorithm (Kirkpatrick et al., 1983) to directly maximize the signed Girvan-Newman modularity:

Q = (w+ * Q+ - w- * Q-) / (w+ + w-)

where Q+ and Q- are the modularities of the positive and negative subgraphs, weighted by their respective total edge weights w+ and w-.

[idx, q] = best_cluster_with_SA_sQ(A);

Declustering

Location: declustering/

A post-processing technique for hierarchical clustering. When recursive bisection separates subclusters that actually belong together, declustering identifies and merges them to improve modularity.

Newman-Girvan Edge Betweenness

Location: matlab_octave_graph_routines/

The classic community detection algorithm (Newman & Girvan, 2004):

1. Compute edge betweenness centrality for all edges
2. Remove the edge with highest betweenness
3. Repeat until the graph splits into the desired number of components

[idx, q] = best_cluster_with_girvan_newman(A);

---

Graph Generation

All projects use random_multi_bottleneck_graph.m to create test graphs with known community structure:

N = [20, 15, 25];          % cluster sizes
P = [.90, .10, .10;        % edge probability matrix
     .10, .85, .20;        % P(i,j) = prob of edge between clusters i and j
     .10, .20, .90];
A = random_multi_bottleneck_graph(N, P);                          % simple graph
A = random_multi_bottleneck_graph(N, P, 'weighted', true);        % weighted
A = random_multi_bottleneck_graph(N, P, 'weighted', true, 'Signed', 0.3);  % signed

Quality Metrics

Signed Girvan-Newman Modularity

The modularity Q is computed as:

Q = trace(E) - ||E^2||

where E_ij is the fraction of edges between communities i and j. For signed graphs, the positive and negative parts are handled separately and combined as a weighted sum.

Adjusted Rand Index (ARI)

Used to compare a found clustering against the ground truth, accounting for chance agreement.

---

Repository Structure

clustering/
|-- README.md                                    # This file
|-- images/                                      # Generated visualizations
|-- declustering/                                # Declustering post-processing
|   |-- numerical_example.m                      # Main demo script
|   |-- declustering.pdf                         # Mathematical explanation
|-- iterative_vs_generalized_fiedler_clustering/ # Fiedler method comparison
|   |-- partition_with_fiedler.m                 # Core Fiedler bipartition
|   |-- hierarchical_partition_with_fiedler.m    # Iterative hierarchical method
|   |-- generalized_partition_with_fiedler.m     # Multi-eigenvector method
|   |-- compare_*.m                              # Comparison experiment scripts
|-- kuramoto_clustering/                         # Kuramoto dynamical clustering
|   |-- Kuramoto_stable.m                        # Kuramoto ODE solver
|   |-- run_kuramoto_cluster.m                   # All-in-one pipeline
|   |-- example.m                                # Worked example
|-- matlab_octave_graph_routines/                # Core graph library
|   |-- spectral_coordinate.m                    # Spectral coordinates method
|   |-- best_cluster_with_*.m                    # Best clustering wrappers
|   |-- simulated_annealing_max.m                # SA optimizer
|   |-- random_multi_bottleneck_graph.m          # Graph generator
|-- network_clustering_octave_matlab/            # Unified comparison framework
|   |-- all_cluster.m                            # Compare all methods
|   |-- Method*.m                                # Individual method wrappers
|   |-- cluster_signals.m                        # Signal-based clustering pipeline

Requirements

• MATLAB R2016a or later (or GNU Octave 4.0+)
• No additional toolboxes required (Statistics Toolbox optional for kmeans)

References

1. M. Fiedler, "Algebraic connectivity of Graphs", Czechoslovak Mathematical Journal 23(98), 298-305, 1973.
2. M.E.J. Newman, M. Girvan, "Finding and evaluating community structure in networks", Phys. Rev. E 69, 026113, 2004.
3. L. Wu, X. Wu, A. Lu, Y. Li, "On Spectral Analysis of Signed and Dispute Graphs: Application to Community Structure", IEEE TKDE 29(7), 1480-1493, 2017.
4. S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi, "Optimization by Simulated Annealing", Science 220, 671-680, 1983.
5. K. Hassani Monfared et al., "Community structure detection and evaluation during the pre- and post-ictal hippocampal depth recordings", arXiv:1804.01568.

License

See the LICENSE file in each subdirectory (GPL v3).