Random growth networks with exponential degree distribution

Fei Ma, Xudong Luo, Ping Wang, Renbo ZhuChaos 2020 · DOI

Abstract

A great variety of complex networks can be well represented as random graphs with some constraints: for instance, a provided degree distribution, a smaller diameter, and a higher clustering coefficient. Among them, the degree distribution has attracted considerable attention from various science communities in the last few decades. In this paper, we focus mainly on a family of random graphs modeling complex networks that have an exponential degree distribution; i.e., P(k)∼ exp(αk), where k is the degree of a vertex, P(k) is a probability for choosing randomly a vertex with degree equal to k, and α is a constant. To do so, we first introduce two types of operations: type-A operation and type-B operation. By both the helpful operations, we propose an available algorithm A for a seminal model to construct exactly solvable random graphs, which are able to be extended to a graph space S(p,p<sup>c</sup>,t) with probability parameters p and p<sup>c</sup> satisfying p+p<sup>c</sup>=1. Based on the graph space S(p,p<sup>c</sup>,t), we discuss several topological structure properties of interest on each member N(p,p<sup>c</sup>,t) itself and find model N(p,p<sup>c</sup>,t) to exhibit the small-world property and assortative mixing. In addition, we also report a fact that in some cases, two arbitrarily chosen members might have completely different other topological properties, such as the total number of spanning trees, although they share a degree distribution in common. Extensive experimental simulations are in strong agreement with our analytical results.
BibTeX
@inproceedings{ma2020random,
  author = {Fei Ma and Xudong Luo and Ping Wang and Renbo Zhu},
  title = {{Random growth networks with exponential degree distribution}},
  booktitle = {Chaos},
  year = {2020},
  doi = {10.1063/5.0022840},
}

Loading related content...

Figure