Support bipartite networks

[Gábor Csárdi]

First I need to find a way to represent them. Basically you need to use attributes, there is no other way. But that means that at the C level they will look quite nasty, for every function that deals with bipartite networks, there will be an extra argument that gives the vertex types.

[Gábor Csárdi (gabor.csardi)]

Ok, first function added, creates a full bipartite graph. Not much, but a start....

[Gábor Csárdi (gabor.csardi)]

Other functions to write:
- create a projection of a bipartite graph.
- create an arbitrary bipartite graph, by giving the vertex types explicitly.
- find the vertex types in a bipartite graph.
- community structure detection: http://www.pubmedcentral.nih.gov/articlerender.fcgi?tool=pubmed&pubmedid=17930301

[Gábor Csárdi (gabor.csardi)]

Projection is done.

[Gábor Csárdi (gabor.csardi)]

igraph_create_bipartite added, creates a graph and checks that it is bipartite. In R it also adds the 'type' vertex attribute.

[Gábor Csárdi (gabor.csardi)]

We also need an igraph_incidence (graph.incidence) function that creates a graph from an incidence matrix.
Another function (igraph_get_incidence and get.incidence) should return the incidence matrix of a bipartite graph.

[Gábor Csárdi (gabor.csardi)]

igraph_incidence is (almost) finished. The R interface needs an argument to add the matrix elements as edge weights.

[Gábor Csárdi (gabor.csardi)]

OK, graph.incidence can create a weighed graph now. We should also handle sparse matrices, that is next.

[Gábor Csárdi (gabor.csardi)]

OK, sparse matrix support added to graph.incidence, now I'll do igraph_get_incidence and get.incidence).

[Gábor Csárdi (gabor.csardi)]

igraph_get_incidence added. The R version needs: 1) sparse graph support, 2) weight support, 3) documentation.

[Gábor Csárdi (gabor.csardi)]

igraph_get_incidence and get.incidence are done.

[Gábor Csárdi (gabor.csardi)]

I am seriously thinking about changing the 'bool' type vectors to 'char'. That way we could have 'NA' at least.

[Gábor Csárdi (gabor.csardi)]

More TODO:
 1) add a function that just calculates how many edges would be in the bipartite projections.
 2) add warnings to all functions that should work differently on bipartite networks, but they don't.

[Gábor Csárdi (gabor.csardi)]

OK, I have added a function that calculates the number of vertices & edges in the bipartite projections.

[nolodie (saxman-umich)]

I've just started to use the igraph R bipartite graph support, which is working great to some extent, but I and am having a bit of difficulty in some areas.

After running the following code to get two one-mode graphs, I seem to lose the node names in the resulting graphs, and I don't see any edge weights.

graph = graph.data.frame( adjlist, directed = FALSE )
V( graph )$type <- is.bipartite( graph )$type
proj <- bipartite.projection( graph )
summary( proj[[1]] )

Vertices: 12
Edges: 52
Directed: FALSE
No graph attributes.
No vertex attributes.
No edge attributes.

I can copy the names from the original graph, but I can't reproduce the weights. Am I overlooking something?

[Gábor Csárdi (gabor.csardi)]

Yes, vertex attributes should be kept, this is being implemented currently. It is theoretically easy, but the attribute handler interface needs an extension, that is why it takes long.

The edge attributes are more problematic, because the projection has edges that correspond to many edges in the original graph. How would you define the edge weights of the edges in the projection graphs? I do not know any natural definition. You can certainly come up with many sensible definitions, but these typically require a very flexible attribute handler. Which we don't have.

[nolodie (saxman-umich)]

I'm really happy to see bipartite network support being added. Most network tools & APIs have only rudimentary support at best.

The following seems to work for me for copying the vertex names.

a <- 0
b <- 0
for ( i in 0:( length( V( graph ) ) - 1 ) ) {
 if ( V( graph )[ i ]$type ) {
  V( part[[2]] )[ a ]$name <- V( graph )[ i ]$name
  a <- a + 1
 } else {
  V( part[[1]] )[ b ]$name <- V( graph )[ i ]$name
  b <- b + 1
 }
}

The only weighting that I'd propose to be "natural" would be the number of shared nodes, from multiplying a network's adjacency matrix by it's transpose. I'll post a reference if I can dig one up. I certainly agree, however, there are a number of ways to calculate weights, especially normalized ones (e.g. Jaccard Index), so perhaps it's outside of the scope of igraph as an API.

[Gábor Csárdi (gabor.csardi)]

This was already added recently (if I understand you correctly), see
http://lists.gnu.org/archive/html/igraph-help/2009-11/msg00240.html

That thread also shows a simpler way to keep the vertex attributes.

[Gábor Csárdi (gabor.csardi)]

See the remaining things to do here:
https://blueprints.launchpad.net/igraph/+spec/bipartite-graphs-in-r

[Gábor Csárdi (gabor.csardi)]

The development of igraph has moved to github, so please do not comment on this bug here. You are of course welcome to comment on github, here:
https://github.com/igraph/igraph/issues/21