[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* **<=**