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

Отображение трех графиков, созданных с помощью модели Барабаши-Альберта (BA). Каждый имеет 20 узлов и параметр присоединения m, как указано. Цвет каждого узла зависит от его степени (одинаковая шкала для каждого графика).

Сетевая наука
Теория
График Комплексная сеть Заражение Маленький мир Без накипи Структура сообщества Перколяция Эволюция Управляемость Рисование графика Социальный капитал Анализ ссылок Оптимизация Взаимность Закрытие Гомофилия Транзитивность Предпочтительная привязанность Теория баланса Сетевой эффект Влияние общества
Типы сетей
Информационная (вычислительная) Телекоммуникации Транспорт Социальное Научное сотрудничество Биологические Искусственный нейрон Взаимозависимый Семантический Пространственный Зависимость Поток на чипе
Графики
Функции Клика Компонент Резать Цикл Структура данных Край Петля Район Путь Вершина Список  / матрица смежности Список  / матрица заболеваемости Типы Двудольный Полный Режиссер Гипер Мульти Случайный Взвешенный
МетрикиАлгоритмы
Центральность Степень Мотив Кластеризация Распределение степеней Ассортативность Расстояние Модульность Эффективность
Модели
Топология Случайный график Эрдеш – Реньи Барабаши – Альберт Фитнес-модель Уоттс-Строгац Экспоненциальный случайный (ERGM) Случайный геометрический (RGG) Гиперболический (HGN) Иерархический Стохастический блок Максимальная энтропия Мягкая конфигурация Тест LFR Динамика Логическая сеть агент на основе Эпидемия / SIR
СпискиКатегории
Темы Програмное обеспечение Сетевые ученые Категория: Теория сетей Категория: Теория графов
v т е

Модель Барабаши – Альберта (BA) - это алгоритм для создания случайных безмасштабных сетей с использованием механизма предпочтительного присоединения . Несколько естественных и созданных руками человека систем, включая Интернет , всемирную паутину , сети цитирования и некоторые социальные сети , считаются приблизительно безмасштабируемыми и определенно содержат несколько узлов (называемых концентраторами) с необычно высокой степенью по сравнению с другими. узлы сети. Модель BA пытается объяснить существование таких узлов в реальных сетях. Алгоритм назван в честь его изобретателей Альберта-Ласло Барабаши и Рики Альберта.и является частным случаем более ранней и более общей модели, называемой моделью Прайса . ^[1]

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

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

Рост означает, что количество узлов в сети увеличивается со временем.

Предпочтительное присоединение означает, что чем больше подключен узел, тем больше вероятность, что он получит новые ссылки. Узлы с более высокой степенью имеют более сильную способность захватывать ссылки, добавленные в сеть. Интуитивно предпочтительную привязанность можно понять, если подумать о социальных сетях, соединяющих людей. Здесь связь от A к B означает, что человек A «знает» или «знаком с» человеком B. Сильно связанные узлы представляют хорошо известных людей с множеством отношений. Когда новичок входит в сообщество, он с большей вероятностью познакомится с одним из этих более заметных людей, чем с относительно неизвестным. Модель BA была предложена, исходя из предположения, что во всемирной паутине новые страницы ссылаются преимущественно на хабы, то есть на очень известные сайты, такие какGoogle , а не на страницы, о которых мало кто знает. Если кто-то выбирает новую страницу для ссылки, случайным образом выбирая существующую ссылку, вероятность выбора конкретной страницы будет пропорциональна ее степени. Модель BA утверждает, что это объясняет правило предпочтительной вероятности прикрепления. Однако, несмотря на то, что модель является весьма полезной, эмпирические данные свидетельствуют о том, что этот механизм в его простейшей форме не применим к всемирной паутине, как показано в «Техническом комментарии к« Появлению масштабирования в случайных сетях » » .

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

Алгоритм [ править ]

Шаги роста сети по модели Барабаши – Альберта ( )${\displaystyle m_{0}=m=2}$

Сеть начинается с начальной подключенной сети узлов.${\displaystyle m_{0}}$

