Graphs.jl icon indicating copy to clipboard operation
Graphs.jl copied to clipboard

Some normalized_cut() fixes

Open alyst opened this issue 2 years ago • 1 comments

Fixes a few issues I have encountered when running normalized_cut():

  • sometimes eigs() returns less eigenvectors than requested, even less than 2. In the latter case the algorithm now would put all vertices to separate modules instead of throwing OutOfBounds exception.
  • isolated or nearly isolated vertices result in degenerated W matrix and zeros on the D diagonal. Now the algorithm would check for that, put the corresponding vertices to separate modules and continue cutting with these vertices excluded (instead of throwing exception upon inv(D)). (Such situations should have been handled by the generalized eigs(), but it is not implemented in ArnoldiMethod.jl, and IIUC using Arpack.jl is problematic).
  • some cleanups to eigs() (handling real and complex cases uniformly)

alyst avatar Dec 24 '21 16:12 alyst

Codecov Report

Merging #84 (17f7023) into master (d25e5d7) will decrease coverage by 0.06%. The diff coverage is 75.00%.

@@            Coverage Diff             @@
##           master      #84      +/-   ##
==========================================
- Coverage   97.30%   97.25%   -0.06%     
==========================================
  Files         115      115              
  Lines        6764     6768       +4     
==========================================
  Hits         6582     6582              
- Misses        182      186       +4     

codecov[bot] avatar Jan 09 '22 11:01 codecov[bot]

Is someone able to review this ? It seems good to me, but I'm not very knowledgeable in spectral graph theory

etiennedeg avatar Nov 08 '22 09:11 etiennedeg