Mark, if I understand what you are asking, then you likely want either the Floyd-Warshall algorithm:
http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm or Djikstra's algorithm http://en.wikipedia.org/wiki/Dijkstra%27s_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 > ______________________________________________ R-help@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.