Laplacian Normalization

Problem

Build the symmetric normalized Laplacian L_sym = I - D^-1/2 A D^-1/2 of an undirected graph with n nodes.

The diagonal is 1 for non-isolated nodes and 0 for isolated ones; off-diagonal entry (i, j) is -1 / sqrt(deg(i) * deg(j)) for every edge. edges is a list of [u, v] pairs.

Hint

The normalized Laplacian eigenvalues always lie between 0 and 2.

Test cases

case 1

in: [3,[[0,1],[1,2]]]

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

case 2

in: [3,[[0,1],[1,2],[2,0]]]

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

case 3

in: [2,[]]

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

Starter codePython

import math
def normalized_laplacian(n, edges):
    # Your code here
    pass

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