Efficient Bipartite Projection

graph-tool
1

Dear all,

I have a bipartite graph, directed and with weightened edges. It is very
large, I believe 36k nodes and 52k edges. I am trying to make a projection
of it, but I could not find any function or way to do so with graph-tool.
Is there any way I am not aware of? If there is no current way, where would
you recommend try with such a big graph? I am currently trying to run this
on a 8gb RAM 2012 macbook pro 15` (2.2 ghz or something like that).

I started of from (1) Gephi plugin (
https://marketplace.gephi.org/plugin/multimode-networks-transformations-2/),
which after running for a couple hours almost froze my computer and output
no graph (I had to force quit it). My second attempt was (and is) on igraph
( http://igraph.org/python/doc/igraph.Graph-class.html#bipartite_projection
)

I came across this post:
http://stackoverflow.com/questions/606516/python-graph-library

And read about graph-tool and how efficient it is compared to the igraph
and networkx (which I was about to try but given up when I saw the time
table).

Thank you for your attention,

attachment.html (1.48 KB)

2

Hi,

Could you specify a particular projection?

`graph_tool.sfp_layout` does a pretty good job for a variety of layouts.
It is also easy to setup custom projection through x, y and z
propertymaps and matplotlib.

Hope this helps,

Guillaume

attachment.html (2.98 KB)

3

Bipartite projection is currently not implemented, but this is a very
easy one. Just open a ticket for it on the website and I'll include an
implementation when I have some time.

Best,
Tiago

4

Dears,

Thank you for the layout information Guillaume, this will come to use in
due time, although it wasn't really what I was after :slight_smile:

Tiago Peixoto, I opened an issue here:
https://git.skewed.de/count0/graph-tool/issues/196 linked to this
discussion.

Thank you both for the quick reply, and the interest on implementing this
feature.

Best Regards,

attachment.html (2.31 KB)

5

Dears,

Thank you for the layout information Guillaume, this will come to use in
due time, although it wasn't really what I was after :slight_smile:

Tiago Peixoto, I opened an issue here:
https://git.skewed.de/count0/graph-tool/issues/196 linked to this
discussion.

Thank you both for the quick reply, and the interest on implementing this
feature.

Best Regards,

Carlos A.
http://carlosandrade.co

attachment.html (3 KB)

6

I thought about bringing this discussion here from my message on igraph
mailing list since it relates to this feature:

It seems to me (I may be badly mistaken) that current bipartite projection
by weighted graphs do not account for the original graph weights.

To contextualize, here a bad hand draw example:
https://www.dropbox.com/s/fl69kekipqksd4i/Screenshot%202014-12-01%2012.51.22.png?dl=0

I am interested on both values (red circle and orange square), however
igraph documentation only accounts (or at least suggest to on the
documentation) for the orange one:
http://igraph.org/python/doc/igraph.Graph-class.html#bipartite_projection

I checked networkX as well but I couldn't find anything about weighted
bipartite graph
projections:
http://networkx.lanl.gov/archive/networkx-1.6/_modules/
<http://networkx.lanl.gov/archive/networkx-1.6/_modules/networkx/algorithms/bipartite/projection.html&gt;
networkx/algorithms/bipartite/projection.html
<http://networkx.lanl.gov/archive/networkx-1.6/_modules/networkx/algorithms/bipartite/projection.html&gt;

Is it possible for this to be taken into account when the posted 'issue' is
tackled?

Thank you,

Carlos A.

attachment.html (5.46 KB)

7

Hi,

Dears,

Thank you for the layout information Guillaume,
this will come to use in due time, although it wasn't really what I
was after :slight_smile:

Yes I guess I missed the "Bipartite" part of the message :stuck_out_tongue:

G.

attachment.html (5.09 KB)

8

Admin,

Is the feature to get the bipartite projection implemented now in graph
tools? If yes, Can you please provide the link as I am unable to find it?
Would be of great help.

Thanks in advance,
Aditya

9

Not yet. If you want to be informed when it is, follow this issue:

    https://git.skewed.de/count0/graph-tool/issues/196