# 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**.

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.

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.

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.

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.