Skip to content

cds2.spectral

Spectral graph theory - Laplacians, Fiedler vectors, algebraic connectivity and spectral clustering.

Spectral graph theory: Laplacians, Fiedler vectors, spectral clustering.

laplacian(adj, normalized=False)

Graph Laplacian L = D - W (combinatorial or symmetric-normalized).

Source code in src/cds2/spectral.py 
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def laplacian(adj: object, normalized: bool = False) -> sparse.csr_matrix:
    """Graph Laplacian ``L = D - W`` (combinatorial or symmetric-normalized)."""
    # Degree is the weighted degree (row sum of W), not the binary degree
    # (count of neighbours). Using the binary degree made L = D_binary - W
    # and rows summed to -8 instead of 0 on [[0,9,1],[9,0,0],[1,0,0]].
    matrix = sparse.coo_matrix(adj).tocsr()
    degree = np.asarray(matrix.sum(axis=1)).ravel().astype(float)
    degree_matrix = sparse.diags(degree)
    combinatorial = (degree_matrix - matrix).tocsr()
    if not normalized:
        return combinatorial
    inverse_sqrt = 1.0 / np.sqrt(np.where(degree == 0.0, 1.0, degree))
    scaling = sparse.diags(inverse_sqrt)
    return (scaling @ combinatorial @ scaling).tocsr()

fiedler_vector(adj)

Eigenvector of the second-smallest Laplacian eigenvalue.

Sign encodes the best bipartition; smoothness over the graph makes it a canonical 1-D embedding.

Source code in src/cds2/spectral.py 
52
53
54
55
56
57
58
59
60
61
62
63
64
def fiedler_vector(adj: object) -> FloatArray:
    """Eigenvector of the second-smallest Laplacian eigenvalue.

    Sign encodes the best bipartition; smoothness over the graph makes it a
    canonical 1-D embedding.
    """
    laplacian_matrix = laplacian(adj)
    n = laplacian_matrix.shape[0]
    if n < 3:
        msg = "Fiedler vector needs at least 3 nodes"
        raise ValueError(msg)
    _values, vectors = _bottom_eigenvectors(laplacian_matrix, k=2)
    return vectors[:, 1]

algebraic_connectivity(adj)

Second-smallest Laplacian eigenvalue - global connectivity measure.

Source code in src/cds2/spectral.py 
67
68
69
70
71
72
73
74
75
def algebraic_connectivity(adj: object) -> float:
    """Second-smallest Laplacian eigenvalue - global connectivity measure."""
    laplacian_matrix = laplacian(adj)
    n = laplacian_matrix.shape[0]
    if n < 2:
        msg = "algebraic connectivity needs at least 2 nodes"
        raise ValueError(msg)
    values, _vectors = _bottom_eigenvectors(laplacian_matrix, k=2)
    return float(max(values[1], 0.0))

spectral_cluster(adj, n_clusters, seed=None, normalized=True)

Cluster graph nodes by k-means on the bottom Laplacian eigenvectors.

Source code in src/cds2/spectral.py 
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
def spectral_cluster(
    adj: object,
    n_clusters: int,
    seed: int | None = None,
    normalized: bool = True,
) -> NDArray[np.int64]:
    """Cluster graph nodes by k-means on the bottom Laplacian eigenvectors."""
    laplacian_matrix = laplacian(adj, normalized=normalized)
    n = laplacian_matrix.shape[0]
    if not 1 <= n_clusters <= n:
        msg = "n_clusters must be between 1 and the number of nodes"
        raise ValueError(msg)
    _values, embedding = _bottom_eigenvectors(laplacian_matrix, k=n_clusters)
    row_norms = np.linalg.norm(embedding, axis=1, keepdims=True)
    unit_embedding = embedding / np.where(row_norms == 0.0, 1.0, row_norms)
    clusterer = KMeans(n_clusters=n_clusters, seed=seed).fit(unit_embedding)
    labels = clusterer.labels_
    assert labels is not None
    return labels