Given a graph \(G = (V,\!E)\) with \(n\) vertices and \(m\) edges, the Dominating Set problem asks for a set \(\mathcal{D} \subseteq V\) of minimal cardinality such that every vertex either is in \(D\) or adjacent to a member of \(D\). Although there is little hope for a kernelization algorithm on general graphs due to the W[2]-hardness of Dominating Set, data reduction rules are extensively used in practice.

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 graph is called a $(k,ρ)$-graph iff every node can reach $ρ$ of its nearest neighbors in at most k hops. This property proved useful in the analysis and design of parallel shortest-path algorithms. Any graph can be transformed into a $(k,ρ)$-graph by adding shortcuts. Formally, the $(k,ρ)$-Minimum-Shortcut problem asks to find an appropriate shortcut set of minimal cardinality. We show that the $(k,ρ)$-Minimum-Shortcut problem is NP-complete in the practical regime of $k \ge 3$ and $ρ= Θ(n^ε)$ for $ε> 0$. With a related construction, we bound the approximation factor of known $(k,ρ)$-Minimum-Shortcut problem heuristics from below and propose algorithmic countermeasures improving the approximation quality. Further, we describe an integer linear problem (ILP) solving the $(k,ρ)$-Minimum-Shortcut problem optimally. Finally, we compare the practical performance and quality of all algorithms in an empirical campaign.

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.

We empirically investigate algorithms for solving Connected Components in the external memory model. In particular, we study whether the randomized O(Sort(E)) algorithm by Karger, Klein, and Tarjan can be implemented to compete with practically promising and simpler algorithms having only slightly worse theoretical cost, namely Borůvka’s algorithm and the algorithm by Sibeyn and collaborators. For all algorithms, we develop and test a number of tuning options. Our experiments are executed on a large set of different graph classes including random graphs, grids, geometric graphs, and hyperbolic graphs. Among our findings are: The Sibeyn algorithm is a very strong contender due to its simplicity and due to an added degree of freedom in its internal workings when used in the Connected Components setting. With the right tunings, the Karger-Klein-Tarjan algorithm can be implemented to be competitive in many cases. Higher graph density seems to benefit Karger-Klein-Tarjan relative to Sibeyn. Borůvka’s algorithm is not competitive with the two others.

We consider the efficient simulation of population protocols. In the population model, we are given a system of n agents modeled as identical finite-state machines. In each step, two agents are selected uniformly at random to interact by updating their states according to a common transition function. We empirically and analytically analyze two classes of simulators for this model. First, we consider sequential simulators executing one interaction after the other. Key to the performance of these simulators is the data structure storing the agents' states. For our analysis, we consider plain arrays, binary search trees, and a novel Dynamic Alias Table data structure. Secondly, we consider batch processing to efficiently update the states of multiple independent agents in one step. For many protocols considered in literature, our simulator requires amortized sub-constant time per interaction and is fast in practice: given a fixed time budget, the implementation of our batched simulator is able to simulate population protocols several orders of magnitude larger compared to the sequential competitors, and can carry out 2^50 interactions among the same number of agents in less than 400s.

We initiate a study of algorithms with a focus on the computational complexity of individual elements, and introduce the fragile complexity of comparison-based algorithms as the maximal number of comparisons any individual element takes part in. We give a number of upper and lower bounds on the fragile complexity for fundamental problems, including Minimum, Selection, Sorting and Heap Construction. The results include both deterministic and randomized upper and lower bounds, and demonstrate a separation between the two settings for a number of problems. The depth of a comparator network is a straight-forward upper bound on the worst case fragile complexity of the corresponding fragile algorithm. We prove that fragile complexity is a different and strictly easier property than the depth of comparator networks, in the sense that for some problems a fragile complexity equal to the best network depth can be achieved with less total work and that with randomization, even a lower fragile complexity is possible.

Hyperbolic random graphs (HRG) and geometric inhomogeneous random graphs (GIRG) are two similar generative network models that were designed to resemble complex real world networks. In particular, they have a power-law degree distribution with controllable exponent beta, and high clustering that can be controlled via the temperature T. We present the first implementation of an efficient GIRG generator running in expected linear time. Besides varying temperatures, it also supports underlying geometries of higher dimensions. It is capable of generating graphs with ten million edges in under a second on commodity hardware. The algorithm can be adapted to HRGs. Our resulting implementation is the fastest sequential HRG generator, despite the fact that we support non-zero temperatures. Though non-zero temperatures are crucial for many applications, most existing generators are restricted to T = 0. We also support parallelization, although this is not the focus of this paper. Moreover, we note that our generators draw from the correct probability distribution, i.e., they involve no approximation. Besides the generators themselves, we also provide an efficient algorithm to determine the non-trivial dependency between the average degree of the resulting graph and the input parameters of the GIRG model. This makes it possible to specify the desired expected average degree as input. Moreover, we investigate the differences between HRGs and GIRGs, shedding new light on the nature of the relation between the two models. Although HRGs represent, in a certain sense, a special case of the GIRG model, we find that a straight-forward inclusion does not hold in practice. However, the difference is negligible for most use cases.

