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

Question

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}]
m1=AdjacencyMatrix[g1] // MatrixPlot

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"]
m2=AdjacencyMatrix[g2] // MatrixPlot

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

Answer 1

From the docs on AdjacencyMatrix:

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"]
m3 = AdjacencyMatrix[g3] // MatrixPlot

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

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

Answer 2

IGraph/M has IGBipartitePartitions for identifying the two partitions.

With your example,

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

Reorder the graph vertices:

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

MatrixPlot@AdjacencyMatrix[g3]

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)

Answer 3

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