igraph-help
[Top][All Lists]

## [igraph] How to work with subgraphs

 From: Matthew Walker Subject: [igraph] How to work with subgraphs Date: Wed, 25 Nov 2009 12:56:55 -0500 User-agent: Thunderbird 2.0.0.23 (X11/20090812)

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?