Menu

graph is a singular matrix

2008-02-27
2013-05-29
  • Tunjic Igor

    Tunjic Igor - 2008-02-27

         Hello,

    I have a problem with the RandomWalkBetweenness-Algorithm. The Graphs I want to analyse are very often transformed into so called
    singular-matrices. The problem is that Colt can not work with this kind of matrices. Is there a way to chack the Graph on this "singularity" before calling the algorithm ? And what does it mean "singularity" in a graph.

              Thank you for your help

     
    • amethyst

      amethyst - 2008-06-26

      Co_ask!

      Thanks in advance!

       
      • Joshua O'Madadhain

        (I think that this has been answered elsewhere, but just for completeness...)

        My best guess offhand is that a matrix is usually going to be called singular if the graph decomposes into > 1 component (maybe > 1 strongly connected component if the graph is directed).  However, there are singular matrices whose corresponding graphs have 0 or 1 components (see http://mathworld.wolfram.com/SingularMatrix.html for some trivial examples; the last one in their 2x2 list corresponds to the complete graph on 2 vertices with self-loops).

        At one point I spent some time trying to work out what the inverse of a graph was (in the 'matrix inverse' sense); there may be a good intuition for it, but I didn't develop one.  (Graph multiplication is fairly straightforward, but the idea of trying to figure out the graph G^-1 such that G*G^-1 yields a graph with all self-loops is just bizarre to me.)  At some point I may pound on that some more just so that I can put that problem to bed...but it won't be soon.  :)

        Joshua

         

Log in to post a comment.