Katz Attenuation Radius Check

Problem

Check whether the Katz attenuation factor is small enough for the series to converge.

Estimate the largest eigenvalue of the symmetric adjacency matrix with 1000 power iterations starting from the all-ones vector and the Rayleigh quotient, then return True exactly when alpha * lambda_max < 1. edges is a list of [u, v] pairs with multiplicities collapsed into weights. An empty graph always returns True.

Hint

The Katz series converges when the attenuation times the spectral radius stays below one.

Test cases

case 1

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

expected: true

case 2

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

expected: false

case 3

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

expected: true

case 4

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

expected: false

case 5

in: [1,[],0.9]

expected: true

Starter codePython

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

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