[igraph] intersection and union of neighborhood in a bipartite graph

[Yannick Rochat]

Dear Gábor & Tamás & All,

Thanks for the answer last time!

This time I'm trying to obtain the intersection and union of neighborhoods of vertices from the same set (top xor bottom) in a bipartite graph. I would like to reproduce the results of Latapy et al. (social networks http://www-rp.lip6.fr/~latapy/Publis/socnet07.pdf page 13, first equation). In this article, he computes them on a 2x10^6 nodes graph …

I'm using R 2.10.0 with igraph 0.5.2

I've found an easy and very efficient way to compute the intersection. Let N(u) be the set of the neighbours of vertex u. Then extract the sparse adjacency matrix (only 0's and 1's, the graph is simple), m, and (m %*% m)_{uv} (in fact m^2) gives | N(u) \inter N(v) |.

About the union, I couldn't find any way to multiply or add matrices to get the result. What I've done :

If I write two loops (on couple of vertices of a same set), …

… computing sum ( m[u,] + m[v,] - | N(u) \inter N(v) | ) costs too much.

… computing sum ( m[u,] | m[v,] ) costs too much.

… translating in R and computing Latapy's original code in C : ftp://www-rp.lip6.fr/pub/latapy/Bip/bip.c costs too much

… using neighbors(g, … ) or V(g)[nei( … )] and the function 'union' costs too much.

etc.

I think this problem occurs in R because of the two loops. I've been told R is very slow when using them.


Anyway, I would like to ask if anybody knows how to solve this problem. Is there a way to compute it without the two loops ? Can I extract a row or a column and keep its sparse structure ?

This question may be out of subject here in this mailing-list, but if igraph can handle it, I would be glad to know :-) I've been losing so much time that an effective solution may be very simple …


Thanks !


Yannick