Bayesian one-mode projection for dynamic bipartite graphs

Ioannis Psorakis, Iead Rezek, Zach Frankel, Stephen J. RobertsarXiv 2012 · OpenReview

Abstract

We propose a Bayesian methodology for one-mode projecting a bipartite network that is being observed across a series of discrete time steps. The resulting one mode network captures the uncertainty over the presence/absence of each link and provides a probability distribution over its possible weight values. Additionally, the incorporation of prior knowledge over previous states makes the resulting network less sensitive to noise and missing observations that usually take place during the data collection process. The methodology consists of computationally inexpensive update rules and is scalable to large problems, via an appropriate distributed implementation.

Introduction

Bipartite networks—where connections only exist between two distinct sets of nodes, such as shoppers and products—are ubiquitous. To analyze relationships between nodes of the same type (e.g., finding similar shoppers), researchers perform a "one-mode projection." The standard approach typically involves counting shared targets (co-occurrences). However, this method is flawed: it fails to account for "gregarious" target nodes that connect to many sources by chance, and it produces noisy point estimates that ignore temporal context and uncertainty.

Bayesian Methodology

The authors propose a generative probabilistic model that treats observed co-occurrences as draws from a Binomial distribution.

Plate notation of the proposed Bayesian model, showing the relationship between the latent attraction coefficient $\pi_{ij}$, opportunities $x_{ij}$, and observed weights $w_{ij}$.
  • The Likelihood: The number of co-occurrences $w_{ij}$ depends on the number of "opportunities" $x_{ij}$ (total unique targets connected to by either node $i$ or $j$) and a latent "attraction coefficient" $\pi_{ij} \in [0, 1]$.
  • The Prior: A Beta distribution prior is placed on $\pi_{ij}$.
  • The Update: Due to the conjugacy of Beta and Binomial distributions, updating the model as new snapshots arrive is computationally trivial. The model adds new co-occurrences to the $\alpha$ parameter and missed opportunities to the $\beta$ parameter.

To handle non-stationary environments where network structure changes abruptly, a mixing coefficient $\kappa$ is introduced to decay the weight of past observations, allowing the model to "forget" obsolete data.

Key Results and Insights

The model was evaluated using an artificial dataset of noisy bipartite networks over 100 to 200 time steps.

Analysis of link presence between nodes 1 and 2, showing (a) posterior density, (b) expected attraction coefficient, and (c) observed vs. expected link weights across time steps.
  • Natural Penalty for Gregariousness: By factoring in total opportunities ($x_{ij}$), the model downplays coincidental overlaps caused by universally popular nodes. If a node connects to thousands of targets, a few shared connections result in a low inferred attraction coefficient.
  • Noise Smoothing and Uncertainty: The Bayesian framework successfully smooths highly fluctuating, noisy observations into stable expected link weights. Instead of a single value, it provides a full probability distribution that sharpens as more data is collected, quantifying the projection's confidence.
  • Changepoint Responsiveness: While standard Bayesian updates can be conservative, the inclusion of the mixing coefficient $\kappa$ allows the model to track new network topologies quickly after a structural shift.

Conclusion

This Bayesian approach offers a robust and scalable alternative to heuristic one-mode projection methods. By modeling the underlying generative process, it naturally handles noise, penalizes coincidental connections, and provides a principled measure of uncertainty. Future work will focus on large-scale applications in financial networks and automating the detection of structural changepoints.

Summary updated

Abstract

We propose a Bayesian methodology for one-mode projecting a bipartite network that is being observed across a series of discrete time steps. The resulting one mode network captures the uncertainty over the presence/absence of each link and provides a probability distribution over its possible weight values. Additionally, the incorporation of prior knowledge over previous states makes the resulting network less sensitive to noise and missing observations that usually take place during the data collection process. The methodology consists of computationally inexpensive update rules and is scalable to large problems, via an appropriate distributed implementation.
BibTeX
@misc{psorakis2012bayesian,
  author = {Ioannis Psorakis and Iead Rezek and Zach Frankel and Stephen J. Roberts},
  title = {{Bayesian one-mode projection for dynamic bipartite graphs}},
  year = {2012},
  eprint = {1212.2767},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1212.2767},
}
Figure