Re: [igraph] graph.cohesion/vertex.connectivity request and suggestion

[Gabor Csardi]

Peter,

On Thu, Apr 19, 2007 at 10:10:54AM -0500, address@hidden wrote:
> Hi,
> 
> I've been using the graph.cohesion() (aka vertex.connectivity())  
> function pretty heavily for a project I'm working on, and it's great  
> in general. However I have one suggestion and one request concerning  
> its implementation.
> 
> First, a suggested shortcut that I've discovered and have been using  
> that might be worth building in to the function. For large graphs,  
> the function takes a very long time, and the result is likely to be  
> either 0 or 1. There's a theorem somewhere that says that for a graph G
> vertex.connectivity(G) <= edge.connectivity(G) <= min(degree(G)) .
> I'm running the function on graphs with between 200 and 800 vertices,  
> and running it in the following control flow has meant that I rarely  
> need to call the function itself and my functions run much more quickly:
> 
> if(!is.connected(G)){
>     k <- 0
> }else if(min(degree(G))==1){
>     k <- 1
> }else{
>     k <- graph.cohesion(G)
> }
> 
> Calculating the degree takes relatively minimal time compared to  
> graph.cohesion, so I thought this might be worth implementing in the  
> function itself.

Good point. I'm aware of this theorem. The main reason for this 
not beeing in igraph is that igraph mainly wants to be a stable 'base' 
library, and features like this can be implemented in five minutes, 
either in R or C, or whatever language you use. I think i'll add this as 
an option.

> 
> Second, a feature request:
> Would it be possible to have a function that both finds the vertex  
> conectivity k of a graph and returns a list of the vertex cutsets of  
> size k? I don't just need to know minimum size of the cutsets, I need  
> to know what cutsets reach that minimum. This shouldn't be too hard  
> to get out of the maxflow/mincut algorithm. Right now I have a sort  
> of kludgey function in R that does this, and it doesn't take too long  
> if k is known, but for vcount(G)>300 it's still a big waste of time  
> (not to mention redundant). In any case, either a seperate function  
> or an option in the current functions would be a boon to my work.

Another good point, this is already on the TODO list. When it'll be 
done depends mostly on my free time. But thanks for the suggestion,
i'll give higher priority for this. Unfortunately the push-relabel 
maxflow algorithm and its implementation is not a piece or cake. 
I'm also planning to implement the while methodology written in
Structural Cohesion and Embeddedness: A Hierarchical Concept of Social
Groups by Moody and White.

> Thanks overall for the great package, by the way. I hardly need to  
> touch Pajek anymore!

Thanks, please keep on sending suggestions to help make it better,

Best,
Gabor

> Peter McMahan
> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help

-- 
Csardi Gabor <address@hidden>    MTA RMKI, ELTE TTK