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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Концепции[править | править вики-текст]

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

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

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

Принцип предпочтительного присоединения заключается в том, что чем больше связей имеет узел, тем более предпочтительно для него создание новых связей. Узлы с наибольшей степенью имеют больше возможностей забирать себе связи, добавляемые в сеть. Интуитивно, принцип предпочтительно присоединения может быть понят, если мы думаем в терминах социальных сетей, которые объединяют людей. Здесь связь от А к 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. Bibcode2002RvMP...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.

Ссылки[править | править вики-текст]