Adjacency Normalization

Problem

Build the row-normalized adjacency matrix D^-1 A of an undirected graph with n nodes.

Each entry A[i][j] is divided by the degree of i, so every non-isolated node's outgoing weights sum to 1. Rows of isolated nodes are all zeros. edges is a list of [u, v] pairs. Return the n by n matrix of floats.

Hint

D^-1 A is the transition matrix of the simple random walk.

Test cases

case 1

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

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

case 2

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

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

case 3

in: [2,[]]

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

Starter codePython

def normalize_adjacency(n, edges):
    # Your code here
    pass

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