Eigenvector Centrality (Power Iteration)

Problem

Compute the eigenvector centrality of an undirected graph with power iteration.

Start with all ones. Each round multiply by (A + I) where A is the adjacency matrix, then normalize to unit length. This shift guarantees convergence on bipartite graphs. Stop when the largest component change is at most tolerance, and return the unit vector.

Hint

Adding the identity keeps the Perron eigenvalue strictly dominant even for bipartite graphs.

Test cases

case 1

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

expected: [0.5,0.7071067811865476,0.5]

case 2

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

expected: [0.7071067811865476,0.4082482904638631,0.4082482904638631,0.4082482904638631]

case 3

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

expected: [0.7071067811865476,0.7071067811865476]

case 4

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

expected: [1]

Starter codePython

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

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