Katz Centrality

Problem

Compute Katz centrality for a directed graph with n nodes: c = beta * (I - alpha * A_transpose)^(-1) * 1, where A is the adjacency matrix and alpha is small enough for the inverse to exist.

Solve the linear system (I - alpha * A_transpose) c = beta * 1 with Gaussian elimination. edges is a list of [u, v] pairs; return the centrality vector.

Hint

A_transpose sends attention backwards along the edges, so incoming neighbors boost a node.

Test cases

case 1

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

expected: [1,1.1]

case 2

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

expected: [1,1.1,1.11]

case 3

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

expected: [1.0526315789473684,1.0526315789473684,1.0526315789473684]

case 4

in: [1,[],0.5,2]

expected: [2]

Starter codePython

def katz_centrality(n, edges, alpha, beta):
    # Your code here
    pass

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