Новые узлы добавляются в сеть по одному. Каждый новый узел связан с существующими узлами с вероятностью, которая пропорциональна количеству связей, которые уже есть у существующих узлов. Формально вероятность того, что новый узел подключен к узлу, равна ^[2]${\displaystyle m\leq m_{0}}$${\displaystyle p_{i}}$${\displaystyle i}$

${\displaystyle p_{i}={\frac {k_{i}}{\sum _{j}k_{j}}},}$

где - степень узла, и сумма производится по всем ранее существовавшим узлам (т. е. знаменатель дает удвоенное текущее количество ребер в сети). Сильно связанные узлы («концентраторы») имеют тенденцию быстро накапливать еще больше ссылок, в то время как узлы только с несколькими ссылками вряд ли будут выбраны в качестве места назначения для новой ссылки. Новые узлы имеют «предпочтение» присоединяться к уже тесно связанным узлам.${\displaystyle k_{i}}$${\displaystyle i}$${\displaystyle j}$

Сеть, созданная по модели Барабаши Альберта. Сеть состоит из 50 вершин с начальными степенями .${\displaystyle m_{0}=1}$

Свойства [ править ]

Распределение степеней [ править ]

Распределение степеней, полученное в рамках модели BA, является безмасштабным, в частности, это степенной закон вида

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

Распределение индекса Хирша [ править ]

Было показано, что распределение индекса Хирша или индекса Хирша также не требует масштабирования и было предложено в качестве индекса лобби для использования в качестве меры центральности ^[4]

${\displaystyle H(k)\sim k^{-6}\,}$

Кроме того, аналитический результат для плотности узлов с h-индексом 1 может быть получен в случае, когда${\displaystyle m_{0}=1}$

${\displaystyle H(1){\Big |}_{m_{0}=1}=4-\pi \,}$

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

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

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

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

Перколяция [ править ]

Порог перколяции модели БА оказался равным pc = 0. ^[6] Это означает, что при случайном удалении узлов в сети BA любая часть узлов не нарушит сеть. С другой стороны, удаление только относительно небольшой части узлов наивысшего уровня вызовет коллапс сети. ^[7]

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

Корреляции между степенями связанных узлов развиваются спонтанно в модели BA из-за того, как развивается сеть. Вероятность нахождения ссылки, которая соединяет узел степени с узлом-предком степени в модели BA для особого случая (дерево BA), определяется выражением${\displaystyle n_{k\ell }}$${\displaystyle k}$${\displaystyle \ell }$${\displaystyle m=1}$

${\displaystyle 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)}}.}$

Это подтверждает существование степени корреляции, потому что, если бы распределения были некоррелированными, мы бы получили . ^[2]${\displaystyle n_{k\ell }=k^{-3}\ell ^{-3}}$

В общем , доля ссылок, которые соединяют узел степени с узлом степени, равна ^[8]${\displaystyle m}$${\displaystyle k}$${\displaystyle \ell }$

${\displaystyle p(k,\ell )={\frac {2m(m+1)}{k(k+1)\ell (\ell +1)}}\left[1-{\frac {{\binom {2m+2}{m+1}}{\binom {k+\ell -2m}{\ell -m}}}{\binom {k+\ell +2}{\ell +1}}}\right].}$

Кроме того, распределение степеней ближайших соседей , то есть распределение степеней соседей узла со степенью , задается формулой ^[8]${\displaystyle p(\ell \mid k)}$${\displaystyle k}$

${\displaystyle p(\ell \mid k)={\frac {m(k+2)}{k\ell (\ell +1)}}\left[1-{\frac {{\binom {2m+2}{m+1}}{\binom {k+\ell -2m}{\ell -m}}}{\binom {k+\ell +2}{\ell +1}}}\right].}$

Другими словами, если мы выбираем узел со степенью , а затем случайным образом выбираем одного из его соседей, вероятность того, что этот случайно выбранный сосед будет иметь степень , определяется выражением выше.${\displaystyle k}$${\displaystyle \ell }$${\displaystyle p(\ell |k)}$

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

