How to efficiently find second-order neighbors in graph-tool?

Question

I'm using graph-tool and would like to find the second-order neighbors of a node (neighbors of neighbors who are not the node itself or the original neighbors). I thought it might be faster to use graph-tool's built-in topology functions, so I tried

# Here g is the digraph, and node is the vertex whose neighbors we want
d = gt.topology.shortest_distance(g,g.vertex(node),max_dist=2)
f = gt.GraphView(g,vfilt=d.a == radius)
second_neighbors = f.vertices()

However, this appears to be considerably slower than direct iteration, even on large graphs. How can I do this very quickly for large networks?

Answer 1

Using iter_out_neighbors and collecting nodes in Python sets should indeed be faster than using intermediary GraphView objects. Here's an example:

import graph_tool.collection

g = graph_tool.collection.data['serengeti-foodweb']
start_node = g.vertex(22)

so_neighbors = set()
exclude = set()
exclude.add(start_node)
for n1 in g.vertex(start_node).out_neighbors():
    exclude.add(n1)
    for n2 in n1.out_neighbors():
        so_neighbors.add(n2)
so_neighbors.difference_update(exclude)

Here's a visual check of the result with the network visualization package gravis inside a Jupyter notebook. The start node 22 is colored green, the second-order neighbors are colored red, and I'm hovering with the mouse over the first-order neighbor 132 to highlight it's direct surroundings. Disclaimer: I'm the author of gravis. It can be used to easily create interactive visualizations of graphs coming from graph-tool, NetworkX, igraph and a few other network packages in Python.