Discovering ego-networks, efficiently.

graph-tool
1

Dear all,

I am using the following code to extract for a node of a graph the induced subgraph containing the node and her neighbors (aka, the ego-netwkork).

Can I make it more efficiently? In particular, is there a way to avoid using python to create the neighbor list (or at least avoid the type casting).

If not, could I use some code in C/C++ for doing this an embedded in graph_tool?

Thanks a lot,
Panos

def egoNetwork(inGraph, node):
    '''
    Compute the ego-network subgraph of the -inGraph- where the ego is the -node-.
    Precondition: inGraph is undirected
    '''
    neighbors = [int(n) for n in node.out_neighbours()]
    neighborhood = inGraph.new_vertex_property("bool")
    neighborhood.a[neighbors] = 1
    neighborhood.a[int(node)] = 1
    return GraphView(inGraph, vfilt = neighborhood)

attachment.html (2.32 KB)

2

The simplest thing one could do is:

    mask = g.new_vertex_property("bool")
    for u in node.out_neighbours():
        mask[u] = True
    mask[node] = True
    ego = GraphView(inGraph, vfilt=mask)

but if you have many neighbours in comparison to the whole graph, the
following may be faster:

    mask = shortest_distance(g, source=node, max_dist=1)
    mask.a[mask.a > 1] = False
    mask[node] = True

    ego = GraphView(inGraph, vfilt=mask)

Best,
Tiago