Re: [igraph] How to work with subgraphs

[Gábor Csárdi]

Hi Matthew,

first of all, igraph is not very good with dynamic graphs, but you
probably already know that.

Secondly, the C attribute handler is not very good, either, the R (and
probably Python as well) attribute handler is much better, especially
if you have string attributes that are repeated for various vertices.

I am not sure that you need to create the big graph at all, it might
be enough to create the small graphs from your big tables of edges and
attributes.

As for replicating the attributes, the simplest would be probably to
add your own vertex ids and edge ids to the big graph, and whenever
you change an attribute in the small graph, go back to the big graph
and update that as well. This can be problematic if you have
overlapping subgraphs of the big graph. Which you probably do.

So, indeed, a possible approach is to have two big tables of data, one
for the vertices, one for the edges, and create graphs only when you
want to calculate something on a subgraph.

Best,
Gabor

On Wed, Nov 25, 2009 at 6:56 PM, Matthew Walker
<address@hidden> wrote:
> Hi,
>
> I would very much appreciate your recommendations on how you feel I should
> proceed; how would you tackle this problem?
>
> I have a "source graph" that could be fairly large (possibly
> thousands-to-millions of vertices but the edges are likely to be fairly
> sparse).  I plan to use the (experimental) C-based attribute system to store
> a fair amount of data for each vertex and each edge in the source graph
> (about 5-10 attributes per vertex and perhaps about 5 attributes per edge).
>  Once defined, the source graph will not change for the duration of the
> program.
>
> I then need to operate on small subsets of the source network.  The
> operations are likely to be similar to centrality measures (such as
> betweenness and closeness) or subset-wide operations (such as density or
> average path length).  Each subset will grow by a few nodes and then I will
> have to re-calculate values of the slightly larger subset.
>
> My question is: how would you recommend I work with the subsets?
>
> One option is to add an attribute into the source graph to say "are you part
> of the subset?".  This has the advantage of being easy to implement.  The
> disadvantage is that when I come to operate on the subsets I have to extract
> them with igraph_subgraph() which has time complexity proportional to the
> number of vertices plus the number of edges in the large source graph.  (I
> have to extract them because otherwise functions such as betweenness operate
> on the entire graph.)
>
> Another option is to store the subsets as distinct subgraphs.  But how would
> I link up all the attributes of the source graph so that they were
> immediately usable by (or, related to) the subset?  How would I grow the
> subsets such that they replicated the structure of the source graph?  I
>  think I would effectively be observing the source network and replicating
> it; but how do I ensure all the copies of the vertices and edges keep the
> attributes associated to their corresponding source-network vertices or
> edges?  Would there be a way to avoid copying the attribute information?
>
> Finally, are their other implementation possibilities you feel I should
> consider?
>
> Thank you very much in advance for your thoughts!
>
> Matthew
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM