4
$\begingroup$

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

matrix plot of the bipartite graph

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

matrix plot of the bipartite graph

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Michael E2 Apr 19 '14 at 19:41
1
$\begingroup$

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

enter image description here

enter image description here

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]]

enter image description here

$\endgroup$
3
$\begingroup$

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]

enter image description here

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]]

enter image description here

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]

enter image description here


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)
$\endgroup$
  • $\begingroup$ You can get the groupings by In[704]:= ConnectedComponents[AdjacencyGraph[1 - AdjacencyMatrix[g2]]] Out[704]= {{1, 5, 6, 7, 8}, {2, 3, 4}}. $\endgroup$ – Daniel Lichtblau Feb 4 '18 at 17:15
  • $\begingroup$ @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]. $\endgroup$ – Szabolcs Feb 4 '18 at 17:25
  • $\begingroup$ Ah. Okay, yes, this will fail in general. $\endgroup$ – Daniel Lichtblau Feb 4 '18 at 17:43
  • 1
    $\begingroup$ 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) $\endgroup$ – Daniel Lichtblau Feb 4 '18 at 22:25
  • 1
    $\begingroup$ 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...) $\endgroup$ – Daniel Lichtblau Feb 4 '18 at 23:08
1
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.