[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[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?
Thank you very much in advance for your thoughts!
Matthew
- [igraph] How to work with subgraphs,
Matthew Walker <=