JuliaGraphs / JuliaGraphs/Graphs.jl
[BUG] Eigenvector centrality for disconnected graphs
Nobody has claimed this yet.
- Dominant language
- Julia
- Stars
- 538
- Forks
- 128
- Avg merge
- 10h 25m
- Merged PRs (30d)
- 2
Description
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
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
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with the eigenvector_centrality(g) entry point and reproduce the disconnected six-node example from the issue repeatedly. Review the listed alternatives and the referenced Matlab behavior; a complete change needs an agreed outcome plus coverage showing stable handling for disconnected graphs, but the issue currently does not specify which behavior to implement.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- julia
- Domain
- data
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 35/100