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

With random graph generation, most of the previously described algorithms were not related to graphs arising in any particular subject area, so in this paper we generate random graphs for a specific area, namely, models of real communication networks. In the paper 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. 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. 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 5x5 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 got 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.