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.

A classical problem in random number generation is the sampling of elements from a given discrete distribution. Formally, given a set of indices S = {1, …,n} and sequence of weights w1; …, wn 2 ℝ+, the task is to provide samples from S with distribution p(i) = Wi/W where . A commonly accepted solution is Walker's Alias Table, which allows for each sample to be drawn in constant time. However, some applications correspond to a dynamic setting, where elements are inserted or removed, or weights change over time. Here, the Alias Table is not efficient, as it needs to be re-built whenever the underlying distribution changes.

Preferential attachment lies at the heart of many network models aiming to replicate features of real world networks. To simulate the attachment process, conduct statistical tests, or obtain input data for benchmarks, efficient algorithms are required that are capable of generating large graphs according to these models. Existing graph generators are optimized for the most simple model, where new nodes that arrive in the network are connected to earlier nodes with a probability P(h) ∝ d that depends linearly on the degree d of the earlier node h. Yet, some networks are better explained by a more general attachment probability P(h) ∝ f (d) for some function f : ℕ → ℝ. Here, the polynomial case f(d) = dα where α ∈ ℝ >0 is of particular interest. In this paper, we present efficient algorithms that generate graphs according to the more general models. We first design a simple yet optimal sequential algorithm for the polynomial model. We then parallelize the algorithm by identifying batches of independent samples and obtain a near-optimal speedup when adding many nodes. In addition, we present an I/O-efficient algorithm that can even be used for the fully general model. To showcase the efficiency and scalability of our algorithms, we conduct an experimental study and compare their performance to existing solutions. Funding This work was supported by the Deutsche Forschungsgemeinschaft (DFG) under grant ME 2088/5-1 (FOR 2975 — Algorithms, Dynamics, and Information Flow in Networks). Supplemental material The internal memory algorithms are maintained at https://github.com/massive-graphs/nonlinear-preferential-attachment. The implementation of the dynamic weighted sampling data structure of [28] is independently maintained as the Rust crate https://crates.io/crates/dynamic-weighted-index. The external memory algorithms are available at https://github.com/massive-graphs/extmem-nlpa. An archive containing the frozen source code of all experiments and most of the raw data collected can be found on https://zenodo.org/record/7318118. * Link to full version: https://arxiv.org/abs/2211.06884

We consider the following common network analysis problem: given a degree sequence d = (d1,…, dn) ∈ ℕn return a uniform sample from the ensemble of all simple graphs with matching degrees. In practice, the problem is typically solved using Markov Chain Monte Carlo approaches, such as Edge-Switching or Curveball, even if no practical useful rigorous bounds are known on their mixing times. In contrast, Arman et al. sketch INC-PoWERLAW, a novel and much more involved algorithm capable of generating graphs for power-law bounded degree sequences with γ ⪆ 2.88 in expected linear time. For the first time, we give a complete description of the algorithm and add novel switchings. To the best of our knowledge, our open-source implementation of INC-POWERLAW is the first practical generator with rigorous uniformity guarantees for the aforementioned degree sequences. In an empirical investigation, we find that for small average-degrees INC-POWERLAW is very efficient and generates graphs with one million nodes in less than a second. For larger average-degrees, parallelism can partially mitigate the increased running-time.

The uniform sampling of simple graphs matching a prescribed degree sequence is an important tool in network science, e.g., to construct graph generators or null-models. Here, the Edge Switching Markov Chain (ES-MC) is a common choice. Given an arbitrary simple graph with the required degree sequence, ES-MC carries out a large number of small changes involving at most four edges to eventually obtain a uniform sample. In practice, reasonably short runs efficiently yield approximate uniform samples. We first engineer a simple sequential ES-MC implementation representing the graph in a hash-set. Despite its simplicity and to the best of our knowledge, our implementation significantly outperforms all openly available solutions. Secondly, we propose the Global Edge Switching Markov Chain (G-ES-MC) and show that it, too, converges to a uni-form distribution. We provide empirical evidence that G-ES-MC requires not more switches than ES-MC (and often fewer). Thirdly, we engineer shared-memory parallel algorithms for ES-MC and G-ES-MC; we find that they benefit from the easier dependency structure of the G-ES-MC. In an empirical evaluation, we demonstrate the scalability of our implementations.