Efficient Uniform Negative Edge Weights

2024/10/30 by Lukas Geis, Geis, Lukas, Daniel Allendorf +11
Physics and Astronomy · Engineering · Computer Science · #Complex Network Analysis Techniques #Advanced Optical Network Technologies #Network Traffic and Congestion Control

paper · pdf · doi:10.48550/arxiv.2410.22717

Abstract

We consider a maximum entropy edge weight model that allows for negative weights. Given a graph G and possible weights W typically consisting of positive and negative values, the model selects edge weights w ∈ 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.

Citations

• Negative-Weight Single-Source Shortest Paths in Near-linear Time
• Depth-First Search and Linear Graph Algorithms
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Mathematical Methods of Organizing and Planning Production

Related

• Estimating parameters of a directed weighted graph model with beta-distributed edge-weights
• Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs
• Maximum entropy distributions on graphs
• Edge Probability Graph Models Beyond Edge Independency: Concepts, Analyses, and Algorithms
• Minimum Weight Random Graphs with Edge Constraints