From inhomogeneous random digraphs to random graphs with fixed arc counts

arXiv:2309.06066 · math.PR · Submitted 2023-09-12 · Read on arXiv

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