Most efficient way to model an epidemic?
Hi all, So I've scoured the documentation for this but I've been indoctrinated in the ways of NetworkX, so I'm pretty confused. I want to implement a simple discrete-time epidemic process on a network. For example, starting out with one infected vertex, I want to explore all its out-neighbors and infect those with probability p, and then the neighbors of those out-neighbors, etc. Once you're infected, you are infected forever. The way I've done this in NetworkX is to essentially keep track of 3 lists of nodes (infected, active, unexplored) and update them in a simple loop. Then at the end of the process when the epidemic dies or hits a threshold, I just subset the graph and get the subgraph which represents the path of the infection. *My question is: *what's the most efficient way to do this using graph-tool? At first I thought the same approach (subsetting vertices, which would mean working with vertex iterables) would be the fastest way, but then I thought maybe working on the original graph with a vertex PropertyMap would be better. But my intuition is extremely poor on this (e.g. is it even possible to subset vertices in a graph based on their values in a PropertyMap object?). Any pointers? -- 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 gogurt, It seems you can keep the state of vertices in a boolean property map and queue the vertices whose neighbors you gotta visit in a python list. []s ale On Thu, Aug 20, 2015 at 3:40 PM, gogurt <gogurt@gmail.com> wrote:
Hi all,
So I've scoured the documentation for this but I've been indoctrinated in the ways of NetworkX, so I'm pretty confused.
I want to implement a simple discrete-time epidemic process on a network. For example, starting out with one infected vertex, I want to explore all its out-neighbors and infect those with probability p, and then the neighbors of those out-neighbors, etc. Once you're infected, you are infected forever.
The way I've done this in NetworkX is to essentially keep track of 3 lists of nodes (infected, active, unexplored) and update them in a simple loop. Then at the end of the process when the epidemic dies or hits a threshold, I just subset the graph and get the subgraph which represents the path of the infection.
*My question is: *what's the most efficient way to do this using graph-tool?
At first I thought the same approach (subsetting vertices, which would mean working with vertex iterables) would be the fastest way, but then I thought maybe working on the original graph with a vertex PropertyMap would be better. But my intuition is extremely poor on this (e.g. is it even possible to subset vertices in a graph based on their values in a PropertyMap object?). Any pointers?
-- 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. _______________________________________________ graph-tool mailing list graph-tool@skewed.de http://lists.skewed.de/mailman/listinfo/graph-tool
On 20.08.2015 20:40, gogurt wrote:
The way I've done this in NetworkX is to essentially keep track of 3 lists of nodes (infected, active, unexplored) and update them in a simple loop. Then at the end of the process when the epidemic dies or hits a threshold, I just subset the graph and get the subgraph which represents the path of the infection.
The difference between graph-tool and NetworkX for things like this is very superficial. Essentially every algorithm that you can come up with for networkx can be mapped one-to-one to graph-tool, and the efficiency will in general be about the same. Graph-tool will be faster only when the important loops can be moved out of Python and into C++.
*My question is: *what's the most efficient way to do this using graph-tool?
At first I thought the same approach (subsetting vertices, which would mean working with vertex iterables) would be the fastest way, but then I thought maybe working on the original graph with a vertex PropertyMap would be better.
You can do exactly that, but the lookup will be slower if you use sets or lists, than if you just mark each infected node with a Boolean property map.
But my intuition is extremely poor on this (e.g. is it even possible to subset vertices in a graph based on their values in a PropertyMap object?).
Why shouldn't it be possible? There are many ways to to this. The simplest is something like: infected = [v for v in g.vertices() if infected[v]] but this is of course O(N). I think the best approach is to keep an infected set together with a property map: is_infected = g.new_vertex_property("bool", False) infected_set = [] root = g.vertex(10) is_infected[root] = True infected_set.append(root) while len(infected_set) < g.num_vertices(): new_infected = [] for v in infected_set: for u in v.out_neighbours(): if random() < p and not is_infected[u]: is_infected[u] = True new_infected.append(u) infected_set.extend(new_infected) I hope this helps. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (3)
-
Alexandre Hannud Abdo -
gogurt -
Tiago de Paula Peixoto