R help - Aug 2008 - Igraph library: How to calculate APSP (shortest path matrix) matrix for a subset list of nodes.

Dear R Users,

I have a network of 25000 total nodes and a list of 500 node which is a
subset of all nodes. Now I want to calculate the APSP (all pair shortest
path) matrix only for these 500 nodes.
I would appreciate any help.
Thanks in advance

Dinesh

-- 
Dinesh Kumar Barupal
Research Associate
Metabolomics Fiehn Lab
UCD Genome Center
451 East Health Science Drive
GBSF Builidng
University of California
DAVIS
95616
http://fiehnlab.ucdavis.edu/staff/kumar

	[[alternative HTML version deleted]]

As far as I know/remember, if your graph is connected and contains E edges then
you can find the shortest distance from any particular vertex to all other
vertices in O(E) operations. You can repeat this procedure starting from every
node (out of the 500). If you have 100,000 edges this will require about
100,000*500 = 50,000,000 operations (times a small factor) which is very
reasonable.


--- On Mon, 25/8/08, dinesh kumar <barupal at gmail.com> wrote:
> From: dinesh kumar <barupal at gmail.com>
> Subject: [R] Igraph library: How to calculate APSP (shortest path matrix)
matrix for a subset list of nodes.
> To: r-help at r-project.org
> Received: Monday, 25 August, 2008, 8:00 AM
> Dear R Users,
> 
> I have a network of 25000 total nodes and a list of 500
> node which is a
> subset of all nodes. Now I want to calculate the APSP (all
> pair shortest
> path) matrix only for these 500 nodes.
> I would appreciate any help.
> Thanks in advance
> 
> Dinesh
> 
> -- 
> Dinesh Kumar Barupal
> Research Associate
> Metabolomics Fiehn Lab
> UCD Genome Center
> 451 East Health Science Drive
> GBSF Builidng
> University of California
> DAVIS
> 95616
> http://fiehnlab.ucdavis.edu/staff/kumar
> 
> 	[[alternative HTML version deleted]]
> 
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
> http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained,
> reproducible code.

I was too optimistic - the complexity is O(E*log(V)) where V is the number of
nodes, but since log(25000) < 20 this is still reasonable.


--- On Mon, 25/8/08, Moshe Olshansky <m_olshansky at yahoo.com> wrote:
> From: Moshe Olshansky <m_olshansky at yahoo.com>
> Subject: Re: [R] Igraph library: How to calculate APSP (shortest path
matrix) matrix for a subset list of nodes.
> To: r-help at r-project.org, "dinesh kumar" <barupal at
gmail.com>
> Received: Monday, 25 August, 2008, 3:27 PM
> As far as I know/remember, if your graph is connected and
> contains E edges then you can find the shortest distance
> from any particular vertex to all other vertices in O(E)
> operations. You can repeat this procedure starting from
> every node (out of the 500). If you have 100,000 edges this
> will require about 100,000*500 = 50,000,000 operations
> (times a small factor) which is very reasonable.
> 
> 
> --- On Mon, 25/8/08, dinesh kumar <barupal at gmail.com>
> wrote:
> 
> > From: dinesh kumar <barupal at gmail.com>
> > Subject: [R] Igraph library: How to calculate APSP
> (shortest path matrix) matrix for a subset list of nodes.
> > To: r-help at r-project.org
> > Received: Monday, 25 August, 2008, 8:00 AM
> > Dear R Users,
> > 
> > I have a network of 25000 total nodes and a list of
> 500
> > node which is a
> > subset of all nodes. Now I want to calculate the APSP
> (all
> > pair shortest
> > path) matrix only for these 500 nodes.
> > I would appreciate any help.
> > Thanks in advance
> > 
> > Dinesh
> > 
> > -- 
> > Dinesh Kumar Barupal
> > Research Associate
> > Metabolomics Fiehn Lab
> > UCD Genome Center
> > 451 East Health Science Drive
> > GBSF Builidng
> > University of California
> > DAVIS
> > 95616
> > http://fiehnlab.ucdavis.edu/staff/kumar
> > 
> > 	[[alternative HTML version deleted]]
> > 
> > ______________________________________________
> > R-help at r-project.org mailing list
> > https://stat.ethz.ch/mailman/listinfo/r-help
> > PLEASE do read the posting guide
> > http://www.R-project.org/posting-guide.html
> > and provide commented, minimal, self-contained,
> > reproducible code.
> 
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
> http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained,
> reproducible code.

