Normalized Graph Laplacian

Problem

Build the symmetric normalized Laplacian of an undirected graph with adjacency matrix A:

L = I - D^(-1/2) * A * D^(-1/2)

where D is the degree matrix. Isolated vertices (degree 0) contribute a zero row and column.

Hint

The normalized Laplacian has eigenvalues in [0, 2] and is scale-invariant.

case 1

in: [[[0,1],[1,0]]]

expected: [[1,-1],[-1,1]]

case 2

in: [[[0,1,0],[1,0,1],[0,1,0]]]

expected: [[1,-0.7071067811865475,0],[-0.7071067811865475,1,-0.7071067811865475],[0,-0.7071067811865475,1]]

case 3

in: [[[0,0],[0,0]]]

expected: [[0,0],[0,0]]

case 4

in: [[[0,1,0],[1,0,0],[0,0,0]]]

expected: [[1,-1,0],[-1,1,0],[0,0,0]]

Starter codePython

def normalized_laplacian(A):
    # Your code here
    pass

4 test cases · run your code against them in the editor