Most network models assume one type of node connected to similar nodes. But many real systems involve two distinct types of entities connected only across types—never within: actors connect to movies they appeared in, not to other actors directly. Patients connect to hospitals they visited, not to other patients. Genes connect to diseases they're associated with. These are bipartite networks—two-mode systems where edges only connect nodes of different types—and they require specialized analysis that standard network methods can't fully capture.
Structure of Bipartite Graphs
A bipartite graph has two disjoint node sets U and V, with edges only between U and V (never within U or V). The bipartite adjacency matrix B has rows indexed by U-nodes and columns by V-nodes: B_{ij} = 1 if u_i connects to v_j. The standard adjacency matrix would be: [[0, B], [B^T, 0]]—a block structure. Many standard graph theorems have bipartite analogs: König's theorem (maximum matching = minimum vertex cover), the bipartite analogue of Hall's marriage theorem, and bipartite-specific random graph models. Detecting bipartiteness in a graph is equivalent to 2-colorability, checkable in linear time.
One-Mode Projections
Bipartite networks are often analyzed through projections onto one mode. The U-projection connects two U-nodes if they share at least one common V-neighbor: two actors are connected if they appeared in the same movie. The U-projection adjacency matrix is P_U = B·B^T, where (P_U)_{ij} counts shared V-neighbors. Weighted projections count the number of shared neighbors rather than just their existence. Projections reduce dimensionality but lose information—the same U-projection can arise from different bipartite structures, and projection can create spurious high-degree hubs from popular V-nodes.
The Degree Distribution
In bipartite networks, both node sets have their own degree distributions. In actor-movie networks, degree of an actor (number of movies) and degree of a movie (number of actors) are independently distributed. The relationship between the two distributions is constrained: the sum of U-degrees must equal the sum of V-degrees (both equal the number of edges). This constraint creates correlations in the projection: high-degree V-nodes (blockbuster movies with many actors) create apparent hubs in the U-projection that reflect the V-degree distribution, not genuine social clustering among actors.
Nestedness and Modularity
Two structural patterns are particularly important in bipartite networks. Nestedness: specialists (few connections) tend to connect to subsets of the neighbors of generalists (many connections)—common in mutualistic ecological networks (plants and pollinators). Modularity in bipartite networks: distinct groups of U-nodes connect preferentially to distinct groups of V-nodes, creating a block-diagonal structure in B. Detecting these patterns requires adaptations of standard community detection methods to bipartite structure. The BRIM algorithm maximizes a bipartite-specific modularity function efficiently.
Applications: Recommendation Systems
Recommendation systems are naturally bipartite: users connect to items they have rated or purchased. Collaborative filtering exploits this structure: recommend items to user u that were highly rated by users similar to u in the bipartite graph. User similarity is measured through the U-projection weighted by shared item interactions. Matrix factorization decomposes the bipartite adjacency matrix B ≈ UV^T into user and item latent factor matrices, capturing the underlying preferences that explain observed interactions. This approach powers Netflix, Spotify, and Amazon recommendations, handling millions of users and items at scale.
Conclusion
Bipartite networks capture the two-mode structure that characterizes a wide class of real systems—affiliation networks, ecological webs, recommendation systems, gene-disease associations. Standard network methods applied naively to projections can produce misleading results; methods designed for bipartite structure—bipartite modularity, nestedness analysis, matrix factorization—extract more accurate and meaningful information. As more relational datasets are recognized as inherently two-mode, bipartite network analysis becomes increasingly essential to network science's practical toolkit.