Re: [R] connectivity measure for graph nodes

From: Charilaos Skiadas <>
Date: Tue, 04 Mar 2008 21:25:16 -0500


        if I understand what you are asking, then you likely want either the Floyd-Warshall algorithm:

or Djikstra's algorithm

The package igraph seems to have some useful methods, (The shortest.paths method is probably what you want, I think).

How large a graph are we talking about here?

Haris Skiadas
Department of Mathematics and Computer Science Hanover College

On Mar 4, 2008, at 9:03 PM, Mark W Kimpel wrote:

> I am doing some work the Rgraphviz, a Bioconductor package, but
> since my
> question is of a more general nature, thought I would send to this
> list
> in hopes that a graph theory expert could answer my question.
> I wish to do some statistics on node-node relationships. In
> particular,
> I want to see if two connected nodes share a common property. I
> believe
> that the more "connected" the two nodes are the more likely it
> would be
> that they share the property. The graph is highly connected, with a
> large majority of nodes connected in some fashion.
> My first question is: can anyone make this real easy and tell me if
> this
> has been done and how?
> If not, I need to start with developing a measure of connectedness
> that
> includes degrees of separation and number of edges at each degree. The
> highest level of connectivity, with weighting 1, would be a first
> order
> connection (the graph is undirected). Beyond that, of course, it gets
> more complicated. To begin, I need to identify the best path
> between two
> nodes then characterize that path.
> Rgraphviz seems to have a fair amount of rendering capabilities, but I
> don't see many functions to statistically analyze the graph.
> Thanks,
> Mark
> --
> Mark W. Kimpel MD ** Neuroinformatics ** Dept. of Psychiatry
> Indiana University School of Medicine
> 15032 Hunter Court, Westfield, IN 46074
> (317) 490-5129 Work, & Mobile & VoiceMail
> (317) 204-4202 Home (no voice mail please)

> mwkimpel<at>gmail<dot>com
> mailing list PLEASE do read the posting guide and provide commented, minimal, self-contained, reproducible code. Received on Wed 05 Mar 2008 - 02:39:24 GMT

Archive maintained by Robert King, hosted by the discipline of statistics at the University of Newcastle, Australia.
Archive generated by hypermail 2.2.0, at Wed 05 Mar 2008 - 08:30:19 GMT.

Mailing list information is available at Please read the posting guide before posting to the list.

list of date sections of archive