# How to sort the adjecency matrix of bipartite graph so to have two off-diagonal blocks

In a bipartite graphs there are two class of nodes, say A and B. Each node of class A may interact only with nodes of the class B, and viceversa. The corresponding adjecency matrix is thus composed by two off-diagonal blocks (if you sort the vertices in an appropriate way).

I realize that when working with adjecency matrix for a given bipartite graphs, sometimes I get the desired order in the adjecency matrix, and thus if I plot it, it is formed by two off-diagonal blocks:

g1=CompleteGraph[{5,3}]


However, sometimes if I plot the adjecency matrix directly from the bipartite graphs, now it is not in the desired order:

l2 = CompleteGraph[{5, 3}] // EdgeList;
weights = RandomReal[{0.5, 2}, Length[l2]];
g2 = Graph[l2, EdgeWeight -> weights, GraphLayout -> "BipartiteEmbedding"]


I'm trying to find a way to automatically sort m2 so to tranform it in a two off-diagonal blocks matrix.

• Note that Dropbox links do not return images, but images embedded in HTML. You need to upload the images to the SE host via the image button above the edit window. – Michael E2 Apr 19 '14 at 19:41

Rows and columns of the adjacency matrix follow the order given by VertexList

And from the docs on VertexList:

Vertices are taken in the order they appear in the list of edges.

Thus, you have

{VertexList[g1], VertexList[g2]}
(* {{1, 2, 3, 4, 5, 6, 7, 8}, {1, 6, 7, 8, 2, 3, 4, 5}} *)


So, you can give an explicit list of vertices as the first argument of Graph to keep the adjacency matrix unchanged:

l2 = CompleteGraph[{5, 3}] // EdgeList;
v2 = CompleteGraph[{5, 3}] // VertexList;
weights = RandomReal[{0.5, 2}, Length[l2]];
g3 = Graph[v2, l2, EdgeWeight -> weights, GraphLayout -> "BipartiteEmbedding"]


Update: Alternatively, you can re-arrange the rows and columns of AdjacencyMatrix[g2] ex post using Ordering as in @Wouters answer:

g2 = Graph[l2, EdgeWeight -> weights,  GraphLayout -> "BipartiteEmbedding"];
m2b = m2[[Ordering[VertexList[g2]], Ordering[VertexList[g2]]]];
Row[ MatrixPlot[#, ImageSize -> 300] & /@ {m2, m2b}, Spacer[5]]


IGraph/M has IGBipartitePartitions for identifying the two partitions.

IGBipartitePartitions[g2]
(* {{1, 2, 3, 4, 5}, {6, 7, 8}} *)


Reorder the graph vertices:

g3 = IGReorderVertices[Flatten@IGBipartitePartitions[g2], g2];



If you just want to visualize the adjacency matrix (with or without weights), but you do not need to compute with it, do both reordering and visualization in one step using IGAdjacencyMatrixPlot.

IGAdjacencyMatrixPlot[g2, Flatten@IGBipartitePartitions[g2]]


This function is quite flexible. Suppose you don't want to show weights and you don't want column labels rotated.

IGAdjacencyMatrixPlot[g2, Flatten@IGBipartitePartitions[g2],
EdgeWeight -> None, "RotateColumnLabels" -> False]


The following is a pure-Mathematica implementation of a function that splits a bipartite graph's vertices into two partitions. The idea is that the partition that a vertex belongs to depends on whether its distance from some chosen vertex is odd or even. If the graph is not connected, we need to split each component of the graph into partitions separately, then merge the results together.

singleComponentBipartitePartitions[graph_] :=
GroupBy[
Transpose@{VertexList[graph], Mod[GraphDistance[graph, First@VertexList[graph]], 2]},
Last -> First
]

bipartitePartitions[graph_?BipartiteGraphQ] :=
Module[{ug},
(* First we convert the graph to undirected and make sure that
all edge weights are discarded so that they do not affect
the graph distance calculation—should ConnectedGraphComponents start
preserving them in a future version. *)
ug = Graph[VertexList[graph], EdgeList@UndirectedGraph[graph]];
Values@Merge[
singleComponentBipartitePartitions /@ ConnectedGraphComponents[ug],
Catenate
]
]

call : bipartitePartitions[expr_] :=
(Message[bipartitePartitions::inv, HoldForm@OutputForm[call], OutputForm[expr], "bipartite graph"];
\$Failed)

• You can get the groupings by In[704]:= ConnectedComponents[AdjacencyGraph[1 - AdjacencyMatrix[g2]]] Out[704]= {{1, 5, 6, 7, 8}, {2, 3, 4}}. – Daniel Lichtblau Feb 4 '18 at 17:15
• @DanielLichtblau That works in this particular case, but it does not work for any bipartite graph. Consider e.g. CycleGraph[6], which is bipartite. AdjacencyGraph[1 - AdjacencyMatrix[g2]] is (almost) the same as GraphComplement[g2]. – Szabolcs Feb 4 '18 at 17:25
• Ah. Okay, yes, this will fail in general. – Daniel Lichtblau Feb 4 '18 at 17:43
• To be clear: I have no issue with the iGraph/M package*, the motivations for writing it, or use of it in MSE responses. I was commenting on that ornate, but probably very efficient, Mathematica snippet for reordering bipartite graph vertices. (Footnote in next comment) – Daniel Lichtblau Feb 4 '18 at 22:25
• I hd missed your question. Yes, the edited version is an improvement for readability. Now upvoted (I guess I forgot to do that several hours ago...) – Daniel Lichtblau Feb 4 '18 at 23:08

maybe Map[Part[#,Ordering[First[Normal[m2]]]]&,Normal[m2],{0,1}]` ?