An Exact and an Approximation Method to Compute the Degree Distribution of Inhomogeneous Random Graph Using Poisson Binomial Distribution

Róbert Pethes () and Levente Kovács
Additional contact information
Róbert Pethes: Physiological Controls Research Center, Óbuda University, 1034 Budapest, Hungary
Levente Kovács: Physiological Controls Research Center, Óbuda University, 1034 Budapest, Hungary

Mathematics, 2023, vol. 11, issue 6, 1-24

Abstract: Inhomogeneous random graphs are commonly used models for complex networks where nodes have varying degrees of connectivity. Computing the degree distribution of such networks is a fundamental problem and has important applications in various fields. We define the inhomogeneous random graph as a random graph model where the edges are drawn independently and the probability of a link between any two vertices can be different for each node pair. In this paper, we present an exact and an approximation method to compute the degree distribution of inhomogeneous random graphs using the Poisson binomial distribution. The exact algorithm utilizes the DFT-CF method to compute the distribution of a Poisson binomial random variable. The approximation method uses the Poisson, binomial, and Gaussian distributions to approximate the Poisson binomial distribution.

Keywords: inhomogeneous random graph; Poisson binomial distribution; degree distribution; DFT-CF method (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/6/1441/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/6/1441/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:6:p:1441-:d:1099063

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().