From inhomogeneous random digraphs to random graphs with fixed arc counts
Preprint
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.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Mathematically mapping the network of cells in the tumor microenvironmentCell Reports Methods, 2025
- Precise reconstruction of the TME using bulk RNA-seq and a machine learning algorithm trained on artificial transcriptomesCancer Cell, 2022
- Comparison of methods and resources for cell-cell communication inference from single-cell RNA-Seq dataNature Communications, 2022
- Deciphering cell–cell interactions and communication from gene expressionNature Reviews Genetics, 2020
- A review of stochastic block models and extensions for graph clusteringApplied Network Science, 2019
- Stochastic block models with multiple continuous attributesApplied Network Science, 2019
- Evaluation of vaccination strategies for SIR epidemics on random networks incorporating household structureJournal of Mathematical Biology, 2017
- Community detection in networks: A user guidePhysics Reports, 2016
- Missing and spurious interactions and the reconstruction of complex networksProceedings of the National Academy of Sciences of the United States of America, 2009
- The phase transition in inhomogeneous random graphsRandom Structures & Algorithms, 2007