Re: [igraph] working with bipartite graphs

[Jose Quesada]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
 
Gábor Csárdi wrote:

Hi Gábor,
> 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.
>
> summary(dg)
Vertices: 2901905
Edges: 10962889
Directed: FALSE
No graph attributes.
Vertex attributes: type.
No edge attributes.

max degree:

max(stats$degree)
[1] 5405

This is the IMDB movie database, in case you were wondering.

>> 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.
>
I agree. I know that this could be a monumental task, but maybe
listing which functions do not work or the method doesn't make sense,
for bipartite graphs could be very useful. Having constructors,
checkers etc for bipartite graphs, but an arsenal of functions that
are not necessarily working for them is problematic. Of course, one
could always look at the code and think carefully if the results make
sense or not, but most users may not have the skill, time or raw
need.  The warning  does sound like a good solution.  Looks like
bipartite graphs are  bleeding edge, and even projection to unimode
is  kind of  a problem people work on right now. That makes them
'bleeding edge'. But also, a killer feature of igraph.
>> 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.
Yes, but in my case it took me a while to understand that. In other
circumstances (i.e., had I gotten results according to my hypothesis),
I would have run with them, not realizing they were not right.
This might be a matter of taste, but a warning of an error is
preferable to returning results anyway. And slowly incorporating
functions that do take into account bipartite networks would be the
way to go.

So, the rule of thumb is 'it won't work for bipartite, unless stated
otherwise'. For example, I still don't know if clusters() provides
sensible results, but following that rule, I should expect it doesn't.
Is that right?
>> 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
>
> [...]

Thanks a lot for your quick response.
Best,
- -Jose

- --
Jose Quesada, PhD.
Max Planck Institute,
Center for Adaptive Behavior and cognition,
Berlin
http://www.josequesada.name/        
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
 
iQIVAwUBSb5srGMobUVGH+HKAQLglA//WQiwX0KR2lTIXiRbM4M/OpVrGoNB+ZrR
YGNG4BVqFgGwYAJcF59GNYJGFw5WbM7uxaiIUYKhZZ1D7/94CPWpA2cq6z7a2EPO
SznCbCNSkkqxoTcdwKTd0//O0Y6gpD3yTtvhFm4ZFnre/FIFlMN4Tzkn2qLdXlMX
0tJZmiTuct32BwjEdDOXetARkk6zqwYCw/hJFTEHSlPHWSJuXYRLCFZ02EsDPkvq
T0JIqDvOiigBTTda+13eWjwqsUGZ3zJbKltDZflk1w3H/a6HEqQTZ1+oFL02E4Dn
C9DiA9WP3h51wQ/IhQl75CaIlUm/0/UE9EX/pBu07E5/qqDqm1KqHjJ7gK/LCLGm
UdQUbPtZi989Oy8RlbNmV18EprEoA/I1rUVKsA8CmRQT4uO08uH0Zq8AJye+6Mhc
I1hL839VLLRBOwhi/R1dqUJ1P4pIQ7YFV7yz1t6IJVbcb4PxPPrtvtLSy01k5Un0
lmUNDNdJTRGt8l/3phG8RG2JXjWOjmPYx14Z0OaC3dWme0qVquyXaGVQbCRP6i0M
ZE5NUw/R+EfMVRQdZDt+IqU53uZKD/1FMe6BBEJ30JvUW7xRA+VUDY+SJ7dIiQhv
JiI9BUIv1rplCxCcu7fSMHVgN8okmtFLIZfqwTfN2N+3lPJ7k6zy3hLNnGv+IS5G
lq/usAoynWM=
=IvCD
-----END PGP SIGNATURE-----