[BUG] Eigenvector centrality for disconnected graphs

[greimel]

Description of bug

In a disconnected graph, eigenvector_centrality sometimes delivers random results.

g = SimpleGraph(6)
add_edge!.(Ref(g), 1:3, (1:3)')
add_edge!.(Ref(g), 4:6, (4:6)')

eigenvector_centrality(g)

Run this multiple times, the numbers are always different.

Strictly speaking,

Eigenvector centrality is not well-defined for disconnected graphs since the centrality scores of the individual components are independent of each other

source on stackoverflow

Here's what Matlab does

[...] If there are several disconnected components, then the algorithm computes the eigenvector centrality individually for each component, then scales the scores according to the percentage of graph nodes in that component. The centrality score of disconnected nodes is 1/numnodes(G).

https://de.mathworks.com/help/matlab/ref/graph.centrality.html

Potential fixes

• add a warning to the documentation
• check if a graph is connected and warn/error if it isn't
• emulate Matlab's behavior

[gdalle]

Hi, thanks for catching this! Which fix would you feel like implementing?

[simonschoelly]

I think the randomness comes from the solver ArnoldiMethod.jl that we are using here. Even if the graph is connected we can get slightly different results between each run:

julia> eigenvector_centrality(path_graph(2))
2-element Vector{Float64}:
 0.7071067811865475
 0.7071067811865475

julia> eigenvector_centrality(path_graph(2))
2-element Vector{Float64}:
 0.7071067811865476
 0.7071067811865476

But if the graph is disconnected the eigenvalues that we get from ArnoldiMethod.jl seem to be all over the place. Its been years since I had to deal with eigenvalues and vectors so I am not sure why this is the case.
This is a general issue in JuliaGraphs that we unfortunately did not solve yet. For example we have also issues when we use spectral methods in GraphPlot.jl for disconnected graphs.

I like the idea of emulating matlabs behavior though - so perhaps for now we can just implement that and document it well.

We also should think how this functions works in case of only weakly connected directed graphs. Here is an example that shows that we also have issues in that case:

julia> gd = DiGraph([Edge(1,2)])
{2, 1} directed simple Int64 graph

julia> eigenvector_centrality(gd)
2-element Vector{Float64}:
 0.9502791434299723
 0.3113993409787471

julia> eigenvector_centrality(gd)
2-element Vector{Float64}:
 0.6899770074048572
 0.7238312850745245