Hidden Variables in Bipartite Networks

Maksim Kitsak, Dmitri V. KrioukovarXiv 2011 · arXiv

Abstract

Bipartite networks, characterized by two distinct sets of nodes where connections only exist between sets, are ubiquitous in real-world systems ranging from consumer-product interactions to scientific collaborations. This paper presents a mathematical framework that models these networks using "hidden variables"—intrinsic node attributes that determine connection probabilities. By applying this formalism, the authors derive analytical expressions for degree distributions, clustering, and correlations, providing a rigorous method to understand how information is preserved or distorted when these networks are projected into simpler, unipartite forms.

The Challenge of Bipartite Projections

Many complex systems are naturally bipartite. Examples include researchers and the papers they publish, or molecules and the chemical reactions they participate in. A common analytical technique is to "project" these networks into a unipartite version—for instance, creating a network of researchers where a link signifies a shared publication.

Bipartite network (a) and its unipartite projections (b, c).

As illustrated in Figure 1, this projection process (or "squashing") can obscure the underlying mechanics of the system. It often creates artificial patterns, such as cliques, that do not represent direct interactions. The fundamental difficulty is that the underlying drivers of connections—the "hidden variables" like a researcher's expertise or a consumer's location—are often unobserved. This research seeks to bridge the gap between these invisible attributes and the visible network structure.

Methodology: The Hidden Variable Formalism

The authors extend the hidden variable formalism to bipartite structures through a multi-step analytical process:

  1. Attribute Assignment: Nodes in the "top" and "bottom" sets are assigned hidden variables ($\kappa$ and $\lambda$) drawn from specific probability distributions.
  2. Connection Probability: A linking function $r(\kappa, \lambda)$ defines the probability of an edge forming between nodes based on their attributes.
  3. Propagators: The authors utilize generating functions to calculate "propagators," which predict the degree distribution for nodes possessing specific traits.
  4. Analytical Derivation: This allows for the derivation of closed-form equations for key metrics, including degree distributions and the bipartite clustering coefficient ($c_B$).

The framework was validated using synthetic datasets of up to $2 \times 10^5$ nodes, comparing theoretical predictions against numerical simulations for both uncorrelated (popularity-based) and stratified (proximity-based) models.

Key Insights: Projection Preservation

A significant contribution of this work is the formalization of how topological properties "travel" through a projection.

Degree distributions $P(k)$ for the original bipartite network and its unipartite projection.

As shown in Figure 5, the authors found that if a bipartite network exhibits a power-law degree distribution, its unipartite projection typically inherits the same power-law exponent. This suggests that certain structural signatures are robust to the projection process.

Other key insights include:

  • Sparse Network Simplification: In sparse networks, the link distribution for a node with a specific trait follows a Poisson distribution, greatly simplifying the mathematical treatment.
  • Constant Clustering in Stratified Models: In models where nodes are arranged on a circle and connect based on distance, the bipartite clustering coefficient remains a constant $1/3$, regardless of network size—a sharp departure from random networks where clustering vanishes in large systems.

Results and Validation

The analytical formulas derived in the paper showed a near-perfect match with numerical simulations for degree distributions and Average Nearest Neighbor Degree (ANND). In uncorrelated networks, the bipartite clustering coefficient $c_B$ was found to scale inversely with the network size ($N$), specifically $c_B \sim N^{-\delta}$, where the decay rate $\delta$ is determined by the tail of the degree distribution.

Conclusion and Future Directions

While the framework provides elegant solutions for sparse networks, future work is needed to address dense networks where the current assumptions may not hold. Furthermore, real-world hidden spaces are likely multi-dimensional and more complex than the simple popularity or circular models tested here.

The authors highlight the "inverse problem" as the next frontier: developing methods to take a real-world network and infer the hidden attributes of its nodes. Solving this could lead to significantly more accurate recommendation engines and a deeper understanding of the latent factors driving social and biological organization.

Summary updated

Abstract

We introduce and study random bipartite networks with hidden variables. Nodes in these networks are characterized by hidden variables which control the appearance of links between node pairs. We derive analytic expressions for the degree distribution, degree correlations, the distribution of the number of common neighbors, and the bipartite clustering coefficient in these networks. We also establish the relationship between degrees of nodes in original bipartite networks and in their unipartite projections. We further demonstrate how hidden variable formalism can be applied to analyze topological properties of networks in certain bipartite network models, and verify our analytical results in numerical simulations.
BibTeX
@misc{kitsak2011hidden,
  author = {Maksim Kitsak and Dmitri V. Krioukov},
  title = {{Hidden Variables in Bipartite Networks}},
  year = {2011},
  eprint = {1104.3184},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1104.3184},
}
Figure