[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] count neighbourhood (python)

From: Gábor Csárdi
Subject: Re: [igraph] count neighbourhood (python)
Date: Sun, 16 Sep 2012 09:46:04 -0400

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.


> 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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]