Русский
!

Conference publications

Abstracts

XXI conference

Моделирование растущих безмасштабных сетей

Митин Н.А., Подлазов А.В., Щетинина Д.П.

Россия, 125047, Москва, Миусская площадь, д.4

1 pp. (accepted)

В докладе рассматривается модель растущих безмасштабных сетей, позволяющая порождать различные показатели распределения вершин по степени. Данная модель имеет следующие правила построения: на каждом временном шаге одновременно новая вершина соединяется со случайно выбранной из существующих вершиной и n вершин, выбранных с вероятностью пропорциональной их степени, пытаются подружиться с друзьями друзей вершины. Количество вершин n определяется по формуле n = p⋅ is, где i – количество вершин в сети в определенный момент времени, а p и s – параметры модели. Друзья ищутся следующим образом: выбираем случайного друга вершины, у которого тоже выбирается случайный друг и устанавливается с ним связь, если её ещё нет. Если она уже есть, попытка считается потраченной впустую и не повторяется.

На основе вышеописанного алгоритма были сгенерированы растущие безмасштабные сети для разных параметров модели. Также исследуется влияние параметров модели на различные количественные характеристики сети: распределение p(k) вершин по числу соседей, корреляции при образовании связей и кластеризация вторичных связей, а также распределение кратчайших путей.

Анализ вышеописанных сетей показал, что при увеличении количества вершин n происходит изменение топологических свойств сети, а именно: происходит переход от экспоненциального вида распределения к степенной зависимости с показателем степени 1 < γ < 3, причем, чем больше n, тем ниже показатель γ. Изменение топологии сети также влияет и на изменение коррелированных свойств сети. При уменьшении показателя распределения вершин по степени, уменьшается показатель степени r в корреляциях при образовании связей.

Исследование зависимостей G(k) среднего числа связей между соседями вершины от ее степени показало, что при уменьшении показателя γ, увеличивается показатель степени зависимости. Так как зависимость G(k) тесно связана с коэффициентом кластеризации, с уменьшением γ уменьшается коэффициент кластеризации вторичных связей.

Исследование распределений кратчайших расстояний между случайно выбранными вершинами сети показало присутствие эффекта малого мира в безмасштабных сетях. При этом при уменьшении показателя распределения вершин по степени происходит уменьшение диаметра сети.

Работа выполнена при поддержке РФФИ (проекты 12-06-00402 и 13-01-00617).



© 2004 Designed by Lyceum of Informational Technologies №1533