Any B-tree has height at least ceil[log_B(n)]. Static B-trees achieving this height are easy to build. In the dynamic case, however, standard B-tree rebalancing algorithms only maintain a height within a constant factor of this optimum. We investigate exactly how close to ceil[log_B(n)] the height of dynamic B-trees can be maintained as a function of the rebalancing cost. In this paper, we prove a lower bound on the cost of maintaining optimal height ceil[log_B(n)], which shows that this cost must increase from Omega(1/B) to Omega(n/B) rebalancing per update as n grows from one power of B to the next. We also provide an almost matching upper bound, demonstrating this lower bound to be essentially tight. We then give a variant upper bound which can maintain near-optimal height at low cost. As two special cases, we can maintain optimal height for all but a vanishing fraction of values of n using Theta(log_B(n)) amortized rebalancing cost per update and we can maintain a height of optimal plus one using O(1/B) amortized rebalancing cost per update. More generally, for any rebalancing budget, we can maintain (as n grows from one power of B to the next) optimal height essentially up to the point where the lower bound requires the budget to be exceeded, after which optimal height plus one is maintained. Finally, we prove that this balancing scheme gives B-trees with very good storage utilization.

Graph randomisation is a crucial task in the analysis and synthesis of networks. It is typically implemented as an edge switching process (ESMC) repeatedly swapping the nodes of random edge pairs while maintaining the degrees involved. Curveball is a novel approach that instead considers the whole neighbourhoods of randomly drawn node pairs. Its Markov chain converges to a uniform distribution, and experiments suggest that it requires less steps than the established ESMC. Since trades however are more expensive, we study Curveball's practical runtime by introducing the first efficient Curveball algorithms: the I/O-efficient EM-CB for simple undirected graphs and its internal memory pendant IM-CB. Further, we investigate global trades processing every node in a graph during a single super step, and show that undirected global trades converge to a uniform distribution and perform superior in practice. We then discuss EM-GCB and EM-PGCB for global trades and give experimental evidence that EM-PGCB achieves the quality of the state-of-the-art ESMC algorithm EM-ES nearly one order of magnitude faster.

We consider the loop less k-shortest path (KSP) problem. Although this problem has been studied in the sequential setting for at least the last two decades, no good parallel implementations are known. In this paper, we provide (i) a first systematic empirical comparison of various KSP algorithms and heuristic optimisations, (ii) carefully engineer various parallel implementations of these sequential algorithms and (iii) perform an extensive study of these parallel implementations on a range of graph classes and multicore architectures to determine the best algorithm and parallelization strategy for different graph classes.

LFR is a popular benchmark graph generator used to evaluate community detection algorithms. We present EM-LFR, the first external memory algorithm able to generate massive complex networks following the LFR benchmark. Its most expensive component is the generation of random graphs with prescribed degree sequences which can be divided into two steps: the graphs are first materialized deterministically using the Havel-Hakimi algorithm, and then randomized. Our main contributions are EM-HH and EM-ES, two I/O-efficient external memory algorithms for these two steps. In an experimental evaluation we demonstrate their performance: our implementation is able to handle graphs with more than 37 billion edges on a single machine, is competitive with a massive parallel distributed algorithm, and is faster than a state-of-the-art internal memory implementation even on instances fitting in main memory. EM-LFR's implementation is capable of generating large graph instances orders of magnitude faster than the original implementation. We give evidence that both implementations yield graphs with matching properties by applying clustering algorithms to generated instances.

Random graphs as mathematical models of massive scale-free networks have recently become very popular. While a number of interesting properties of them have been proven, huge instances of such networks actually need to be generated for experimental evaluation and to provide artificial data sets. In this paper, we consider generation methods for random graph models based on linear preferential attachment under limited computational resources and investigate our techniques using the well-known Barabási-Albert (BA) graph model. We present the first two I/O-efficient BA generators, MP-BA and TFP-BA, for the external-memory (EM) model and then extend MP-BA to massive parallelism based on but not limited to GPGPU. Our simple and easily generalizable sequential TFP-BA outperforms a highly tuned implementation of the sequential linear-time BB-BA algorithm by Batagelj and Brandes by several orders of magnitude once the graph size exceeds the available RAM by only 2%. An implementation of MP-BA targeting heterogeneous systems with CPUs and GPUs is 17.6 times faster than BB-BA for instances fitting in main memory and scales well in the EM setting. Both schemes support a number of features in more general preferential attachment models, e.g., seed graphs exceeding main memory, vertices with random initial degrees, the uniform sampling of vertices, directed graphs and edges between two randomly chosen vertices. Compared with previous studies on computer clusters, MP-BA yields competitive results and already poses a viable alternative using only a single machine.

