Extract a neighborhood of a randomly selected node

graph-tool
1

Hi all,

I have a pretty large graph G from which want to do the following:

1) Randomly select a node from G
2) Get the vertices that lie within radius 2 of the node
3) Extract the subgraph induced by those vertices

My code for doing this is the following:
/
randnode = random.randint(0,G.num_vertices())

pred_map = gt.shortest_distance(G, source=G.vertex(randnode), max_dist=2,
pred_map=True)
pred_tree = gt.predecessor_tree(G, pred_map[1])

# DEBUG
#print(pred_tree.num_vertices())

verts = pred_tree.vertices()
vmap = G.new_vertex_property('bool')
for i in verts:
    vmap[G.vertex_index[i]] = True
/

Then using vmap, I plan to do a GraphView on G and get the subgraph. But
something is clearly going wrong here. If I uncomment the line under the #
DEBUG comment, then I clearly see that pred_tree always has the same number
of vertices as the original graph.

Am I missing something about how predecessor_tree() works? I expected it to
only return a subgraph of the original graph, which should have a lot fewer
vertices...

2

Hi jimmy/gogurt,

The predecessor graph, returned by predecessor_tree, contains all the nodes
from the original graph, and edges representing the predecessor
relationships given by the map.

In any case, understand that normally you should not have to create an
intermediate graph in order to filter a graph, since you can just use the
information you had to begin with to directly build the filter.

In your case, notice that to get the information you need you don't need
the predecessor map, just the distance map which always gets returned by
shortest_distance.

The logic being: all vertices reached by shortest_distance get a distance
attributed which is an integer smaller than the size of the graph,
otherwise they get attributed an "impossible" distance which is larger than
the size of the graph.

(In your case the vertices of interest have distance of less or equal to 2,
but as you already tell shortest_distance to stop at distance 2, any vertex
that has a higher distance will still be mapped to the "impossible"
distance, so we can just compare the distance to the size of the graph.)

All you have to do is create a new property and assign values to it
according to what you find in the distance map:

g = gt.Graph()

v = g.vertex( random.randint( 0, g.num_vertices() ) )

dmap = gt.shortest_distance( g, source=v, max_dist=2 )

mymap = g.new_vertex_property( 'bool' )

for w in g.vertices():
  if dmap[w] < g.num_vertices():
    mymap[w] = True

Now you can use mymap in GraphView.

I haven't actually ran the code so there might be typos.
Good luck and have fun!

Abraços,
l
e
.~´

attachment.html (4.17 KB)

3

This is entirely right. I would just like to point out that it is a good
idea to avoid iterator loops whenever possible. The above can be done
more compactly and efficiently with:

    dmap = gt.shortest_distance(g, source=v, max_dist=2)
    u = GraphView(g, vfilt=dmap.a < g.num_vertices())

Best,
Tiago

4

Amazing. Thanks Alexandre and Tiago. There's definitely a steep learning
curve to graph-tool but I appreciate how nice it is once you get the hang of
it. Thanks for your patience once again.

-Jimmy