Re: [igraph] working with bipartite graphs

[Gábor Csárdi]

Jose,

On Mon, Mar 16, 2009 at 1:42 PM, Jose Quesada <address@hidden> wrote:
[...]
> I know that most papers just dump bipartite graphs to unimode, and
> work from there... but I'm stuck with bipartite graphs. Plus
> bipartite.projection() on my graph -2.7 M vertices- eats up all memory
> and start swapping with 8Gb; bipartite.projection() must be using
> non-sparse matrix format at some point.

No, it is not.
igraph needs about (4*|E|+2*|V|) * 8 + 4*|V| bytes of memory to store
the graph. It needs further 16*|V| + (2*|V|+2*|E|) * 8 bytes to
calculate the bipartite projection. Assuming 5M edges in your graph,
this is less than 400MB altogether. So either 1) you have more edges,
or 2) there is something wrong with the function, or 3) the bipartite
projection results a dense graph. It would probably make sense to
write a function that does not actually create the projections, just
counts the number of edges in them. I think 3) is most likely.

Can you send me the number of edges in the graph, and the highest
vertex degree in your graph? Just to try to reproduce the problem.

> Question (1) Is bipartite.projection() memory intensive, or am I doing
> something wrong? I can imagine code that goes linearly through a
> sparse representation of the connections without loading the matrix to
> memory, but maybe I'm missing something important here.
>
> I'm right now interested in clusters() and page.rank().
>
> Since some functions, such as page.rank(), do not make sense when
> applied to a bipartite graph, I tried to make the graph unimode by
> removing the 'type' attribute. That didn't help, see small example below.
>
> Question (2): is it possible to tell igraph: "analyze this as if it
> was not bipartite"? Removing type didn't help, but this is obvious
> since the structure of the network IS bipartite, even without type.

Some functions support bipartite networks, but most of them don't.
Some functions are the same on bipartite networks as well, e.g. maybe
closeness() would be the same, but some measures are defined
differently for bipartite networks, e.g. modularity and Page Rank
should be modified. I am sure that there are some that have been never
defined for bipartite nets and some maybe don't even make sense on
them.

> Question (3): I worry that clusters() and other functions are really
> designed for unimode networks and they will blow up or return
> incorrect results when using bipartite networks. Is that the case?

They definitely don't blow up if a type attribute is present, at least
not because of the 'type' attribute. They just ignore the 'type'
attribute. Whether the result will make sense or not is a different
question. If you think that it does not, then we can add some warnings
if these functions are called with a 'type' vertex attribute.

> If
> so, maybe having some kind of trivial check -i.e., not running
> is.bipartite() since it seems expensive- within the function may be
> helpful. For example, calling page.rank(bipartiteNet) would return a
> warning. And so on for any other function that is not designed for
> bipartite functions.

Just check whether there is a 'type' attribute. To check that the
structure is bipartite or not takes of course longer.

Besides, basically _no_ function in igraph is designed for bipartite
networks. Except of course the ones that are explicitly for bipartite
nets, like graph.incidence() and bipartite.projection().

But the warning is a good idea, I would just need to go over all
igraph functions and add the warning, if it is needed.

Best,
Gabor

[...]

-- 
Gabor Csardi <address@hidden>     UNIL DGM