igraph-help
[Top][All Lists]

## Re: [igraph] Rewiring connected graph and/or checking connectedness loca

 From: Rafael Calsaverini Subject: Re: [igraph] Rewiring connected graph and/or checking connectedness locally Date: Wed, 11 May 2011 15:48:48 -0300

Gabor,

I didn't know that igraph wasn't ideal for dynamical graphs. I used it mainly cause I didn't had time to create my own library.

I use three things from igraph that I'd have to search around on how to implement myself: testing connectedness, calculate the average geodesic distance and betweenness centrality (it's not critical, though).

Will the gain in performance be big if I implement a simple adjacency list and adequate functions? Do you know of any other library that is good for this kind of thing?
---
Rafael Calsaverini
Dep. de Física Geral, Sala 336
Instituto de Física - Universidade de São Paulo

http://stoa.usp.br/calsaverini/weblog
CEL: (11) 7525-6222
USP: (11) 3091-6803

On Wed, May 11, 2011 at 09:44, Gábor Csárdi wrote:
Rafael,

igraph is not very good for dynamic graphs, removing or adding an edge
has the same cost, as recreating the graph from scratch.

You could try using adjacency lists instead of igraph graphs, if you
don't need to call any igraph functions to calculate properties of
your graphs while doing the MC. This also means that you'll need to
write your own function that checks for connectedness, but this is not
very hard, a DFS of BFS will do.

There is a measure that you could use for deciding whether the graph
will be connected, if you remove any single edge from it. It is called
edge connectivity. Unfortunately, it is expensive to calculate it, and
it is cheaper to actually remove the edge and check that the graph is
connected.

Or, theoretically you could also check the biconnected components in
your graphs, removing and edge from a biconnected component keeps that
component connected. But again, I think this will take more time to
maintain than just checking connectedness.

Best,
Gabor

On Tue, May 10, 2011 at 3:22 PM, Rafael Calsaverini
> Hi,
> I am working on a monte carlo simulation of a system whose state is
> described as a graph. At every step of the simulation I must generate a new
> set of edges for the graph based on it's last state and accept or not the
> new configuration based on some criteria. The problem is that I
> must guarantee that the graph remain connected at each step.
> The way I'm doing this now is by brute force:
>   - select a random pair of vertices;
>   - if there's not an edge between them, create one.
>   - if there is an edge between them, remove it and check if the graph
> remains connected.
>   - if it does, then proceed, if it doesn't, put the edge back and try
> another pair.
> This works for my purposes, but the problem is that the last step is too
> expensive. There's a phase in the model where the graph is almost fully
> connected and it's very improbable that removing an edge will divide the
> graph in two components. There's another phase in which the graph resembles
> a star, and almost any edge I try to remove will make the graph not
> connected, so I keep removing edges and putting them back for a long time.
> My question are:
> is there a different way to do this?
> is there any function in igraph that will rewire the graph and keep it
> connected?
> is there any way to check locally if removing a given edge will separate the
> graph in two components?
> My graphs are not big (20 to 50 vertices, from a few edges to fully
> connected), but I have to repeat the monte carlo steps many, many, many
> times...
> Thanks in advance for the help
> ---
> Rafael Calsaverini
> Dep. de Física Geral, Sala 336
> Instituto de Física - Universidade de São Paulo
>
> http://stoa.usp.br/calsaverini/weblog
> CEL: (11) 7525-6222
> USP: (11) 3091-6803
>
>
> _______________________________________________
> igraph-help mailing list
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>

--
Gabor Csardi <address@hidden>     MTA KFKI RMKI

_______________________________________________
igraph-help mailing list