Search code examples
pythonnetworkxgraph-theoryigrapheigenvector

Difference between NetworkX and iGraph calculation of eigenvector centrality

I am trying to calculate the eigenvector centrality for nodes in a graph

Both packages iGraph and NetworkX have methods to calculate eigenvector centrality, but they are returning different values for the same graph

import igraph as ig
import networkx as nx
import numpy as np

count_crossing = np.loadtxt("some_weight_adjacency_matrix")

#%% iGraph

Gig = ig.Graph.Weighted_Adjacency(count_crossing, mode = 'directed')
Gig_centrality = Gig.evcent(directed = True, weights='weight')  #same as G_ig.eigenvector_centrality

#%% NetworkX

Gnx = nx.DiGraph(count_crossing)
Gnx_centrality = nx.eigenvector_centrality(Gnx, max_iter=500, weight = 'weight')

Both methods return a list of eigenvector centralities for each node in the graph, but the values are not equal. The returned values from the iGraph centrality calculation are roughly twice that of the NetworkX centrality calculation, but not exactly. Both functions are running on graphs generated from the same adjacency matrix; any ideas on why they produce such different values would be much appreciated! Thanks

Solution

  • The specific choices igraph makes when calculating eigenvector centrality are documented here:

    Typical causes of differences between packages are:

    • The handling of self-loops in undirected graphs: igraph consistently counts each self-loop twice on the diagonal of the adjacency matrix A. This is mathematically convenient and consistent, e.g. it ensures that \sum_i A_ij gives twice the degree of vertex j. However, not all network analysis packages are careful about this choice.
    • Sometimes the leading eigenvalue of the adjacency matrix is degenerate, meaning that the eigenvector centrality is not uniquely defined. To avoid this, make sure that your graph is connected. Eigenvector centrality is not meaningful for disconnected graphs.
    • Eigenvector centrality was developed for undirected graphs. While it can be generalized to directed graphs, problems (such as the solution not being unique) are much more likely. If you are applying the function to directed graphs (as you appear to be), make sure you know what you are doing! Ideally, use only strongly connected graphs.
    • In the directed case, igraph computes the left eigenvector. In other words, the centrality of a vertex is proportional to the sum of centralities of vertices pointing to it. Does NetworkX do the same?

    The returned values from the iGraph centrality calculation are roughly twice that of the NetworkX centrality calculation

    Eigenvector centralities are just the leading eigenvector of the adjacency matrix. Eigenvectors are unique only up to a multiplication by a scalar. Thus the magnitude of eigenvector centrality scores is meaningless in isolation. It only makes sense to compare the scores of two different vertices in the same graph.

    but not exactly

    If you have concerns about the correctness of the result, you can always verify it by multiplying the eigenvector by the adjacency matrix, and see if you get the same vector (times some scalar) back.

    I believe NetworkX uses power iteration to compute eigenvector centrality, and limits the maximum number of steps. It may not have converged to the desired accuracy. igraph uses ARPACK.