igraph-help
[Top][All Lists]

## Re: [igraph] count neighbourhood (python)

 From: Raphael Clifford Subject: Re: [igraph] count neighbourhood (python) Date: Sat, 15 Sep 2012 10:09:14 +0100

```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). 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?

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

```