Hypergraph Laplacian Build

Problem

Build the normalized hypergraph Laplacian L = D_v - H D_e^-1 H^T with unit hyperedge weights.

H is the incidence matrix, D_v holds node degrees, and D_e holds hyperedge sizes. Two nodes in the same hyperedge of size s contribute -1/s off-diagonal, and every incidence adds 1 to the diagonal. hyperedges is a list of vertex lists. Return the n by n float matrix.

Hint

Dividing by the hyperedge size makes larger hyperedges contribute weaker pairwise couplings.

Test cases

case 1

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

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

case 2

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

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

case 3

in: [2,[]]

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

Starter codePython

def hypergraph_laplacian(n, hyperedges):
    # Your code here
    pass

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