[SciPy-User] Matrix-free version of connected_components

[Per Nielsen]

I have looked into the functions provided by the networkX package, however,
as far as I have been able to understand both networkX and scipy employ
similar methods for finding the connected components. Thus I still need the
full sparse matrix (or graph which I think is similar in memory usage) in
memory, which I would like to avoid.

Thank you for your reply and the reference.

Per

On Thu, Aug 2, 2012 at 12:50 PM, Daπid <davidmenhur at gmail.com> wrote:

> I am not sure if this is what you are looking for, but an alternative
> approach would be to transform the matrix into a graph, and then get
> the connected components using, for eample, networkx. You can find a
> complete description about the topic in: "Complex networks: Structure
> and dynamics" S. Boccaletti et al. (2006) Phys. Reports. Sorry that I
> cannot provide anything more concise.
>
>
> David.
>
> On Thu, Aug 2, 2012 at 8:07 AM, Per Nielsen <evilper at gmail.com> wrote:
> > Thanks for the reply.
> >
> > This approach looks like it could do the job, although it appaers to be
> > significantly more computationally demanding than connected_components,
> due
> > to the repeated need to find the Fiedler vector of very large systems.
> But I
> > will give it a go! :)
> >
> > Per
> >
> >
> > On Wed, Aug 1, 2012 at 3:18 PM, Gael Varoquaux
> > <gael.varoquaux at normalesup.org> wrote:
> >>
> >> You can try spectral graph partioning, computing the Fiedler with
> arpack,
> >> that only needs matrix-vector product:
> >> http://mathworld.wolfram.com/FiedlerVector.html
> >> http://en.wikipedia.org/wiki/Algebraic_connectivity
> >>
> >> HTH,
> >>
> >> Gael
> >>
> >> On Wed, Aug 01, 2012 at 02:15:51PM +0200, Per Nielsen wrote:
> >> > Hi all,
> >>
> >> > I work with large sparse matrices which consists of several
> disconnected
> >> > components and I only need one of these. So far I have succesfully
> been
> >> > using scipy.sparse.csgraph.connected_components to dig out the
> component
> >> > I
> >> > needed. This algorithm does however require the entire sparse matrix
> as
> >> > input, which sometimes is too large to fit in memory.
> >>
> >> > For this reason I wondered whether there existed a matrix-free version
> >> > of connected_components, or another algorithm achieving the same,
> where
> >> > I
> >> > would only need to provide a function calculating the sparse
> >> > matrix-vector
> >> > product.
> >>
> >> > Any help, hints, or information would be greatly appreciated :)
> >>
> >> > Cheers,
> >> > Per
> >>
> >>
> >> --
> >>     Gael Varoquaux
> >>     Researcher, INRIA Parietal
> >>     Laboratoire de Neuro-Imagerie Assistee par Ordinateur
> >>     NeuroSpin/CEA Saclay , Bat 145, 91191 Gif-sur-Yvette France
> >>     Phone:  ++ 33-1-69-08-79-68
> >>     http://gael-varoquaux.info
> http://twitter.com/GaelVaroquaux
> >> _______________________________________________
> >> SciPy-User mailing list
> >> SciPy-User at scipy.org
> >> http://mail.scipy.org/mailman/listinfo/scipy-user
> >
> >
> >
> > _______________________________________________
> > SciPy-User mailing list
> > SciPy-User at scipy.org
> > http://mail.scipy.org/mailman/listinfo/scipy-user
> >
> _______________________________________________
> SciPy-User mailing list
> SciPy-User at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.scipy.org/pipermail/scipy-user/attachments/20120802/97987b21/attachment.html>