It is O(|V|+|E|) to calculate unweighted shortest paths from one vertex 
to all others. It is indeed O(|E|*log|V|) if you have a weighted graph.
But both of these should be reasonable for |V|=25000 and 500 sources, 
you just need a fair amount of memory.

For the details see ?shortest.paths.

Gabor

On Sun, Aug 24, 2008 at 11:06:08PM -0700, Moshe Olshansky
wrote:
> I was too optimistic - the complexity is O(E*log(V)) where V is the number
of nodes, but since log(25000) < 20 this is still reasonable.
> 
> 
> --- On Mon, 25/8/08, Moshe Olshansky <m_olshansky at yahoo.com>
wrote:
> 
> > From: Moshe Olshansky <m_olshansky at yahoo.com>
> > Subject: Re: [R] Igraph library: How to calculate APSP (shortest path
matrix) matrix for a subset list of nodes.
> > To: r-help at r-project.org, "dinesh kumar" <barupal at
gmail.com>
> > Received: Monday, 25 August, 2008, 3:27 PM
> > As far as I know/remember, if your graph is connected and
> > contains E edges then you can find the shortest distance
> > from any particular vertex to all other vertices in O(E)
> > operations. You can repeat this procedure starting from
> > every node (out of the 500). If you have 100,000 edges this
> > will require about 100,000*500 = 50,000,000 operations
> > (times a small factor) which is very reasonable.
> > 
> > 
> > --- On Mon, 25/8/08, dinesh kumar <barupal at gmail.com>
> > wrote:
> > 
> > > From: dinesh kumar <barupal at gmail.com>
> > > Subject: [R] Igraph library: How to calculate APSP
> > (shortest path matrix) matrix for a subset list of nodes.
> > > To: r-help at r-project.org
> > > Received: Monday, 25 August, 2008, 8:00 AM
> > > Dear R Users,
> > > 
> > > I have a network of 25000 total nodes and a list of
> > 500
> > > node which is a
> > > subset of all nodes. Now I want to calculate the APSP
> > (all
> > > pair shortest
> > > path) matrix only for these 500 nodes.
> > > I would appreciate any help.
> > > Thanks in advance
> > > 
> > > Dinesh
> > > 
> > > -- 
> > > Dinesh Kumar Barupal
> > > Research Associate
> > > Metabolomics Fiehn Lab
> > > UCD Genome Center
> > > 451 East Health Science Drive
> > > GBSF Builidng
> > > University of California
> > > DAVIS
> > > 95616
> > > http://fiehnlab.ucdavis.edu/staff/kumar
> > > 
> > > 	[[alternative HTML version deleted]]
> > > 
> > > ______________________________________________
> > > R-help at r-project.org mailing list
> > > https://stat.ethz.ch/mailman/listinfo/r-help
> > > PLEASE do read the posting guide
> > > http://www.R-project.org/posting-guide.html
> > > and provide commented, minimal, self-contained,
> > > reproducible code.
> > 
> > ______________________________________________
> > R-help at r-project.org mailing list
> > https://stat.ethz.ch/mailman/listinfo/r-help
> > PLEASE do read the posting guide
> > http://www.R-project.org/posting-guide.html
> > and provide commented, minimal, self-contained,
> > reproducible code.
> 
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
-- 
Csardi Gabor <csardi at rmki.kfki.hu>    MTA RMKI, ELTE TTK