On Sat, Sep 15, 2012 at 5:09 AM, Raphael Clifford <[email protected]> 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 <[email protected]> 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 > [email protected] > https://lists.nongnu.org/mailman/listinfo/igraph-help -- Gabor Csardi <[email protected]> MTA KFKI RMKI _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
