concept bipartite graph in category graphs
This is an excerpt from Manning's book Graph Powered Machine Learning MEAP V08.
In this graph representation, on the left side there are all the users and on the left side all the items. The relationships goes only from nodes in one subset to nodes in the other subset, whereas no relationships occur between nodes of the same set. This is an example of a bipartite graph.
More formally, a bipartite graph or (bigraph) is a special type of graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V or viceversa. Vertex sets U and V are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles [Reinhard Diestel, 2017]. In graph theory, a cycle is a path of edges and vertices wherein a vertex is reachable from itself. The path length is the number of vertices in the path. So in a bipartite graph any cycle has an even number of vertices.
People’s preferences for things, such as for certain products sold by a retailer, can be represented as graphs in recommendation networks [Newman, 2010] and used in recommender systems. The fundamental and most common representation of a recommendation network is a bipartite graph or bigraph.
Figure 5.4 A generic bipartite graph
In generic terms, a bipartite graph is a network whose nodes can be divided into two disjoint sets U and V such that each link connects a U-node (i.e. a node from the U set) to a V-node (i.e. a node from the V set).[35] To make it simpler, if we color the U-nodes green and the V-nodes purple, then each link must connect nodes of different colors [Barabási and Pósfai, 2016]. —— Figure 5.4