An Exact and an Approximation Method to Compute the Degree Distribution of Inhomogeneous Random Graph Using Poisson Binomial Distribution
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 rand...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-03-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/11/6/1441 |
| _version_ | 1797610273886961664 |
|---|---|
| author | Róbert Pethes Levente Kovács |
| author_facet | Róbert Pethes Levente Kovács |
| author_sort | Róbert Pethes |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-11T06:13:05Z |
| format | Article |
| id | doaj.art-2263e218e94d4704897932d8546b1458 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-11T06:13:05Z |
| publishDate | 2023-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-2263e218e94d4704897932d8546b14582023-11-17T12:28:40ZengMDPI AGMathematics2227-73902023-03-01116144110.3390/math11061441An Exact and an Approximation Method to Compute the Degree Distribution of Inhomogeneous Random Graph Using Poisson Binomial DistributionRóbert Pethes0Levente Kovács1Physiological Controls Research Center, Óbuda University, 1034 Budapest, HungaryPhysiological Controls Research Center, Óbuda University, 1034 Budapest, HungaryInhomogeneous 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.https://www.mdpi.com/2227-7390/11/6/1441inhomogeneous random graphPoisson binomial distributiondegree distributionDFT-CF method |
| spellingShingle | Róbert Pethes Levente Kovács An Exact and an Approximation Method to Compute the Degree Distribution of Inhomogeneous Random Graph Using Poisson Binomial Distribution Mathematics inhomogeneous random graph Poisson binomial distribution degree distribution DFT-CF method |
| title | An Exact and an Approximation Method to Compute the Degree Distribution of Inhomogeneous Random Graph Using Poisson Binomial Distribution |
| title_full | An Exact and an Approximation Method to Compute the Degree Distribution of Inhomogeneous Random Graph Using Poisson Binomial Distribution |
| title_fullStr | An Exact and an Approximation Method to Compute the Degree Distribution of Inhomogeneous Random Graph Using Poisson Binomial Distribution |
| title_full_unstemmed | An Exact and an Approximation Method to Compute the Degree Distribution of Inhomogeneous Random Graph Using Poisson Binomial Distribution |
| title_short | An Exact and an Approximation Method to Compute the Degree Distribution of Inhomogeneous Random Graph Using Poisson Binomial Distribution |
| title_sort | exact and an approximation method to compute the degree distribution of inhomogeneous random graph using poisson binomial distribution |
| topic | inhomogeneous random graph Poisson binomial distribution degree distribution DFT-CF method |
| url | https://www.mdpi.com/2227-7390/11/6/1441 |
| work_keys_str_mv | AT robertpethes anexactandanapproximationmethodtocomputethedegreedistributionofinhomogeneousrandomgraphusingpoissonbinomialdistribution AT leventekovacs anexactandanapproximationmethodtocomputethedegreedistributionofinhomogeneousrandomgraphusingpoissonbinomialdistribution AT robertpethes exactandanapproximationmethodtocomputethedegreedistributionofinhomogeneousrandomgraphusingpoissonbinomialdistribution AT leventekovacs exactandanapproximationmethodtocomputethedegreedistributionofinhomogeneousrandomgraphusingpoissonbinomialdistribution |