eigen_centrality for a directed graph (R)

Hi,

I am using the function eigen_centrality() applied to a weighted graph. In particular, being w the weighted adjacency matrix, the graph g is defined as: graph.adjacency(w,mode="directed",weighted=TRUE) .

Then, I have run the command below:

eigen_centrality(g)$vector

… my question is: what do I really get with this command? If I run eigen_centrality(g, directed = TRUE, weights = E(g)$weigh) , I obtain a different result.

Thank you

Can you show a complete but minimal example that demonstrates the difference?

Regarding how eigencentrality is computed in igraph, you will find some information here as well as in links within:

Consider the network with adjacency matrix n given by the following matrix:

n =\left( \begin{array}{ccccccccc} 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ \end{array} \right)

and consider the matrix w = n/rowSums((n)) . Now if
g = graph.adjacency(wnet,mode="directed",weighted=TRUE)
and you compute both eigen_centrality(g)$vector and eigen_centrality(g, directed = TRUE, weights = E(g)$weigh)$vector, you obtain different results.

I know which is the def. of eigenvector centrality, but I wanted to know what the function gives as result.

The default for the directed argument to eigen_centrality is FALSE, as you can see in the documentation. In the first call, hence directed=FALSE by default, while in the second call, you explicitly set directed=TRUE. The full reproducible example is below, showing that both calls produce identical results if you set directed=TRUE also in the first call.

library(igraph)

A = matrix(
    c(0, 1, 1, 1, 1, 1, 1, 0, 0,
      1, 0, 1, 1, 0, 0, 0, 0, 0,
      1, 1, 0, 0, 1, 0, 0, 0, 0,
      1, 1, 0, 0, 0, 1, 0, 0, 0,
      1, 0, 1, 0, 0, 0, 0, 1, 0,
      1, 0, 0, 1, 0, 0, 0, 0, 0,
      1, 0, 0, 0, 0, 0, 0, 0, 1,
      0, 0, 0, 0, 1, 0, 0, 0, 1,
      0, 0, 0, 0, 0, 0, 1, 1, 0),
    nrow=9, ncol=9)

w = A/rowSums((A))
g = graph.adjacency(w,mode="directed",weighted=TRUE)

v1 = eigen_centrality(g, directed = TRUE)$vector
v2 = eigen_centrality(g, directed = TRUE, weights = E(g)$weigh)$vector
print(v1)
print(v2)

output:

> print(v1)
[1] 1.0000000 0.5000000 0.5000000 0.5000000 0.5000000 0.3333333 0.3333333
[8] 0.3333333 0.3333333
> print(v2)
[1] 1.0000000 0.5000000 0.5000000 0.5000000 0.5000000 0.3333333 0.3333333
[8] 0.3333333 0.3333333

Thank you for the reply. So the result of the call eigen_centrality(g, directed = TRUE, weights = E(g)$weigh)$vector takes the weights from the graph.
And what about the results of eigen_centrality(g)$vector? Since the default for the directed argument to eigen_centrality is FALSE, it would return the same of eigen_centrality(graph.adjacency(adj, mode = "undirected"), directed = TRUE)$vector. Actually it doesn’t. Where am I wrong?

Yes, both eigen_centrality(g, weights = E(g)$weight) and eigen_centrality(g) use the weights that are provided in the graph. Note that this is only the case if the weights are in the edge attribute named weight.

Please note that graph.adjacency(adj, mode = "undirected") uses what is the same as mode="max", meaning that it will take as undirected edge weight the maximum of the two entries adj[i, j] and adj[j, i]. The unnormalised adjacency matrix A that you included is symmetric, so then this does not matter much. If you are using the normalised adjacency matrix w this does matter of course, since it is no longer symmetric.

However, even then, creating an undirected graph is not the same as creating a directed graph and then treating is as undirected when calculating eigen_centrality. Treating a directed graph as undirected in eigen_centrality implies that it ignores the direction of the edges. Since edges are directed, there are two edges between each connected pair of nodes for the adjacency matrix you used, both of which have a different weight. Hence, this is different from creating an undirected graph from the start, which will have only one edge, with a different weight.

Concretely, if you do

g = graph.adjacency(w,mode="directed",weighted=TRUE)