Аналитический результат для коэффициента кластеризации модели BA был получен Клеммом и Эгуилусом ^[9] и доказан Боллобасом. ^{[10] [11]} Метод среднего поля для изучения коэффициента кластеризации был применен Фрончаком, Фрончаком и Холистом. ^[12]

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

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

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

Спектральные свойства [ править ]

Спектральная плотность модели BA имеет форму, отличную от полукруглой спектральной плотности случайного графа. Он имеет форму треугольника, вершина которого лежит значительно выше полукруга, а края затухают по степенному закону.^[14]

Динамическое масштабирование [ править ]

Обобщенное распределение степеней модели БА для .${\displaystyle F(q,t)}$${\displaystyle m=1}$

Эти же данные изображаются в автомодельных координатах и и это дает отличной разрушились показывая , что экспонат динамического масштабирования.${\displaystyle t^{1/2}F(q,N)}$${\displaystyle q/t^{1/2}}$${\displaystyle F(q,t)}$

По определению, модель BA описывает явление развития во времени и, следовательно, помимо ее свойства отсутствия масштабирования, можно также искать ее свойство динамического масштабирования. В сети BA узлы также могут быть охарактеризованы обобщенной степенью , произведением квадратного корня из времени рождения каждого узла и их соответствующей степени , а не только степенью, поскольку время рождения имеет значение в сети BA. Мы обнаружили, что обобщенное распределение степеней имеет некоторые нетривиальные особенности и демонстрирует динамическое масштабирование.${\displaystyle q}$${\displaystyle k}$${\displaystyle k}$${\displaystyle F(q,t)}$

${\displaystyle F(q,t)\sim t^{-1/2}\phi (q/t^{1/2}).}$

Это означает , что отдельные участки против разрушится в универсальную кривую , если участки против . ^[15]${\displaystyle F(q,t)}$${\displaystyle q}$${\displaystyle F(q,t)t^{1/2}}$${\displaystyle q/t^{1/2}}$

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

Модель А [ править ]

Модель A сохраняет рост, но не включает предпочтительную привязанность. Вероятность подключения нового узла к любому уже существующему узлу равна. Результирующее распределение степеней в этом пределе является геометрическим ^[16], что указывает на то, что одного роста недостаточно для создания безмасштабной структуры.

Модель B [ править ]

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

Неспособность моделей A и B привести к безмасштабному распределению указывает на то, что рост и предпочтительное присоединение необходимы одновременно для воспроизведения стационарного степенного распределения, наблюдаемого в реальных сетях. ^[2]

Нелинейная преимущественная привязка [ править ]

Модель BA можно рассматривать как частный случай более общей модели нелинейной предпочтительной привязанности (NLPA). ^[17] Алгоритм NLPA идентичен модели BA с заменой вероятности прикрепления более общей формой

${\displaystyle p_{i}={\frac {k_{i}^{\alpha }}{\sum _{j}k_{j}^{\alpha }}},}$

где - постоянный положительный показатель степени. Если , NLPA сводится к модели BA и называется «линейной». Если NLPA упоминается как «сублинейный», а степень распределения сети стремится к растянутому экспоненциальному распределению . Если , NLPA упоминается как «суперлинейный», и небольшое количество узлов подключается почти ко всем другим узлам в сети. Для обоих и свойство сети без масштабирования нарушается в пределе бесконечного размера системы. Однако, если только немного больше , NLPA может привести к распределению степеней, которое временно не масштабируется. ^[18]${\displaystyle \alpha }$${\displaystyle \alpha =1}$${\displaystyle 0<\alpha <1}$${\displaystyle \alpha >1}$${\displaystyle \alpha <1}$${\displaystyle \alpha >1}$${\displaystyle \alpha }$${\displaystyle 1}$

История [ править ]

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

См. Также [ править ]

• Модель Бьянкони – Барабаши
• Китайский ресторанный процесс
• Сложные сети
• Модель Эрдеша – Реньи (ER)
• Модель цены
• Теория перколяции
• Безмасштабная сеть
• Сеть малого мира
• Модель Уоттса и Строгаца

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

Внешние ссылки [ править ]

• "Этот человек мог править миром"
• "Реализация Java для Барабаши – Альберта"
• "Создание графов модели Барабаши – Альберта в коде"