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

Модель Барабаши — Альберт — это математическая модель роста сложных сетей, предложенная физиками Альбертом-Ласло Барабаши и Рекой Альберт в 1999 году. Модель объясняет возникновение безмасштабных сетей, то есть сетей, распределение степеней вершин в которых подчиняется степенному закону. Она описывает, как в реальных сетях (например, в интернете, социальных сетях, цитировании научных статей) появляются «хабы» — узлы с аномально большим числом связей.

¶Основные принципы

Модель Барабаши — Альберт основана на двух ключевых механизмах, которые отличают её от классических моделей случайных графов, таких как модель Эрдёша — Реньи:

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

1. Предпочтительное присоединение (преференциальное связывание). Вероятность того, что новый узел соединится с конкретным существующим узлом \( i \), пропорциональна степени этого узла \( k_i \) (числу его связей). Формально это выражается как:

\[ \Pi(k_i) = \frac{k_i}{\sum_j k_j} \] где \( \Pi(k_i) \) — вероятность выбора узла \( i \), а \( \sum_j k_j \) — сумма степеней всех существующих узлов. Этот механизм означает, что чем больше связей уже имеет узел, тем быстрее он приобретает новые. В контексте интернета это можно интерпретировать так: популярные сайты (с большим числом ссылок) с большей вероятностью получают новые ссылки, чем малоизвестные.

¶Математическое описание

Модель Барабаши — Альберт можно описать с помощью непрерывного приближения, предложенного самими авторами. Пусть \( k_i(t) \) — степень узла \( i \), добавленного в момент времени \( t_i \). Скорость изменения степени узла пропорциональна его текущей степени: \[ \frac{\partial k_i}{\partial t} = m \cdot \frac{k_i}{\sum_j k_j} \] Поскольку в каждый момент времени в сети \( t \) узлов, а каждый новый узел добавляет \( m \) связей, общее число связей в сети равно \( m t \). Сумма степеней всех узлов равна удвоенному числу связей: \( \sum_j k_j = 2 m t \). Подставляя это в уравнение, получаем: \[ \frac{\partial k_i}{\partial t} = \frac{k_i}{2 t} \] Решая это дифференциальное уравнение с начальным условием \( k_i(t_i) = m \), находим: \[ k_i(t) = m \left( \frac{t}{t_i} \right)^{1/2} \] Это означает, что степень узла растёт как корень квадратный из времени, прошедшего с момента его появления. Чем раньше узел появился в сети, тем выше его степень.

Из этого решения можно получить распределение степеней \( P(k) \), то есть вероятность того, что случайно выбранный узел имеет степень \( k \). В модели Барабаши — Альберт оно подчиняется степенному закону: \[ P(k) \sim k^{-3} \] Показатель степени \( \gamma = 3 \) является универсальным для этой модели и не зависит от параметра \( m \). Это означает, что в сети существует небольшое число узлов с очень высокой степенью (хабы) и огромное число узлов с низкой степенью.

¶Свойства модели

¶Безмасштабность

Главное свойство модели — отсутствие характерного масштаба в распределении степеней. В отличие от случайных графов, где распределение степеней является пуассоновским (средняя степень хорошо описывает типичный узел), в модели Барабаши — Альберт средняя степень не является репрезентативной. Степени узлов варьируются на несколько порядков, что и дало название классу «безмасштабные сети».

¶Малое среднее расстояние

Модель Барабаши — Альберт порождает сети с малым средним расстоянием между узлами (эффект «тесного мира»). Среднее расстояние \( \langle d \rangle \) растёт логарифмически с размером сети \( N \): \[ \langle d \rangle \sim \frac{\ln N}{\ln \ln N} \] Это свойство характерно для многих реальных сетей, таких как интернет или социальные графы.

¶Кластеризация

Коэффициент кластеризации (мера того, насколько соседи узла связаны между собой) в модели Барабаши — Альберт убывает с ростом размера сети как \( C \sim N^{-0.75} \). Это значение ниже, чем в некоторых реальных сетях (например, в социальных), что указывает на ограничения модели.

¶Модификации и обобщения

Оригинальная модель Барабаши — Альберт имеет несколько ограничений, которые были устранены в последующих работах:

