[igraph] working with bipartite graphs

[Jose Quesada]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
 
Hi All,

I'm using igraph 0.6 just because I cannot find any other library that
could do large graphs and have bipartite functions.

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.

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.

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? 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.

Thanks for this great package, I hope the release of 0.6 will open new
untapped possibilities for bipartite networks.

Best,
- -Jose


library(igraph)
library(Matrix)
# create an incidence matrix
a = Matrix(ifelse(runif(1000)>.8, 1, 0), 100, 10)
#
g = graph.incidence(a, directed=T, mode="out")
summary(g)
p = page.rank(g)
V(g)$prank = p$vector

# now remove type attribute for vertex; copy graph first
g2 = g
g2 = remove.vertex.attribute(g2, "type")
summary(g2)
p2 = page.rank(g2)
V(g2)$prank2 = p2$vector
summary(g2)
is.bipartite(g2) # even after removing vertex attribute type, graph is
bipartite

any(is.na(ifelse(V(g2)$prank==V(g2)$prank2, 1, NA)))
# FALSE; pagerank is unaffected by removing vertex attribute type

- --
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
 
iQIVAwUBSb5JF2MobUVGH+HKAQJYXQ//ZI4FARktmOovpz1qMncR3ojU+nYiPwEY
9BM008E1WI4DRdblQHFY1ii6emu4jeIRuJTFxDG+CUPYy18p4C33iffQALZnu9KR
DUXe5rlLrOrCapzloCePXktSqSXsOonETsLxfT8S7ldiqBwvGYJxR7t9kauUt0Px
Y0mO5YzMsFV3Q+mjhfU+/a07hsogflPep5uosmVqUXcr1XvaVkUvvvqS3Eir62m9
SLse1UJifiHUfPziaYRMGcwA9RQPqpfnzfjo8bd9Eu9wqCdeEYNgYi9qezK4xzDP
BCX7gt+n2rts25EKdRe4+P87vWFg+HLdNWCDelty1gn3D9rAiCR//LKB/53gMd9e
qgL46tSKid4bMXdmC/zNYf3eb2puKniCvbYTmJT6Uu2HNBK+djAOcTi7zj57LSgz
u7+JjdRhakBYx7K2IjSYqXHIsJBwj6D+PVxuBZRI11Fu8CBYvT8OlmWc9l9RybbA
6eLpG1KOKMItkMCWu2JaCL07dD5wbQTPGW63J3HZVoVqNIzD6k8dE0xHN8a1gbrX
pPgUa+RzkzKYaTY4wPcW044xsitJKXMArrMzHdGfl353hiYjV1C9Qp581tFlv/Vj
Rs/PtvQtdCEa66rPZDEWi+QGH0pnPytIOQ+N0QB/y+HkS5PWhrK4ZMM3jWOQ6Bx3
yK4i69A9T/8=
=hdRC
-----END PGP SIGNATURE-----