Efficient Uniform Negative Edge Weights
This work provides a practical sampling algorithm for a maximum entropy edge weight model with negative weights, addressing a computational bottleneck in network analysis and related fields.
The authors propose an MCMC method to uniformly sample edge weights from a set including negative values, conditioned on the absence of negative cycles, and engineer an efficient implementation using dynamic Johnson's algorithm and bidirectional Dijkstra search.
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.