Multisplit is a broadly useful parallel primitive that permutes its input data into contiguous buckets or bins, where the function that categorizes an element into a bucket is provided by the programmer. Due to the lack of an efficient multisplit on GPUs, programmers often choose to implement multisplit with a sort. However, sort does more work than necessary to implement multisplit, and is thus inefficient. In this work, we provide a parallel model and multiple implementations for the multisplit problem. Our principal focus is multisplit for a small number of buckets. In our implementations, we exploit the computational hierarchy of the GPU to perform most of the work locally, with minimal usage of global operations. We also use warp-synchronous programming models to avoid branch divergence and reduce memory usage, as well as hierarchical reordering of input elements to achieve better coalescing of global memory accesses. On an NVIDIA K40c GPU, for key-only (key-value) multisplit, we demonstrate a 3.0-6.7x (4.4-8.0x) speedup over radix sort, and achieve a peak throughput of 10.0 G keys/s.

Computing shortest path distance is a fundamental primitive in many graph applications. On graphs that do not fit in the main memory of the computing device, computing such distances requires hours to months even with the best I/O-efficient shortest path implementations. For applications requiring many such shortest path distances, one would ideally like to preprocess the input graph into a space-efficient data structure I/O-efficiently, such that the distance queries can be answered with a small additive distortion using only O(1) I/Os. Furthermore, in a batch setting, one would like to answer O(n) such distance queries in Õ(n/B) I/Os. In this paper, we focus on engineering an I/O-efficient distance oracle for large graphs that model real-world interactions. Our engineered oracle (i) preprocesses graphs with multi-billion edges in less than an hour using a single core of a typical PC, (ii) answers online shortest path queries in milliseconds using a SSD, (iii) answers batched shortest path queries using HDDs with an average time per query of a few microseconds, (iv) results in a highly accurate shortest path estimate and (v) uses space linear in the number of nodes. Our implementation creates small oracle labels (i.e., they can still be kept in internal memory for rather large graphs) but also efficiently handles the case when both the graph and these labels have to reside on external storage. Dynamic settings where new edges are continuously inserted into the graph are efficiently supported, too.

Novel algorithmic ideas for big data have not been accompanied by advances in the way central memory is allocated to concurrently running programs. Commonly, RAM is poorly managed since the programs’ trade offs between speed of execution and RAM consumption are ignored. This trade off is, however, well known to the programmers. We adopt mechanism design tools to truthfully elicit this (multidimensional) information with the aim of designing more clever RAM allocation algorithms. We introduce a novel paradigm wherein programs are bound to overbidding declarations of their running times. We show the limitations of this paradigm in the absence of transfers and prove how to leverage waiting times, as a currency, to obtain optimal money burning mechanisms for the makespan. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

