Special Generation of Random Graphs and Statistical Study of Some of Their Invariants

Boris Melnikov () and Bowen Liu
Additional contact information
Boris Melnikov: Department of Computational Mathematics and Cybernetics, Shenzhen MSU–BIT University, 1 International University Park Road, Dayun New Town, Longgang District, Shenzhen 518172, China
Bowen Liu: Department of Computational Mathematics and Cybernetics, Shenzhen MSU–BIT University, 1 International University Park Road, Dayun New Town, Longgang District, Shenzhen 518172, China

Mathematics, 2025, vol. 13, issue 12, 1-14

Abstract: In this paper, we generate random graphs for a specific area, namely, models of real communication networks. We propose a method that determines the “best” invariant; the corresponding basic algorithm is as follows. For the generated set of graphs, we calculate the numerical values of each of the pre-selected invariants (i.e., indexes of Graovac–Ghorbani, Randic̀, Wiener, global clustering coefficients and the vector of second-order degrees). For all graphs, we arrange these numerical values in descending order, after which, for each of the 10 pairs of invariants, we calculate the rank correlation of these orders; for such calculations, we use 5 different variants of rank correlation algorithms (i.e., usual pair correlation, Spearman’s algorithm, Kendall’s algorithm and its improved version, and the algorithm proposed by the authors). In such a way, we get 10 pairs of rank correlation values, then we arrange them as the values of 10 independent elements of the 5 × 5 table (rows and columns of this table correspond to the 5 invariants under consideration). If the rank correlation values are negative, we record the absolute value of this value in the table. The basic idea is that the “most independent” invariant of the graph gets the minimum sum when summing 4 values of its row, i.e., less than for other invariants (other rows). For our subject area, we obtained the same result for 5 different variants of calculating the rank correlation: the value obtained for the vector of second-order degrees is significantly better than all the others, and among the usual invariants, the global clustering coefficients invariant is significantly better than others ones. This fact corresponds to our previous calculations, in which we ordered the graph invariants according to completely different algorithms.

Keywords: random graph; communication networks; rank correlation; Graovac-Ghorbani index; graph invariants; global clustering coefficient (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/12/1904/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/12/1904/ (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:13:y:2025:i:12:p:1904-:d:1673404

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 ().