Eigenvector Power Iteration Count

Problem

Count how many power iterations eigenvector centrality needs to converge.

Start from the unit all-ones vector, multiply by (A + I) each round and renormalize to unit length, stopping when the largest component change is at most tolerance. Use the +I shift so bipartite graphs still converge. edges is a list of [u, v] pairs. Return the number of iterations performed, capped at 10000.

Hint

The shift adds one to every adjacency eigenvalue and keeps the iteration away from period two.

Test cases

case 1

in: [3,[[0,1],[1,2]],1e-7]

expected: 10

case 2

in: [4,[[0,1],[0,2],[0,3]],1e-7]

expected: 13

case 3

in: [2,[[0,1]],1e-7]

expected: 1

case 4

in: [1,[],1e-7]

expected: 1

Starter codePython

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

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