Spectral Graph Structure Analysis (C++)

This project implements a C++ pipeline for analyzing the structure of large sparse graphs using spectral methods and sparse linear algebra. The focus is on scalability, performance measurement, and structural interpretation rather than visualization or machine learning.

Overview

Given a random geometric graph, the code:

• Constructs a sparse normalized graph Laplacian
• Computes the smallest Laplacian eigenpairs using an iterative eigensolver
• Builds a 2D spectral embedding from nontrivial eigenvectors
• Analyzes graph structure using connectivity, spectral partitioning, and topological heuristics
• Measures runtime scaling of major computational phases

The implementation emphasizes sparse data structures, iterative algorithms, and empirical performance analysis.

Methods

• Graph construction: ε-neighborhood random geometric graph in ℝ²
• Linear algebra: Sparse normalized Laplacian
• Eigenvalue solver: Iterative method via Spectra (Lanczos-type)
• Spectral embedding: Fiedler vector and second nontrivial eigenvector
• Structural analysis:
  • Connected components
  • Fiedler cut edge count
  • Angular “loopiness” heuristic for nonlocal structure
• Performance analysis:
  • Graph construction time
  • Laplacian construction time
  • Eigenvalue solve time

Build Instructions

Dependencies

• C++17 compiler
• Eigen (header-only)
• Spectra (header-only)

Build

mkdir build
cd build
cmake ..
make -j
# Spectral Graph Structure Analysis (C++)

This project implements a C++ pipeline for analyzing the structure of large sparse graphs using spectral methods and sparse linear algebra. The focus is on scalability, performance measurement, and structural interpretation rather than visualization or machine learning.

## Overview

Given a random geometric graph, the code:
- Constructs a sparse normalized graph Laplacian
- Computes the smallest Laplacian eigenpairs using an iterative eigensolver
- Builds a 2D spectral embedding from nontrivial eigenvectors
- Analyzes graph structure using connectivity, spectral partitioning, and topological heuristics
- Measures runtime scaling of major computational phases

The implementation emphasizes sparse data structures, iterative algorithms, and empirical performance analysis.

## Methods

- **Graph construction**: ε-neighborhood random geometric graph in ℝ²
- **Linear algebra**: Sparse normalized Laplacian
- **Eigenvalue solver**: Iterative method via Spectra (Lanczos-type)
- **Spectral embedding**: Fiedler vector and second nontrivial eigenvector
- **Structural analysis**:
  - Connected components
  - Fiedler cut edge count
  - Angular “loopiness” heuristic for nonlocal structure
- **Performance analysis**:
  - Graph construction time
  - Laplacian construction time
  - Eigenvalue solve time

## Build Instructions

### Dependencies
- C++17 compiler
- Eigen (header-only)
- Spectra (header-only)

### Build
```bash
mkdir build
cd build
cmake ..
make -j
./spectral