I'm trying to extract a connected bipartite graph Bconn from the a given incidence matrix B-

I have a matrix representing a bipartite graph - the incidence matrix B (weighted or not is unimportant). I want to extract the incidence matrix Bconn of the corresponding connected bipartite sub-graph. The incidence matrix may be rectangular. ù

One can transform the incidence matrix B into a squared adjacency matrix A, where the off-diagonal blocks are the incidence matrices (one the transpose of the other if the bi-partite graph is undirected and thus A is symmetric) - standard basic graph theory.

I would like to find a method for both directed and undirected graphs, and I do NOT want to transform the incidence into an adjacency matrix and in turn A into a graph, and then use ConnectedComponent or SubGraph, and then re-transform the graph object into a matrix: this method is not very efficient. I think that just working with matrices is faster.

I have been able to find a method for undirected NON-bipartite graph, but probably there is a even more efficient way to solve the problem and especially to find a way so to operate directly with the incidence matrix B.

My code is the following:

Sx = Dimensions[B][[1]]; Sy = Dimensions[B][[2]];

A = Join[Join[Table[0, {i, 1, Sx}, {j, 1, Sx}], B, 2],Join[B // Transpose, Table[0, {i, 1, Sy}, {j, 1, Sy}], 2]];

isnode = Position[Total[A], 0] // Reverse;

Aconn = Transpose[Delete[Transpose[Delete[A, isnode]], isnode]];

Bconn = A[[1 ;; Sx, Sy + 1, Sx + Sy]];

Of course I can do a function doing all these operations, but the point is that I'm not convinced of this algorithm, as I'm looking to something faster and that I can use directly to B.

Thanks for any suggestion/solution!!

  • $\begingroup$ Would IncidenceGraph help? It takes the incidence matrix and converts to a Graph object. $\endgroup$ – Daniel Lichtblau Jan 15 '14 at 16:37
  • $\begingroup$ @DanielLichtblau "incidence matrix" has several different and confusing meanings, unfortunately. I think in Mathematica (IncidenceMatrix and IncidenceGraph) this matrix describes the connections between edges and vertices: rows are vertices, columns are edges. Another meaning is when we describe the connections of the two kinds of vertices of a bipartite graph: rows are the first group of vertices and columns are the second group. It sounds like the OP is using the expression in the latter sense. $\endgroup$ – Szabolcs Jan 15 '14 at 21:08
  • $\begingroup$ @sam84 I am not following your question completely. Why do you want to avoid building an adjacency matrix? This is the simplest solution: it's as simple as padding your incidence matrix with zeros. And it doesn't even waste memory if you use sparse arrays. Given an incidence matrix mat, the adjacency matrix will be am = PadLeft[SparseArray[mat], {1, -1} Total@Dimensions[mat]], then use AdjacencyGraph. $\endgroup$ – Szabolcs Jan 15 '14 at 21:13
  • $\begingroup$ Regardless of your preferred graph representation you can do a BreadthFirstScan. Starting node is Blue, 1st layer is Red, 2nd layer is Blue, etc. Blue and Red define the bipartite graph. $\endgroup$ – A.G. Jan 16 '14 at 7:01
  • 1
    $\begingroup$ If you really need to work only with matrices, you could do something like this: k=1; FixedPoint[Unitize[im.(#.im)] &, ReplacePart[ConstantArray[0, Length[im]], k -> 1]]. Here im is the incidence matrix. This command will give a vector where 1s indicate nodes from the first group that are connected to node k. You can multiply the result with im again to get the nodes in the connected component from the second group. You can work with the transpose of im to start with a node from the second group. $\endgroup$ – Szabolcs Jan 21 '14 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.