• Нелинейное предпочтительное присоединение. В реальных сетях вероятность присоединения может зависеть от степени нелинейно: \( \Pi(k) \sim k^\alpha \). При \( \alpha < 1 \) распределение степеней становится более однородным, при \( \alpha > 1 \) — возникает «победитель получает всё» (сеть становится звездообразной). При \( \alpha = 0 \) модель сводится к случайному графу.
• Удаление узлов и связей. В реальных сетях узлы и связи могут исчезать (например, закрытие сайтов или удаление друзей). Модификации модели учитывают эти процессы, что может приводить к другим показателям степени в распределении.
• Внутренние связи между существующими узлами. В оригинальной модели новые связи добавляются только с новыми узлами. В реальности существующие узлы также могут устанавливать связи друг с другом (например, два старых друга в социальной сети). Это увеличивает коэффициент кластеризации.
• Модели с несколькими типами узлов. Например, в научных сетях цитирования статьи могут иметь разный «возраст» или «качество», что влияет на вероятность получения новых ссылок.

¶Применение

Модель Барабаши — Альберт используется для описания и анализа широкого круга реальных сетей:

• Интернет. Структура Всемирной паутины, где веб-страницы соединяются гиперссылками, демонстрирует безмасштабное распределение: небольшое число сайтов (например, Google, Wikipedia) имеют огромное число входящих ссылок, в то время как большинство страниц имеют лишь несколько ссылок.
• Социальные сети. Сети дружбы в онлайн-платформах (например, ВКонтакте, Facebook* — организация признана экстремистской и запрещена в РФ) также следуют степенному закону: есть «звёзды» с миллионами подписчиков и множество пользователей с десятками друзей.
• Научные цитирования. Распределение числа цитирований статей подчиняется степенному закону: небольшое число работ (например, основополагающие статьи) цитируются тысячи раз, в то время как большинство — лишь несколько раз.
• Биологические сети. Метаболические сети, сети взаимодействия белков и нейронные сети также демонстрируют безмасштабные свойства.

¶Критика и ограничения

Модель Барабаши — Альберт, несмотря на свою популярность, подвергается критике по нескольким причинам:

• Универсальность показателя. Степенной закон с показателем \( \gamma = 3 \) редко наблюдается в реальных сетях. Например, в интернете \( \gamma \) обычно находится в диапазоне от 2,1 до 2,5, а в социальных сетях — от 2,0 до 2,8. Это требует введения дополнительных механизмов, таких как нелинейное присоединение или старение узлов.
• Предпочтительное присоединение как предположение. Механизм преференциального связывания не всегда подтверждается эмпирически. В некоторых сетях (например, в сети цитирования патентов) новые узлы могут выбирать партнёров случайным образом или на основе других факторов (например, близости тематики).
• Отсутствие кластеризации. Реальные сети часто имеют высокий коэффициент кластеризации, который модель Барабаши — Альберт не воспроизводит адекватно. Это ограничение было частично преодолено в более сложных моделях, таких как модель «малых миров» Уоттса — Строгаца.
• Статичность параметров. В модели параметры \( m \) и \( m_0 \) считаются постоянными, в то время как в реальных сетях они могут меняться со временем (например, скорость роста числа новых пользователей в социальной сети может замедляться).

¶Интересные факты

• Модель Барабаши — Альберт была разработана на основе анализа данных о структуре интернета, собранных в 1998–1999 годах. Барабаши и его коллеги обнаружили, что распределение ссылок на веб-страницы подчиняется степенному закону, что противоречило существовавшим тогда моделям случайных графов.
• Статья Барабаши и Альберт «Emergence of Scaling in Random Networks» (1999) является одной из самых цитируемых в области сетевой науки — по состоянию на 2024 год она была процитирована более 50 000 раз.
• Модель иногда называют «моделью Барабаши — Альберт — Жанга» (Bianconi–Barabási model) в честь более поздних обобщений, учитывающих «приспособленность» узлов (конкуренцию между узлами за связи).

¶Источники

• Barabási, A.-L., & Albert, R. (1999). Emergence of Scaling in Random Networks. Science, 286(5439), 509–512.
• Barabási, A.-L. (2016). Network Science. Cambridge University Press.
• Newman, M. E. J. (2010). Networks: An Introduction. Oxford University Press.
• Dorogovtsev, S. N., & Mendes, J. F. F. (2003). Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford University Press.