Модель Барабаши – Альберта - Barabási–Albert model

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

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

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

Концепции

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

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

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

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

Алгоритм

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

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

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

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

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

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

Характеристики

Распределение степеней

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

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

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

Распределение индекса Хирша

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

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

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

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

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

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

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

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

Перколяция

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

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

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

${displaystyle n_ {kell} = {frac {4left (ell -1ight)} {kleft (k + 1ight) left (k + ell ight) left (k + ell + 1ight) left (k + ell + 2ight)}} + {frac {12left (ell -1ight)} {kleft (k + ell -1ight) left (k + ell ight) left (k + ell + 1ight) left (k + ell + 2ight)}}.}.}$

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

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

${displaystyle p (k, ell) = {frac {2m (m + 1)} {k (k + 1) ell (ell +1)}} слева [1- {frac {{inom {2m + 2} {m +1}} {inom {k + ell -2m} {ell -m}}} {inom {k + ell +2} {ell +1}}} ight].}$

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

${displaystyle p (ell mid k) = {frac {m (k + 2)} {kell (ell +1)}} left [1- {frac {{inom {2m + 2} {m + 1}} {inom {k + ell -2m} {ell -m}}} {inom {k + ell +2} {ell +1}}} ight].}$

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

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

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

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

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

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

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

Спектральная плотность модели БА имеет форму, отличную от полукруглой спектральной плотности случайного графа. Он имеет форму треугольника, вершина которого лежит значительно выше полукруга, а края затухают по степенному закону.^[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 также может быть охарактеризована обобщенная степень ${displaystyle q}$, произведение квадратного корня из времени рождения каждого узла и их соответствующей степени ${displaystyle k}$вместо степени ${displaystyle k}$ одинокие с момента рождения имеют значение в сети BA. Мы находим, что обобщенное распределение степеней ${displaystyle F (q, t)}$ имеет некоторые нетривиальные особенности и экспонаты динамическое масштабирование

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

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

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

Модель А

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

Модель B

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

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

История

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

Смотрите также

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

Рекомендации

внешняя ссылка

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