Skip to content

connectivity measure for graph nodes

2 messages · Mark Kimpel, Charilaos Skiadas

Mark Kimpel
# 
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
Charilaos Skiadas
# 
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: