Efficient Uniform Negative Edge Weights

Abstract

We consider a maximum entropy edge weight model that allows for negative weights. Given a graph $G$ and possible weights $\mathcal{W}$ typically consisting of positive and negative values, the model selects edge weights $w\in {\mathcal{W}}^m$ uniformly at random from all weights that do not introduce a negative cycle. We propose an MCMC process and show that it converges to the required distribution. We then engineer an implementation of the process using a dynamic version of Johnson's algorithm in connection with a bidirectional Dijkstra search as well as an innovative resampling method. We empirically study the performance characteristics of these novel sampling algorithms as well as the output produced by the model.