[igraph] How to work with subgraphs

[Matthew Walker]

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