Re: [igraph] count neighbourhood (python)

[Gábor Csárdi]

On Sat, Sep 15, 2012 at 5:09 AM, Raphael Clifford <address@hidden> wrote:
> I tested the running time of the igraph implementation of
> neighborhood_size it does indeed appear to be fast and memory
> efficient (although I don't know exactly how it works).

It simply does a breadth-first search form the starting vertex, and
the igraph data structure ensures fast traversal of the graph.

> I would also like to count the number of edges within a 2 hop neighborhood of 
> each
> node.  One way is
>
> [g2.subgraph(g2.neighborhood(v, order = 2)).ecount() for v in g.vs]
>
> Is there a better/faster igraph way?

I think this is probably the best way. At the C level there is a
function that gives these graphs directly, but it does essentially the
same as you are doing.

Gabor

> Raphael
>
> On 15 September 2012 09:21, Raphael Clifford <address@hidden> wrote:
>> I would like to count the number of vertices within a 2 hop distance
>> of each node in a large sparse graph.  I see there is a function which
>> one could call with neighborhood size(vertices=g.vs, order=2). What
>> method is used to do the calculation?
>>
>> A classic way to do it would be to represent the graph as a sparse
>> matrix, square it using a clever sparse matrix multiplication
>> algorithm and count the number of elements in each row that are
>> non-negative.  I am wondering how this would compare to the
>> implemented method in igraph.  Can igraph make a sparse matrix that
>> could be fed directly into
>> http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csr_matrix.html#scipy.sparse.csr_matrix
>> for example?
>>
>> Raphael
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help



-- 
Gabor Csardi <address@hidden>     MTA KFKI RMKI