Edge cases in eigenvector centralities

igraph_eigenvector_centrality has two special cases: it returns all-ones for graphs with no edges or graphs with all-zero weights.

I propose changing this to return all-zeros instead. Reasoning:

  • In undirected graphs, isolated vertices have centrality 0. In a graph with no edges, all vertices are isolated.
  • In directed graphs with no cycles, 0 is returned for all vertices.
  • Currently, if the leading eigenvalue is 0, all-zeros are returned. I can see this in the code. However, I cannot see how the eigenvalue could be zero in the undirected case, unless the graph has no edges (a special case which is caught early). I assume this can only occur due to roundoff errors.
  • A common (though not very sophisticated) method to compute eigenvector centralities is to repeatedly multiply by the adjacency matrix and normalize. This would give all-zeros.

I am wondering if I am missing any reasons why it is a good idea to return all-ones. Of course, all-ones are not technically wrong. If the graph has no edges, the adjacency matrix contains all zeros, so any vector is an eigenvector.

@Gabor I think you implemented this. Do you recall why you chose to return all-ones?

Does anyone else see a reasons why not to change to all-zeros?

This was a long time ago, so I don’t remember the details, but the current behavior seems correct to me.

An all zero vector is not an eigenvector, so we cannot return that. Or think about the random walk representation/analogy, you can start from any vertex and you stay there, so every vertex needs to be 1, assuming the maximum one is scaled to 1.