JuliaGraphs / JuliaGraphs/Graphs.jl

[BUG] Eigenvector centrality for disconnected graphs

Open
#404 3 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug help wanted
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

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

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.