2015-05-18
349
Для проверки эффективности данного алгоритма была взята сеть автономных сетей Интернет, мгновенный снимок которой был получен в 2006 году на проекте Oregon RouteViews [9]. Данные об этой сети были взяты из [10].
По данным этой реальной сети были построены модели графов ПС и модели с использованием предложенного алгоритма.
В данной работе особый интерес представляли такие характеристики графа как его диаметр и коэффициент кластеризации. Поэтому в таблице 2 представлены характеристики графа именно по этим структурным характеристикам сл.г.
Коэффициент кластеризации и диаметр графа взяты как среднее из 100 значений. Данные параметры моделей считались в пакете R.
Таблица 2 – Сравнение диаметра графа и коэффициента кластеризации в различных моделях сети автономных систем
| Сеть | Коэффициент кластеризации | Диаметр графа |
| Мгновенный снимок сети Автономных систем | 0.0111464 | |
| Граф БА, m = 2 | 0.0008704 | 9.13 |
| Граф БА, m = 2, с модифицированным правилом выбором вершин | 0.0938698 | 14.19 |
| Граф ПС с распределением ребер в приращении rk = {0/0.0000000, 1/0.3509441, 2/0.427474478, 3/0.082815651, 4/0.038862743, 5/0.099902998} | 0.0032301 | 8.81 |
| Граф ПС с распределением ребер в приращении rk ={0/0.0000000, 1/0.442421898, 2/0.457278271, 3/0, 0.033445638, 4/0.01771394, 5/0.009795921, 6/0.005440743, 7/0.003764738, 8/0.00143948, 9/0.001057483, 10/0.001174982, 11/0.00129248, 12/0.001409978, 13/0.023764444} | 0.0045669 | 9.07 |
| Граф ПС с распределением ребер в приращении rk = {0/0.0000000, 1/0.3509441, 2/0.427474478, 3/0.082815651, 4/0.038862743, 5/0.099902998}. Используется модифицированное правило выбора вершин. | 0.0090506 | 11.97 |
Первый столбец таблицы 2 представляет собой описание характеризуемой сети.
|
|
|
Вначале идёт реальная сеть. Именно данные из этой строки являются образцом для сравнения.
Граф БА со средней степенью связности равно 2, это модель, построенная полностью по правилу построения графа БА.
Далее данный граф строился с применением данного алгоритма.
Последующие сети – это графы ПС с различным распределением рёбер в приращении. Были получены разные графы путём изменения функции предпочтения. В фигурных скобках указанно, какое количество рёбер с какой вероятностью будет присоединяться.
Из полученных результатов можно сделать вывод, что данный алгоритм увеличивает коэффициент кластеризации и диаметр, то есть приближает характеристики моделей к характеристикам реальных сетей.
Полученные результаты говорят о том, что данный алгоритм является эффективным.
