Модель Барабаси

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

Концепции

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

* рост сети

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

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

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

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

Алгоритм

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

Сеть начинается с начальной сетки с $m_0$ узлами. $m_0 >= 2$ и степень каждого узла в начальной сети должна быть не меньше 1, иначе она всегда будет отделена от остальной части сети.

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

$p_i = {k_i \over \sum_{j} k_j}$

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

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

Свойства

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

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

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

$P\left(k\right)\sim k^{-3} \,$

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

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

$\ell\sim\frac{\ln N}{\ln \ln N}.$

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

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

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

$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\ell}=k^{-3}\ell^{-3}$.

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

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

$C\sim N^{-0.75}. \,$^[1]

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

$C(k) = k^{-1}. \,$

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

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

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

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

Модель А

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

Модель B

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

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

История

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

Примечания

1. ↑ ^{1 2 3 4} Albert, Réka (2002). «Statistical mechanics of complex networks». Reviews of Modern Physics 74: 47–97. DOI:10.1103/RevModPhys.74.47. Bibcode: 2002RvMP...74...47A.
2. ↑ ^{1 2} Albert-László Barabási & Réka Albert (October 1999). «Emergence of scaling in random networks». Science 286 (5439): 509–512. DOI:10.1126/science.286.5439.509.
3. ↑ S.N. Dorogovtsev, A.V. Goltsev, and J.F.F. Mendes, e-print cond-mat/0112143.
4. ↑ Udny Yule (1925). «A Mathematical Theory of Evolution Based on the Conclusions of Dr. J. C. Willis, F.R.S.». Journal of the Royal Statistical Society 88 (3): 433–436. DOI:10.2307/2341419.
5. ↑ Herbert A. Simon (December 1955). «On a Class of Skew Distribution Functions». Biometrika 42 (3–4): 425–440. DOI:10.1093/biomet/42.3-4.425.
6. ↑ D.J. de Solla Price (1976). «A general theory of bibliometric and other cumulative advantage processes». Journal of the American Society for Information Science 27: 292–306. DOI:10.1002/asi.4630270505.

Ссылки

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