Most efficient way to model an epidemic?

graph-tool
1

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?

2

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

attachment.html (2.63 KB)

3

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