Терентьева Ю.Ю., Мельников Б.Ф., Лю Бовень

СПЕЦИАЛЬНЫЙ ВАРИАНТ ГЕНЕРАЦИИ ГРАФОВ – МОДЕЛЕЙ СЕТЕЙ СВЯЗИ И ИХ СТАТИСТИЧЕСКОЕ ИССЛЕДОВАНИЕ

Резюме: В настоящей статье затрагивается проблема генерации случайных графов для моделей реальных сетей связи. Для этой цели предлагается метод, который определяет «наилучший» инвариант, соответствующий основной алгоритм заключается в следующем. Для сгенерированного набора графов мы вычисляем численные значения каждого из предварительно выбранных инвариантов (в статье мы используем 5 штук). Для всех графов мы упорядочиваем эти численные значения в порядке убывания, после чего для каждой из 10 пар инвариантов вычисляем ранговую корреляцию этих порядков; для таких вычислений мы используем 5 различных вариантов алгоритмов ранговой корреляции. Таким образом, мы получаем 10 пар значений ранговой корреляции, затем упорядочиваем их как значения 10 независимых элементов таблицы 5х5 (строки и столбцы таблицы соответствуют 5 рассматриваемым инвариантам). Вместо отрицательных значений ранговой корреляции мы записываем абсолютное значение этого показателя. Основная идея заключается в том, что «самый независимый» инвариант графа получает минимальную сумму при суммировании 4 значений его строки, т.е. меньше, чем для других инвариантов. Для нашей предметной области мы получили одинаковый результат для любого варианта расчёта (то есть для 5 различных вариантов расчета ранговой корреляции): значение, полученное для вектора степеней второго порядка, значительно лучше всех остальных, а среди «обычных» инвариантов значительно лучше других глобальный коэффициент кластеризации. Этот факт соответствует нашим предыдущим расчётам, в которых мы упорядочивали графовые инварианты в соответствии с совершенно иными алгоритмами.

Ключевые слова: cлучайный граф, коммуникационные сети, ранговая корреляция, индекс Граовача-Горбани, инварианты графа, глобальный коэффициент кластеризации.

Yu. Yu. Terentyeva, B. F. Melnikov, Liu Bowen

A SPECIAL OPTION FOR GENERATING GRAPH MODELS OF COMMUNICATION NETWORKS AND THEIR STATISTICAL STUDY

Summary: This article addresses the problem of generating random graphs for models of real communication networks. For this purpose, a method is proposed 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 (in the article we use 5 options). 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 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 got the same result for any calculation option (that is, 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.