Hyperbolic models can reproduce the heavy-tailed degree distribution, high clustering, and hierarchical structure of empirical networks. Current algorithms for finding the hyperbolic coordinates of networks, however, do not quantify uncertainty in the inferred coordinates. We present BIGUE, a Markov chain Monte Carlo (MCMC) algorithm that samples the posterior distribution of a Bayesian hyperbolic random graph model. We show that combining random walk and random cluster transformations significantly improves mixing compared to the commonly used and state-of-the-art dynamic Hamiltonian Monte Carlo algorithm. Using this algorithm, we also provide evidence that the posterior distribution cannot be approximated by a multivariate normal distribution, thereby justifying the use of MCMC to quantify the uncertainty of the inferred parameters.

We study the problem of clustering networks whose nodes have imputed or physical positions in a single dimension, for example prestige hierarchies or the similarity dimension of hyperbolic embeddings. Existing algorithms, such as the critical gap method and other greedy strategies, only offer approximate solutions to this problem. Here, we introduce a dynamic programming approach that returns provably optimal solutions in polynomial time -- O(n^2) steps -- for a broad class of clustering objectives. We demonstrate the algorithm through applications to synthetic and empirical networks and show that it outperforms existing heuristics by a significant margin, with a similar execution time.

Département de Physique, de Génie Physique, et d'Optique, Université Laval, Québec (Québec), Canada G1V 0A6 and Centre interdisciplinaire en modélisation mathématique, Université Laval, Québec (Québec), Canada G1V 0A6 (Dated: June 16, 2020) Forecasting the evolution of contagion dynamics is still an open problem to which mechanistic models only offer a partial answer. To remain mathematically and/or computationally tractable, these models must rely on simplifying assumptions, thereby limiting the quantitative accuracy of their predictions and the complexity of the dynamics they can model. Here, we propose a complementary approach based on deep learning where the effective local mechanisms governing a dynamic are learned automatically from time series data. Our graph neural network architecture makes very few assumptions about the dynamics, and we demonstrate its accuracy using stochastic contagion dynamics of increasing complexity on static and temporal networks. By allowing simulations on arbitrary network structures, our approach makes it possible to explore the properties of the learned dynamics beyond the training data. Our results demonstrate how deep learning offers a new and complementary perspective to build effective models of contagion dynamics on networks. Our capacity to prevent or contain outbreaks of infectious tasks, making them prime candidates to tackle several diseases is directly linked to our ability to accurately model challenges of contagion dynamics modeling. Since the seminal work of Kermack and Here, we demonstrate how deep learning can be used to McKendrick almost a century ago [1], a variety of models build effective models of stochastic contagion dynamics taking incorporating ever more sophisticated contagion mechanisms place on complex networks. Instead of constructing a have been proposed, studied and used [2-5].