Модель Барабаши — Альберт

Модель Барабаши-Альберт (БА) — алгоритм генерации случайных безмасштабных сетей с использованием принципа предпочтительного присоединения. Безмасштабные сети широко распространены в природных сетях (пищевые цепочки) и сетях, созданных человеком (Интернет, всемирная паутина, сети цитирования, некоторые социальные сети).

КонцепцииПравить

Многие исследуемые сети попадают под класс безмасштабных сетей. Это значит, что они имеют степенное распределение по степени узла, тогда как модели случайных графов (Уоттса — Строгатца  (англ.) (рус. и Эрдёша — Реньи) не имеют такого распределения. Модель Барабаши — Альберт — одна из нескольких предложенных моделей со степенным распределением, которые генерируют безмасштабные сети. Она включает в себя две важные общие концепции:

• рост сети
• принцип предпочтительного присоединения (ПП)

Обе концепции широко представлены в сетях реального мира. Рост значит, что число узлов сети увеличивается со временем.

Принцип предпочтительного присоединения заключается в том, что чем больше связей имеет узел, тем более предпочтительно для него создание новых связей. Узлы с наибольшей степенью имеют больше возможностей забирать себе связи, добавляемые в сеть. Интуитивно, принцип предпочтительно присоединения может быть понят, если мы думаем в терминах социальных сетей, которые объединяют людей. Здесь связь от А к B значит, что человек A «знает» или «знаком» с человеком B. Сильно связанные узлы представлены известными людьми с большим числом связей. Когда новичок попадает в сообщество, для него/неё более предпочтительно связаться с одним из известных людей, чем с относительно неизвестным. Подобным образом во всемирной сети страницы связываются с хабами, к примеру, с хорошо известными сайтами, как Гугл или Википедия, чем со страницами, которые мало кому известны. Если выбирать для связи новую страницу случайным образом, то вероятность выбора определённой страницы будет пропорциональна её степени. Это объясняет принцип предпочтительного присоединения.

Принцип предпочтительно присоединения — пример положительной обратной связи, где изначально случайные вариации (один узел изначально имеет больше ссылок или начинает собирать ссылки раньше других) автоматически усиливаются, тем самым значительно увеличивая разрыв. Это также иногда называют эффектом Матфея, «богатые становятся богаче», или автокатализом в химии.

АлгоритмПравить

 

Шаги роста сети в соответствии с моделью БА

Сеть начинается с начальной сетки с $m_0$$m_{0}$  узлами. $m_0\ge <!--\; \ge \; -->2$$m_{0}\geq 2$  и степень каждого узла в начальной сети должна быть не меньше 1, иначе она всегда будет отделена от остальной части сети.

В каждый момент времени в сеть добавляется новый узел. Каждый новый узел соединяется с существующими узлами с вероятностью, пропорциональной числу связей этих узлов. Формально, вероятностью $p_i$$p_{i}$  того, что новый узел соединится с узлом i равна:

$p_i=\frac{k_i}{\underset{j}{\sum <!--\; \sum \; -->}{k}_j}$$p_{i}={k_{i} \over \sum _{j}k_{j}}$ 

где $k_i$$k_i$  — степень i-го узла, а в знаменателе суммируются степени всех существующих узлов. Наиболее связанные узлы («хабы»), как правило, накапливают ещё больше связей, тогда как узлы с небольшим числом связей вряд ли будут выбраны для присоединения новых узлов. Новые узлы имеют «предпочтение» соединяться с наиболее связанными узлами.

 

Сеть, построенная в соответствии с моделью БА. Сеть построена из 50 вершин с начальной степенью m=1.

СвойстваПравить

Степенное распределениеПравить

Степенное распределение в модели БА является безмасштабным, точнее подчиняется степенному закону

 

Распределение степеней модели БА, которое подчиняется степенному закону. В логарифмическом масштабе степенная функция представляет собой прямую линию.

$P\left(k\right)\sim <!--\; \sim \; -->k^{-<!--\; -\; -->3}$$P\left(k\right)\sim k^{-3}$ 

Средняя длина путиПравить

Средняя длина пути в модели БА увеличивается в среднем, как логарифм размера сети. Точная форма имеет двойную логарифмическую поправку и выглядит, как

$\mathrm{\ell <!--\; \ell \; -->}\sim <!--\; \sim \; -->\frac{\ln <!--\; \; -->N}{\ln <!--\; \; -->\ln <!--\; \; -->N}.$$\ell \sim {\frac {\ln N}{\ln \ln N}}.$ 

Модель БА имеет систематически более короткий средний путь, нежели случайный граф.

Корреляции степени узлаПравить

Корреляции степеней соединённых узлов развиваются случайным образом в модели БА, из-за особенностей развития сети. Вероятность нахождения связи между узлами со степенями и в модели БА представлена, как

$n_{k\mathrm{\ell <!--\; \ell \; -->}}=\frac{4\left(\mathrm{\ell <!--\; \ell \; -->}-<!--\; -\; -->1\right)}{k\left(k+1\right)\left(k+\mathrm{\ell <!--\; \ell \; -->}\right)\left(k+\mathrm{\ell <!--\; \ell \; -->}+1\right)\left(k+\mathrm{\ell <!--\; \ell \; -->}+2\right)}+\frac{12\left(\mathrm{\ell <!--\; \ell \; -->}-<!--\; -\; -->1\right)}{k\left(k+\mathrm{\ell <!--\; \ell \; -->}-<!--\; -\; -->1\right)\left(k+\mathrm{\ell <!--\; \ell \; -->}\right)\left(k+\mathrm{\ell <!--\; \ell \; -->}+1\right)\left(k+\mathrm{\ell <!--\; \ell \; -->}+2\right)}.$$n_{k\ell }={\frac {4\left(\ell -1\right)}{k\left(k+1\right)\left(k+\ell \right)\left(k+\ell +1\right)\left(k+\ell +2\right)}}+{\frac {12\left(\ell -1\right)}{k\left(k+\ell -1\right)\left(k+\ell \right)\left(k+\ell +1\right)\left(k+\ell +2\right)}}.$ 

Конечно же, результат будет другим, если распределение было некоррелированным, $n_{k\mathrm{\ell <!--\; \ell \; -->}}=k^{-<!--\; -\; -->3}{\mathrm{\ell <!--\; \ell \; -->}}^{-<!--\; -\; -->3}$$n_{k\ell }=k^{-3}\ell ^{-3}$ .

Коэффициент кластеризацииПравить

Пока нет аналитических значений коэффициента кластеризации модели БА. Коэффициенты кластеризации, полученные эмпирически путём, в общем случае значительно выше для модели БА, нежели для случайных сетей. Коэффициент кластеризации также зависит от размера сети согласно приближенному степенному закону:

$C\sim <!--\; \sim \; -->N^{-<!--\; -\; -->0.75}.$$C\sim N^{-0.75}.$ 

Это поведение всё же отличается от поведения малых сетей, где кластеризация не зависит от размера сети. В случае иерархических сетей, кластеризация как функция степени узла также подчиняется степенному закону:

$C(k)=k^{-<!--\; -\; -->1}.$$C(k)=k^{-1}.$ 

Данные результаты были аналитически получены Дороговцевым, Гольцевым и Мендесом.

Спектральные качестваПравить

Форма спектральной плотности модели БА отличается от полукруглой спектральной плотности случайного графа. Она имеет треугольную форму с вершиной, лежащей значительно выше полукруга, а края убывают по степенному закону.

Предельные случаиПравить

Модель АПравить

Модель А сохраняет рост, но не включает принцип предпочтительного присоединения. Вероятность присоединения нового узла к существующим везде одинакова. Конечное распределение степеней в данном случае говорит о том, что рост сам по себе недостаточен для получения безмасштабной структуры.

Модель BПравить

Модель B сохраняет принцип предпочтительного присоединения, но исключает рост. Модель начинается с фиксированного числа разъединённых узлов и добавляет связи, предпочтительно выбирая точками назначения узлы с высокой степенью. Хотя распределение степеней в начале моделирования выглядит безмасштабным, оно нестабильно, и в конечно итоге становится близко к гауссову, когда сеть приближается к насыщению. Таким образом принцип ПП сам по себе недостаточен для создания безмасштабной структуры.

Провал моделей А и B при получении безмасштабного распределения говорит о том, что рост и ПП одинаково необходимы для воспроизведения стационарного степенного распределения, наблюдаемого в сетях реального мира.

ИсторияПравить

Принцип предпочтительного присоединения впервые использовался для объяснения степенного распределения, полученного Юлем в 1925 году, хотя математический анализ Юля признан туманным по современным стандартам из-за отсутствия соответствующих инструментов для анализа случайных процессов. Современный метод основного кинетического уравнения, который даёт более прозрачный вывод, был применён к проблеме Гербертом Саймоном в 1955 в ходе исследования размеров городов и других явлений. Впервые он был применён к росту сетей Дереком де Солла Прайсом в 1976, который интересовался сетями цитирования между научными публикациями. Название «предпочтительное присоединение» и сегодняшнюю популярность моделей безмасштабных сетей связано с работой Альберта-Ласло Барабаши и Реки Альберт  (англ.) (рус., которые независимо открыли процесс в 1999 и применили его к степенному распределению во всемирной паутине.

СсылкиПравить

• Комплексные сети