you will see ecount(g) returning 26, while if you do

g = graph.adjacency(w,mode="undirected",weighted=TRUE)

you will see ecount(g) returning 13.

So the results are different because are different the two graphs:

g1 = graph.adjacency(w,mode=“directed”,weighted=TRUE)
g2 = graph.adjacency(w,mode=“undirected”,weighted=TRUE)

From the computational point of view, since the eigen_centrality computes the eigenvector corresponding to the largest eigenvalue of the “adjacency” matrix of the graph, in these two different cases, what is taken as “adjacency matrix”? In other terms, why would they differ?
Thank you again

The adjacency matrix of the two graphs are also different. You can check that yourself:

get.adjacency(g1, attr = 'weight')

yields

9 x 9 sparse Matrix of class "dgCMatrix"
                                                                                         
 [1,] .         0.1666667 0.1666667 0.1666667 0.1666667 0.1666667 0.1666667 .         .  
 [2,] 0.3333333 .         0.3333333 0.3333333 .         .         .         .         .  
 [3,] 0.3333333 0.3333333 .         .         0.3333333 .         .         .         .  
 [4,] 0.3333333 0.3333333 .         .         .         0.3333333 .         .         .  
 [5,] 0.3333333 .         0.3333333 .         .         .         .         0.3333333 .  
 [6,] 0.5000000 .         .         0.5000000 .         .         .         .         .  
 [7,] 0.5000000 .         .         .         .         .         .         .         0.5
 [8,] .         .         .         .         0.5000000 .         .         .         0.5
 [9,] .         .         .         .         .         .         0.5000000 0.5000000 .  

while

get.adjacency(g2, attr = 'weight')

yields

9 x 9 sparse Matrix of class "dgCMatrix"
                                                                       
 [1,] .         0.3333333 0.3333333 0.3333333 0.3333333 0.5 0.5 .   .  
 [2,] 0.3333333 .         0.3333333 0.3333333 .         .   .   .   .  
 [3,] 0.3333333 0.3333333 .         .         0.3333333 .   .   .   .  
 [4,] 0.3333333 0.3333333 .         .         .         0.5 .   .   .  
 [5,] 0.3333333 .         0.3333333 .         .         .   .   0.5 .  
 [6,] 0.5000000 .         .         0.5000000 .         .   .   .   .  
 [7,] 0.5000000 .         .         .         .         .   .   .   0.5
 [8,] .         .         .         .         0.5000000 .   .   .   0.5
 [9,] .         .         .         .         .         .   0.5 0.5 .  

Since you’re working with directed graphs, just a word of warning: eigenvector centrality is not really ideal for directed graphs, primarily because most real-world directed networks are not (strongly) connected.

Consider if hub/authority scores, or perhaps PageRank, are a better fit for your application.

1 Like

Thank you again.
It comes out what you were saying, i.e. get.adjacency(g1, attr = 'weight') gives exatly w (except for the sparse/normal matrix), while get.adjacency(g2, attr = 'weight') gives as (i,j)-th entry \max \left\{w_{ij},w_{ji}\right\}.

Thank you

1 Like

@szhorvat thank you for maintaining igraph and answering questions.

The function eigen_centrality contains a

WARNING: eigen_centrality will not symmetrize your data before extracting eigenvectors; don’t send this routine asymmetric matrices unless you really mean to do so.

Your warning above about being unsuitable for real-world graphs reads important. Should it be added to the manual (page 159)?

Thanks

@astruck Can you please give us a short example that triggers this warning? I’m not quite sure where this may be coming from. Which version of igraph are you using?

I’m referring to the igraph manual, published 2022-07-19 for igraph v1.3.4. I do not have triggered the warning mentioned in the manual. Your warning here in this thread about being unsuitable for weakly connected graphs reads important enough to be included in the manual?

1 Like

I just realized that. Thanks for the clarification. This warning is inaccurate and outdated, so I will remove it. Actually, edge directions are ignored by default in the R interface (see the default of directed = FALSE).

I’ll include a note about disconnected graphs.

Thanks for the feedback. Please let us know if you come across anything else that looks fishy. We are aware that the R/igraph documentation could use some editing, but we are short of hands (and short of R experts as well).