Related Categories

Graph Theory Background

Bipartite Projection

A bipartite graph is a type of network graph where the nodes can be partitioned into two disjoint and independent sets, U and V. Additionally, all the edges in the network must connect node from U to a node in V.

Figure 1: An example of a bipartite network where the disjoint sets of nodes are color coded. The blue nodes, set U, and the green nodes, set V, are separated by a dashed yellow line. All the edges in the network pass through the dashed yellow line.

Suppose we want to see how the blue nodes are connected to each other by way of the green nodes. We can re-arrange the nodes to give a sense of how the blue nodes are related to each other.

Figure 2: This figure shows how the bipartite network from Figure 1 can be rearranged to give an idea of how the blue nodes are related to each other by way of the green nodes.

This second arrangement already gives some clarity as to how the blue nodes are connected to each other. A “projection” of the green nodes onto the blue nodes can be seen in the next step, where each green node is replaced by a set of edges that connect all the blue nodes that are connected to the given green node.

Figure 3: This figure shows how the rearranged bipartite graph can be converted to a homogeneous graph with edges replacing the green nodes. The graph shown on the right-hand side of the figure is the result of this example of bipartite projection.

This conversion also shows that the blue nodes ‘B’ and ‘C’ are connected in two ways. These two lines could be thought of as a single edge with twice the edge weight of the other edges. This concludes the process of bipartite projection, as we now have formed a network graph exclusively comprised of blue nodes.

N-Partite Projection

The idea of projection that was introduced in the previous section is not limited to 2 distinct sets of nodes. Here we show how the example from the previous subsection can be easily expanded to include nodes and edges from a 3 distinct set. This is an example of a 3-partite graph. Furthermore, you can see how we can follow the exact same process to get to a network graph comprised of exclusively blue nodes.

Figure 4: This figure demonstrates the concept of N-partite projection as an expansion of the ideas behind bipartite projection.

In the final graph, we can see that there is a new edge connecting ‘A’ and ‘D’ and new edges between ‘B,’ ‘C,’ and ‘E’ that tighten the existing relationship between this group of nodes. The new edges can be seen in orange.

Again, while the idea of projection has been demonstrated for bipartite and 3-partite network graphs, the idea is applicable to any sized N-partite network graphs, where “N” simply represents the number of distinct sets of nodes.