Bipartite graph
A bipartite graph is a graph whose vertices can be partitioned into two disjoint sets, with edges only between the sets.
Graph Algorithms for Data Science
A bipartite graph is a graph whose nodes are divided into two types, with edges connecting nodes across the two types rather than within the same type.
- How it is used
- Models interactions between two entity types to infer similarity, recommendations, segments, or co-occurrence networks.
- How deep it goes
- Defines the two-set structure, then develops modeling, projection, Jaccard scoring, and Graph Data Science orientation controls.
- Examples
- Uses users and items, users and movies, tweets and hashtags, product baskets, and users listening to musical genres.
- What you can do after
- Apply it via Cypher and Graph Data Science to project interaction networks and evaluate shared-neighbor similarity.
Read how Graph Algorithms for Data Science explains bipartite graph →
Graph Neural Networks in Action
A bipartite graph is a graph whose nodes are partitioned into subsets and whose edges connect nodes in different subsets rather than within the same subset.
- How it is used
- Models cross-set relationships, particularly pin–board connections used for recommendations.
- How deep it goes
- Defines the two-set edge rule and illustrates an application, but does not give a bipartite-graph implementation.
- Examples
- Uses pins and boards, including pins shared across boards, to illustrate permitted edges.
- What you can do after
- Evaluate/understand whether a two-set dataset satisfies the bipartite edge constraint before using it in a graph pipeline.
Read how Graph Neural Networks in Action explains bipartite graph →
Advanced Algorithms and Data Structures
A bipartite graph is a graph whose vertices can be partitioned into two groups with edges only between the groups; in this section the graph is also required to be connected.
- How it is used
- Uses two-color partitioning to test graphs and support recognition of K₃,₃ during planarity testing.
- How deep it goes
- Defines partitions and complete variants, then gives a BFS-based coloring procedure that returns partitions but omits running-time analysis.
- Examples
- Uses K₃,₃, red-and-blue vertex coloring, adjacency lists, queues, and contrasting bipartite and non-bipartite diagrams.
- What you can do after
- Diagnose bipartiteness with BFS coloring and recover the two vertex partitions for a connected graph.
Read how Advanced Algorithms and Data Structures explains bipartite graph →
Related concepts
- graphkind of · A graph is a mathematical structure consisting of vertices connected by edges that represent relationships or connections.
- network projectionused by · Network projection is the transformation of a multipartite graph into a graph containing one selected node type by inferring connections through shared neighbors.
- graph coloringequivalent to · Graph coloring is the assignment of colors to graph elements subject to constraints, such as requiring adjacent vertices to have different colors.
- co-occurrence networkproduces · A co-occurrence network is a graph whose entities are connected when they appear together in a shared context.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.