From inhomogeneous random digraphs to random graphs with fixed arc counts
math.PR
Submitted: 2023-09-12
Updated: 2023-09-12
Comments: 42 pages, 3 figures
Journal ref: Stochastic Processes and their Applications, 2026, 196, 104875
DOI: 10.1016/j.spa.2026.104875
License: http://creativecommons.org/licenses/by/4.0/
The gist: Consider a random graph model with n vertices where each vertex has a vertex-type drawn from some discrete distribution.
Terminology
Abstract
Consider a random graph model with n vertices where each vertex has a vertex-type drawn from some discrete distribution. Suppose that the number of arcs to be placed between each pair of vertex-types is known, and that each arc is placed uniformly at random without replacement between one of the vertex-pairs with matching types. In this paper, we will show that under certain conditions this random graph model is equivalent to the well-studied inhomogeneous random digraph model. We will use this equivalence in three applications. First, we will apply the equivalence on some well known random graph models (the Erdős-Rényi model, the stochastic block model, and the Chung-Lu model) to showcase what their equivalent counterparts with fixed arcs look like. Secondly, we will extend this equivalence to a practical model for inferring cell-cell interactions to showcase how theoretical knowledge about inhomogeneous random digraphs can be transferred to a modeling context. Thirdly, we will show how our model induces a natural fast algorithm to generate inhomogeneous random digraphs.
Related papers
- Rank-One HCIZ Integrals and Multiplicative Convolutions
- Repeated averaging on random d-regular graphs
- Precise cover times for branching random walks on Hamming graphs: (iterated) logarithmic corrections
- Markov Chain CLTs: Resolving Open Problems
- Marked stable L'evy processes in Brownian local time
- A Sharp Refinement of Samuels' Inequality via Cap Moves