Is nx.eigenvector_centrality_numpy() using the Arnoldi iteration instead of the basic power method?

76 Views Asked by At

Since nx.eigenvector_centrality_numpy() using ARPACK, is it mean that nx.eigenvector_centrality_numpy() using Arnoldi iteration instead of the basic power method?

because when I try to compute manually using the basic power method, the result of my computation is different from the result of nx.eigenvector_centrality_numpy(). Can someone explain it to me?

To make it more clear, here is my code and the result that I got from the function and the result when I compute manually.

import networkx as nx

G = nx.DiGraph()

G.add_edge('a', 'b', weight=4)
G.add_edge('b', 'a', weight=2)
G.add_edge('b', 'c', weight=2)
G.add_edge('b','d', weight=2)
G.add_edge('c','b', weight=2)
G.add_edge('d','b', weight=2)

centrality = nx.eigenvector_centrality_numpy(G, weight='weight')
centrality

The result:

{'a': 0.37796447300922725,
 'b': 0.7559289460184545,
 'c': 0.3779644730092272,
 'd': 0.3779644730092272} 

Below is code from Power Method Python Program and I did a little bit of modification:

# Power Method to Find Largest Eigen Value and Eigen Vector
# Importing NumPy Library
import numpy as np
import sys

# Reading order of matrix
n = int(input('Enter order of matrix: '))

# Making numpy array of n x n size and initializing 
# to zero for storing matrix
a = np.zeros((n,n))

# Reading matrix
print('Enter Matrix Coefficients:')
for i in range(n):
    for j in range(n):
        a[i][j] = float(input( 'a['+str(i)+']['+ str(j)+']='))

# Making numpy array n x 1 size and initializing to zero
# for storing initial guess vector
x = np.zeros((n))

# Reading initial guess vector
print('Enter initial guess vector: ')
for i in range(n):
    x[i] = float(input( 'x['+str(i)+']='))

# Reading tolerable error
tolerable_error = float(input('Enter tolerable error: '))

# Reading maximum number of steps
max_iteration = int(input('Enter maximum number of steps: '))

# Power Method Implementation
lambda_old = 1.0
condition =  True
step = 1
while condition:
    # Multiplying a and x
    ax = np.matmul(a,x)
    
    # Finding new Eigen value and Eigen vector
    x = ax/np.linalg.norm(ax)
    
    lambda_new = np.vdot(ax,x)
    
    
    # Displaying Eigen value and Eigen Vector
    print('\nSTEP %d' %(step))
    print('----------')
    print('Eigen Value = %0.5f' %(lambda_new))
    print('Eigen Vector: ')
    for i in range(n):
        print('%0.5f\t' % (x[i]))
    
    # Checking maximum iteration
    step = step + 1
    if step > max_iteration:
        print('Not convergent in given maximum iteration!')
        break
    
    # Calculating error
    error = abs(lambda_new - lambda_old)
    print('errror='+ str(error))
    lambda_old = lambda_new
    condition = error > tolerable_error 

I used the same matrix and the result:

STEP 99
----------
Eigen Value = 3.70328
Eigen Vector: 
0.51640 
0.77460 
0.25820 
0.25820 
errror=0.6172133998483682

STEP 100
----------
Eigen Value = 4.32049
Eigen Vector: 
0.71714 
0.47809 
0.35857 
0.35857 
Not convergent in given maximum iteration!

I've to try to compute it with my calculator too and I know it's not convergent because |lambda1|=|lambda2|=4. I've to know the theory behind nx.eigenvector_centrality_numpy() properly so I can write it right for my thesis. Help me, please

0

There are 0 best solutions below