graphs.lanczos_eigenvectors

Lanczos Method for Finding Eigenvalues and Eigenvectors of a Graph.

This module demonstrates the Lanczos method to approximate the largest eigenvalues and corresponding eigenvectors of a symmetric matrix represented as a graph’s adjacency list. The method efficiently handles large, sparse matrices by converting the graph to a tridiagonal matrix, whose eigenvalues and eigenvectors are then computed.

Key Functions: - find_lanczos_eigenvectors: Computes the k largest eigenvalues and vectors. - lanczos_iteration: Constructs the tridiagonal matrix and orthonormal basis vectors. - multiply_matrix_vector: Multiplies an adjacency list graph with a vector.

Complexity: - Time: O(k * n), where k is the number of eigenvalues and n is the matrix size. - Space: O(n), due to sparse representation and tridiagonal matrix structure.

Further Reading: - Lanczos Algorithm: https://en.wikipedia.org/wiki/Lanczos_algorithm - Eigenvector Centrality: https://en.wikipedia.org/wiki/Eigenvector_centrality

Example Usage: Given a graph represented by an adjacency list, the find_lanczos_eigenvectors function returns the largest eigenvalues and eigenvectors. This can be used to analyze graph centrality.

Functions

find_lanczos_eigenvectors(→ tuple[numpy.ndarray, ...)	Computes the largest eigenvalues and their corresponding eigenvectors using the
lanczos_iteration(→ tuple[numpy.ndarray, numpy.ndarray])	Constructs the tridiagonal matrix and orthonormal basis vectors using the
main(→ None)	Main driver function for testing the implementation with doctests.
multiply_matrix_vector(→ numpy.ndarray)	Performs multiplication of a graph's adjacency list representation with a vector.
validate_adjacency_list(→ None)	Validates the adjacency list format for the graph.

Module Contents

graphs.lanczos_eigenvectors.find_lanczos_eigenvectors(graph: list[list[int | None]], num_eigenvectors: int) → tuple[numpy.ndarray, numpy.ndarray]

Computes the largest eigenvalues and their corresponding eigenvectors using the Lanczos method.

Args:

graph: The graph as a list of adjacency lists. num_eigenvectors: Number of largest eigenvalues and eigenvectors to compute.

Returns:

A tuple containing:

• eigenvalues: 1D array of the largest eigenvalues in descending order.

• eigenvectors: 2D array where each column is an eigenvector corresponding

  to an eigenvalue.

Raises:

ValueError: If the graph format is invalid or num_eigenvectors is out of bounds.

>>> eigenvalues, eigenvectors = find_lanczos_eigenvectors(
...     [[1, 2], [0, 2], [0, 1]], 2
... )
>>> len(eigenvalues) == 2 and eigenvectors.shape[1] == 2
True

graphs.lanczos_eigenvectors.lanczos_iteration(graph: list[list[int | None]], num_eigenvectors: int) → tuple[numpy.ndarray, numpy.ndarray]

Constructs the tridiagonal matrix and orthonormal basis vectors using the Lanczos method.

Args:

graph: The graph represented as a list of adjacency lists. num_eigenvectors: The number of largest eigenvalues and eigenvectors

to approximate.

Returns:

A tuple containing:

• tridiagonal_matrix: A (num_eigenvectors x num_eigenvectors) symmetric

  matrix.

• orthonormal_basis: A (num_nodes x num_eigenvectors) matrix of orthonormal

  basis vectors.

Raises:

ValueError: If num_eigenvectors is less than 1 or greater than the number of

nodes.

>>> graph = [[1, 2], [0, 2], [0, 1]]
>>> T, Q = lanczos_iteration(graph, 2)
>>> T.shape == (2, 2) and Q.shape == (3, 2)
True

graphs.lanczos_eigenvectors.main() → None

Main driver function for testing the implementation with doctests.

graphs.lanczos_eigenvectors.multiply_matrix_vector(graph: list[list[int | None]], vector: numpy.ndarray) → numpy.ndarray

Performs multiplication of a graph’s adjacency list representation with a vector.

Args:

graph: The adjacency list of the graph. vector: A 1D numpy array representing the vector to multiply.

Returns:

A numpy array representing the product of the adjacency list and the vector.

Raises:

ValueError: If the vector’s length does not match the number of nodes in the

graph.

>>> multiply_matrix_vector([[1, 2], [0, 2], [0, 1]], np.array([1, 1, 1]))
array([2., 2., 2.])
>>> multiply_matrix_vector([[1, 2], [0, 2], [0, 1]], np.array([0, 1, 0]))
array([1., 0., 1.])

graphs.lanczos_eigenvectors.validate_adjacency_list(graph: list[list[int | None]]) → None

Validates the adjacency list format for the graph.

Args:

graph: A list of lists where each sublist contains the neighbors of a node.

Raises:

ValueError: If the graph is not a list of lists, or if any node has

invalid neighbors (e.g., out-of-range or non-integer values).

>>> validate_adjacency_list([[1, 2], [0], [0, 1]])
>>> validate_adjacency_list([[]])  # No neighbors, valid case
>>> validate_adjacency_list([[1], [2], [-1]])  # Invalid neighbor
Traceback (most recent call last):
    ...
ValueError: Invalid neighbor -1 in node 2 adjacency list.