We present I/O-efficient single-source shortest path algorithms for undirected graphs. Our main result is an algorithm with I/O complexity O(√( nm log L )/ B +MST( n, m )) on graphs with n vertices, m edges, and arbitrary edge lengths between 1 and L ; MST( n, m denotes the I/O complexity of computing a minimum spanning tree; B denotes the disk block size. If the edge lengths are drawn uniformly at random from (0,1], the expected I/O complexity of the algorithm is O(√ nm/B + ( m/B )log B + MST( n, m )). A simpler algorithm has expected I/O complexity O(√( nm log B )/ B + MST( n, m )) for uniformly random edge lengths.

We report on initial experimental results for a practical I/O-efficient Single-Source Shortest-Paths (SSSP) algorithm on general undirected sparse graphs where the ratio between the largest and the smallest edge weight is reasonably bounded (for example integer weights in {1, …, 232}) and the realistic assumption holds that main memory is big enough to keep one bit per vertex. While our implementation only guarantees average-case efficiency, i.e., assuming randomly chosen edge-weights, it turns out that its performance on real-world instances with non-random edge weights is actually even better than on the respective inputs with random weights. Furthermore, compared to the currently best implementation for external-memory BFS [6], which in a sense constitutes a lower bound for SSSP, the running time of our approach always stayed within a factor of five, for the most difficult graph classes the difference was even less than a factor of two. We are not aware of any previous I/O-efficient implementation for the classic general SSSP in a (semi) external setting: in two recent projects [10, 23], Kumar/Schwabe-like SSSP approaches on graphs of at most 6 million vertices have been tested, forcing the authors to artificially restrict the main memory size, M, to rather unrealistic 4 to 16 MBytes in order not to leave the semi-external setting or produce huge running times for larger graphs: for random graphs of 220 vertices, the best previous approach needed over six hours. In contrast, for a similar ratio of input size vs. M, but on a 128 times larger and even sparser random graph, our approach was less than seven times slower, a relative gain of nearly 20. On a real-world 24 million node street graph, our implementation was over 40 times faster. Even larger gains of over 500 can be estimated for random line graphs based on previous experimental results for Munagala/Ranade-BFS. Finally, we also report on early results of experiments in which we replace the hard disk by a solid state disk (flash memory).

We provide the first non-trivial result on dynamic breadth-first search (BFS) in external-memory: For general sparse undirected graphs of initially $n$ nodes and $O(n)$ edges and monotone update sequences of either $Theta(n)$ edge insertions or $Theta(n)$ edge deletions, we prove an amortized high-probability bound of $O(n/B^{2/3}+sort(n)cdot log B)$ I/Os per update. In contrast, the currently best approach for static BFS on sparse undirected graphs requires $Omega(n/B^{1/2}+sort(n))$ I/Os.

We present a simple algorithm which maintains the topological order of a directed acyclic graph (DAG) with n nodes, under an online edge insertion sequence, in O ( n 2.75 ) time, independent of the number m of edges inserted. For dense DAGs, this is an improvement over the previous best result of O (min{ m 3/2 log n , m 3/2 + n 2 log n }) by Katriel and Bodlaender [2006]. We also provide an empirical comparison of our algorithm with other algorithms for incremental topological sorting.

Breadth first search (BFS) traversal on massive graphs in external memory was considered non-viable until recently, because of the large number of I/Os it incurs. Ajwani et al. [3] showed that the randomized variant of the o(n) I/O algorithm of Mehlhorn and Meyer [24] (MM_BFS) can compute the BFS level decomposition for large graphs (around a billion edges) in a few hours for small diameter graphs and a few days for large diameter graphs. We improve upon their implementation of this algorithm by reducing the overhead associated with each BFS level, thereby improving the results for large diameter graphs which are more difficult for BFS traversal in external memory. Also, we present the implementation of the deterministic variant of MM_BFS and show that in most cases, it outperforms the randomized variant. The running time for BFS traversal is further improved with a heuristic that preserves the worst case guarantees of MM_BFS. Together, they reduce the time for BFS on large diameter graphs from days shown in [3] to hours. In particular, on line graphs with random layout on disks, our implementation of the deterministic variant of MM_BFS with the proposed heuristic is more than 75 times faster than the previous best result for the randomized variant of MM_BFS in [3].

Several routing schemes in ad hoc networks first establish a virtual backbone and then route messages via backbone nodes. One common way of constructing such a backbone is based on the construction of a connected dominating set (CDS). In this article we present a very simple distributed algorithm for computing a small CDS. Our algorithm has an approximation factor of at most 6.91, improving upon the previous best-known approximation factor of 8 due to Wan et al. [2002]. The improvement relies on a refined analysis of the relationship between the size of a maximal independent set and a minimum CDS in a unit disk graph. This subresult also implies improved approximation factors for many existing algorithm.

Computing the strong components of a directed graph is an essential operation for a basic structural analysis of it. This problem can be solved by twice running a depth-first search (DFS). In an external setting, in which all data can no longer be stored in the main memory, the DFS problem is unsolved so far. Assuming that node-related data can be stored internally, semi-external computing does not make the problem substantially easier. Considering the definite need to analyze very large graphs, we have developed a set of heuristics which together allow the performance of semi-external DFS for directed graphs in practice. The heuristics have been applied to graphs with very different graph properties, including "web graphs" as described in the most recent literature and some large call graphs from ATT. Depending on the graph structure, the program is between 10 and 200 times faster than the best alternative, a factor that will further increase with future technological developments.

We show that the well-known random incremental constructlon of Clarkson and Shor [14] can be adapted via gradations to provide efficient external-memory algorithms for some geomctric problems.In particular, as the main result, we obtain an optimal randomized algorithm for the problem of computing the trapezoidal decomposition determined by a set of N line scgmcnts in the plane with K pairwise intersections, that requires G($$ logMjB Q + 5) expected disk accesses (I/OS), where M is the size of the available internal memory and B is the size of the block transfer.The approach is sufficiently general to obtain algorithms for the problems of 2-d and 3-d convex hulls, 2-d abstract Voronoi diagrams and batched point location in a planar subdivision, which require an optimal expected number of I/OS and are olmplcr than the ones previously known.The results extend to a external-memory model with multiple disks.