Abstract
Network metrics form a fundamental part of the network analysis toolbox. Used to quantitatively measure different aspects of the network, these metrics can give insights into the underlying network structure and function. In this work, we connect network metrics to modern probabilistic machine learning. We focus on the centrality metric, which is used a wide variety of applications from web search to gene-analysis. First, we formulate an eigenvector-based Bayesian centrality model for determining node importance. Compared to existing methods, our probabilistic model allows for the assimilation of multiple edge weight observations, the inclusion of priors and the extraction of uncertainties. To enable tractable inference, we develop a variational lower bound (VBC) that is demonstrated to be effective on a variety of networks (two synthetic and five real-world graphs). We then bridge this model to sparse Gaussian processes. The sparse variational Bayesian centrality Gaussian process (VBC-GP) learns a mapping between node attributes to latent centrality and hence, is capable of predicting centralities from node features and can potentially represent a large number of nodes using only a limited number of inducing inputs. Experiments show that the VBC-GP learns high-quality mappings and compares favorably to a two-step baseline, i.e., a full GP trained on the node attributes and pre-computed centralities. Finally, we present two case-studies using the VBC-GP: first, to ascertain relevant features in a taxi transport network and second, to distribute a limited number of vaccines to mitigate the severity of a viral outbreak.
Introduction
In network analysis, centrality metrics such as PageRank or Eigenvector centrality are essential for identifying the most influential nodes in a system. However, traditional tools typically treat the network as a static, perfectly observed ground truth. In reality, real-world graphs are often "messy," characterized by experimental noise, repeated conflicting observations, or missing connectivity data. This paper addresses these limitations by bridging the gap between traditional network science and modern probabilistic machine learning, introducing a Bayesian framework for network centrality.
Methods
Variational Bayesian Centrality (VBC)
The authors reformulate eigenvector centrality as a latent variable problem. Instead of a single deterministic score, each node’s centrality is treated as a random variable. To ensure scores remain positive (as required by the Perron-Frobenius theorem), the model employs log-normal priors. Because exact Bayesian inference is computationally expensive, a variational lower bound is derived to make the inference tractable.
VBC-Gaussian Process (VBC-GP)
The VBC-GP model links node attributes (features) to their latent centrality using a Sparse Gaussian Process. This allows the model to learn a mapping from features to centrality, enabling the prediction of importance for new nodes and the representation of massive networks using a small set of "inducing points."
This end-to-end approach optimizes the feature-to-centrality mapping simultaneously with network inference, leading to more robust results than traditional two-step "calculate then regress" methods.
Experimental Results
The models were evaluated on seven diverse networks, including synthetic random and scale-free graphs, biological connectomes (cat brain, C. elegans), social networks, and Singaporean transport data.
Key findings include:
- Robustness to Noise: VBC achieved 10–20% higher correlation with true centralities compared to standard averaging on noisy datasets.
- Predictive Accuracy: The VBC-GP successfully predicted node importance from features, outperforming full GP baselines on most real-world networks.
- Epidemiological Impact: In a simulated viral outbreak, using VBC-GP to target vaccinations for the top 30% of individuals reduced total infections by 62%, significantly outperforming random or standard baseline distributions.
- Urban Insights: In a taxi network study, the model correctly identified that retail space for sale and resident population were the primary drivers of transport hub status in Singapore.
Conclusion and Future Work
This work introduces a powerful probabilistic framework for network analysis that incorporates uncertainty and feature-based prediction as first-class citizens. While effective, the authors note that future work should address the non-convexity of the loss function, scale the model for networks with millions of nodes using stochastic variational inference, and extend the framework to capture temporal centrality dynamics.
Summary updated