Hi all, Relative graph-tool newbie here. I have a situation which I'm not sure how to approach in an efficient manner. I was hoping maybe someone could give some insight here. Basically, I want to generate an undirected Price network of N nodes, but I would like to be able to "look back" and access the subgraph when the network was only "k" nodes large. For simplicity's, say I'm adding one edge per vertex (i.e. m=1). One obvious way to do this seems to be to write a generator where, after adding the k-th vertex, you append a copy of the graph at that time onto some list. Then at the end you would have a list of length N where each element is a graph object. However... this seems kind of like overkill. I was thinking another way to do this is to generate only one graph, but give each node and edge an "age" attribute (as in the example in the tutorial). Then you could get the time-k subgraph by selecting only nodes and edges that have age less than k. Is there an obvious way to implement this in graph-tool? Specifically, for each time-k subgraph I'd want to be able to access the degree distribution at that time, and also the usual properties of the graph such as neighbors of a given node, etc. Many thanks, Jimmy
On 04/26/2014 08:35 PM, Jimmy Jin wrote:
However... this seems kind of like overkill. I was thinking another way to do this is to generate only one graph, but give each node and edge an "age" attribute (as in the example in the tutorial). Then you could get the time-k subgraph by selecting only nodes and edges that have age less than k.
Is there an obvious way to implement this in graph-tool? Specifically, for each time-k subgraph I'd want to be able to access the degree distribution at that time, and also the usual properties of the graph such as neighbors of a given node, etc.
Yes, the "age" is simply the index of the node/edge, since they are added sequentially. The first vertex added has index 0, the second has index 1, and so on. To extract the graph at a given age you just construct a GraphView, i.e. u = GraphView(g, vfilt=lambda v: int(v) < 1000) will give you the graph at time step 1000. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
Oh my goodness, that is such an easy solution. Thanks for pointing this out Tiago. Good design at work! Sorry for such a trivial question. -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
Hi all, this is a follow-up question to the one posed above. So, ultimately what I'd like to do in the graph sequence idea above is this: Assume we are generating an undirected Price network with m=1, so generating a tree. For each time i in the sequence, I would like to identify the node which was newly added (which ought to simply be the one with index i, or maybe i-1) and then extract the degree of the node in the *previous* graph which the new node connected to. Using the graph idea of Tiago, the code I've written looks like: This code seems to work fine, the only problem is that it takes forever. Fortunately the memory taken up isn't very large as per Tiago's help, but even when I try to run this on an N=2000 node graph it takes over 30 seconds (I'm running Ubuntu with an i7 chip and 4g of memory). I would eventually want to run something like this for graphs of 100,000 nodes or larger. My questions are: 1) Where is the performance bottleneck coming from? and 2) Is there an easy way to get around it? Thanks for all your help. Many thanks, -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
On 04/28/2014 09:21 PM, gogurt wrote:
import graph_tool.all as gt def extract_deg(G, start):
# Initialize lists deg = []
if start == 1: deg.append(1) norm.append(1) i = 2 else: i = start
while i < sum(1 for _ in G.vertices()):
Gcurr = gt.GraphView(G,vfilt=lambda v: int(v) <= i) Gprev = gt.GraphView(G,vfilt=lambda v: int(v) < i)
# For time i, get the degree (as of time i-1) of # the node which has the edge to the newly-added # node in time i
v = Gcurr.vertex(i) for j in v.all_neighbours(): w = Gprev.vertex(j) deg.append(w.in_degree() + w.out_degree()) i += 1
return deg
Your code is inefficient in many ways. In order to understand why, you have to ask yourself for all statements, how many operations are necessary for it to be completed. For instance, in your loop statement: while i < sum(1 for _ in G.vertices()): The sum simply counts the number of vertices, but takes O(N) time. You should simply use G.num_vertices() which is O(1). When you construct the filter, Gcurr = gt.GraphView(G,vfilt=lambda v: int(v) <= i) The function provided to vfilt is called for each vertex, which is again O(N). You can improve it by using array expressions: mask = G.vertex_index.copy("int") mask.a = mask.a <= i Gcurr = gt.GraphView(G,vfilt=mask) This is still O(N), but avoids that a python function gets called for each vertex. However, it is possible to remove the O(N) by not depending on the GraphView altogether. When you do the loop over the neighbours, you can simply ignore newer vertices as you go along: v = G.vertex(i) for w in v.out_neighbours(): if int(w) < i: continue k = len([u for u in w.out_neighbours() if int(u) < i]) deg.append(k) Which should do as you want, and is much faster. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (3)
-
gogurt -
Jimmy Jin -
Tiago de Paula Peixoto