Модель Барабаши – Альберта (BA) - это алгоритм для создания случайных безмасштабных сетей с использованием механизма предпочтительного присоединения . Несколько естественных и созданных руками человека систем, включая Интернет , всемирную паутину , сети цитирования и некоторые социальные сети , считаются приблизительно безмасштабируемыми и определенно содержат несколько узлов (называемых концентраторами) с необычно высокой степенью по сравнению с другими. узлы сети. Модель BA пытается объяснить существование таких узлов в реальных сетях. Алгоритм назван в честь его изобретателей Альберта-Ласло Барабаши и Река Альберта.и является частным случаем более ранней и более общей модели, называемой моделью Прайса . [1]
Концепции
Многие наблюдаемые сети (по крайней мере приблизительно) попадают в класс безмасштабных сетей , что означает, что они имеют степенное (или безмасштабное) распределение степеней, в то время как модели случайных графов, такие как модель Эрдеша – Реньи (ER) и Модель Уоттса – Строгаца (WS) не демонстрирует степенных законов. Модель Барабаши – Альберта - одна из нескольких предложенных моделей, которые генерируют безмасштабные сети. Он включает в себя две важные общие концепции: рост и предпочтительную привязанность . И рост, и предпочтительная привязанность широко распространены в реальных сетях.
Рост означает, что количество узлов в сети увеличивается со временем.
Предпочтительное присоединение означает, что чем больше подключен узел, тем больше вероятность, что он получит новые ссылки. Узлы с более высокой степенью имеют более сильную способность захватывать ссылки, добавленные в сеть. Интуитивно предпочтительную привязанность можно понять, если подумать о социальных сетях, соединяющих людей. Здесь связь от A к B означает, что человек A «знает» или «знаком с» человеком B. Сильно связанные узлы представляют хорошо известных людей с множеством отношений. Когда новичок входит в сообщество, он с большей вероятностью познакомится с одним из этих более заметных людей, чем с относительно неизвестным. Модель BA была предложена исходя из предположения, что во всемирной паутине новые страницы ссылаются преимущественно на хабы, то есть на очень известные сайты, такие как Google , а не на страницы, о которых мало кто знает. Если кто-то выбирает новую страницу для ссылки, случайным образом выбирая существующую ссылку, вероятность выбора конкретной страницы будет пропорциональна ее степени. Модель BA утверждает, что это объясняет правило предпочтительной вероятности прикрепления. Однако, несмотря на то, что модель является весьма полезной, эмпирические данные свидетельствуют о том, что этот механизм в его простейшей форме не применим к всемирной паутине, как показано в «Техническом комментарии к« Появлению масштабирования в случайных сетях » » .
Позже модель Бьянкони-Барабаши работает над решением этой проблемы, вводя параметр «приспособленность». Предпочтительное присоединение - это пример цикла положительной обратной связи, когда изначально случайные вариации (один узел изначально имеет больше ссылок или начал накапливать ссылки раньше, чем другой) автоматически усиливаются, что значительно увеличивает различия. Это также иногда называют эффектом Мэтью : « богатые становятся богаче ». См. Также автокатализ .
Алгоритм
Сеть начинается с начальной подключенной сети из узлы.
Новые узлы добавляются в сеть по одному. Каждый новый узел подключен ксуществующие узлы с вероятностью, пропорциональной количеству связей, которые уже есть у существующих узлов. Формально вероятность что новый узел подключен к узлу это [2]
где степень узла и сумма производится по всем ранее существовавшим узлам (т.е. знаменатель дает удвоенное количество ребер в сети). Сильно связанные узлы («концентраторы») имеют тенденцию быстро накапливать еще больше ссылок, в то время как узлы только с несколькими ссылками вряд ли будут выбраны в качестве места назначения для новой ссылки. Новые узлы имеют «предпочтение» присоединяться к уже тесно связанным узлам.
Характеристики
Распределение степеней
Распределение степеней, полученное в рамках модели BA, является безмасштабным, в частности, это степенной закон вида
Распределение индекса Хирша
Было показано, что распределение индекса Хирша или индекса Хирша также не требует масштабирования и было предложено в качестве индекса лобби для использования в качестве меры центральности [4]
Кроме того, аналитический результат для плотности узлов с h-индексом 1 может быть получен в случае, когда
Средняя длина пути
Средняя длина пути модели БА увеличивается примерно логарифмически с размером сети. Фактическая форма имеет двойную логарифмическую поправку и выглядит как [5]
Модель BA имеет систематически более короткую среднюю длину пути, чем случайный граф.
Перколяция
Порог перколяции модели БА оказался равным pc = 0. [6] Это означает, что при случайном удалении узлов в сети BA любая часть узлов не нарушит сеть. С другой стороны, удаление только относительно небольшой части узлов наивысшего уровня вызовет коллапс сети. [7]
Корреляции степени узла
Корреляции между степенями связанных узлов развиваются спонтанно в модели BA из-за того, как развивается сеть. Вероятность,, поиска ссылки, которая соединяет узел степени к предковому узлу степени в модели БА для частного случая (Дерево БА) задается формулой
Это подтверждает существование степени корреляции, потому что, если бы распределения были некоррелированными, мы бы получили . [2]
Для общего , доля ссылок, которые соединяют узел степени в узле степени это [8]
Кроме того, распределение степени ближайшего соседа , то есть распределение степеней соседей узла со степенью , дается формулой [8]
Другими словами, если мы выберем узел со степенью , а затем случайным образом выберите одного из его соседей, вероятность того, что этот случайно выбранный сосед будет иметь степень дается выражением выше.
Коэффициент кластеризации
Аналитический результат для коэффициента кластеризации модели BA был получен Клеммом и Эгуилусом [9] и доказан Боллобасом. [10] [11] Метод среднего поля для изучения коэффициента кластеризации был применен Фрончаком, Фрончаком и Холистом. [12]
Это поведение по-прежнему отличается от поведения сетей малого мира, где кластеризация не зависит от размера системы. В случае иерархических сетей кластеризация как функция степени узла также следует степенному закону,
Этот результат был получен аналитически Дороговцевым, Гольцевым и Мендесом. [13]
Спектральные свойства
Спектральная плотность модели BA имеет форму, отличную от полукруглой спектральной плотности случайного графа. Он имеет форму треугольника, вершина которого лежит значительно выше полукруга, а края затухают по степенному закону. [14]
Динамическое масштабирование
По определению, модель BA описывает явление развития во времени и, следовательно, помимо ее свойства отсутствия масштабирования, можно также искать ее свойство динамического масштабирования. В сети БА узлы также могут характеризоваться обобщенной степенью, произведение квадратного корня из времени рождения каждого узла и их соответствующей степени , вместо степени одинокие с момента рождения имеют значение в сети BA. Мы находим, что обобщенное распределение степенейимеет некоторые нетривиальные функции и демонстрирует динамическое масштабирование
Это означает, что различные сюжеты против рухнет в универсальную кривую, если мы построим график против . [15]
Предельные случаи
Модель А
Модель A сохраняет рост, но не включает предпочтительную привязанность. Вероятность подключения нового узла к любому уже существующему узлу равна. Результирующее распределение степеней в этом пределе является геометрическим [16], что указывает на то, что одного роста недостаточно для создания безмасштабной структуры.
Модель B
Модель B сохраняет предпочтительную привязанность, но исключает рост. Модель начинается с фиксированного числа отключенных узлов и добавляет ссылки, предпочтительно выбирая узлы высокого уровня в качестве пунктов назначения. Хотя распределение степеней в начале моделирования выглядит безмасштабным, распределение нестабильно и в конечном итоге становится почти гауссовым, когда сеть приближается к насыщению. Таким образом, одного лишь предпочтительного крепления недостаточно для создания структуры без накипи.
Неспособность моделей A и B привести к безмасштабному распределению указывает на то, что рост и предпочтительное присоединение необходимы одновременно для воспроизведения стационарного степенного распределения, наблюдаемого в реальных сетях. [2]
Нелинейная предпочтительная привязка
Модель BA можно рассматривать как частный случай более общей модели нелинейной предпочтительной привязанности (NLPA). [17] Алгоритм NLPA идентичен модели BA с заменой вероятности прикрепления более общей формой
где - постоянный положительный показатель. Если, NLPA сводится к модели BA и называется «линейной». Если, NLPA называется «сублинейным», и степень распределения сети стремится к растянутому экспоненциальному распределению . Если, NLPA называется «суперлинейным», и небольшое количество узлов подключается почти ко всем остальным узлам в сети. Для обоих а также , свойство сети безмасштабности нарушается в пределе бесконечного размера системы. Однако если лишь немного больше, чем , NLPA может привести к распределению степеней, которое временно не масштабируется. [18]
История
Преимущественная привязка впервые появилась в 1923 году в знаменитой урной модели венгерского математика Дьёрдя Поли в 1923 году. [19] Современный метод главного уравнения, который дает более прозрачный вывод, был применен к задаче Гербертом А. Саймоном в 1955 году. [20] в процессе изучения размеров городов и других явлений. Впервые он был применен к росту сетей Дереком де Солла Прайсом в 1976 году. [21] Прайс интересовался сетями цитирования между научными статьями, и модель Прайса использовала «кумулятивное преимущество» (его имя для предпочтительной привязанности) для получения направленная сеть, поэтому модель Барабаши-Альберта является неориентированной версией модели Прайса . Название «предпочтительное присоединение» и нынешняя популярность безмасштабных сетевых моделей обусловлены работой Альберта-Ласло Барабаши и Рики Альберта , которые заново открыли этот процесс независимо в 1999 году и применили его к распределению степеней в сети. [3]
Смотрите также
- Модель Бьянкони – Барабаши
- Китайский ресторанный процесс
- Сложные сети
- Модель Эрдеша – Реньи (ER)
- Модель цены
- Теория перколяции
- Безмасштабная сеть
- Сеть малого мира
- Модель Уоттса и Строгаца
Рекомендации
- ^ Альберт, Река; Барабаши, Альберт-Ласло (2002). «Статистическая механика сложных сетей». Обзоры современной физики . 74 (1): 47–97. arXiv : cond-mat / 0106096 . Bibcode : 2002RvMP ... 74 ... 47 . CiteSeerX 10.1.1.242.4753 . DOI : 10.1103 / RevModPhys.74.47 . ISSN 0034-6861 .
- ^ а б в Альберт, Река ; Барабаши, Альберт-Ласло (2002). «Статистическая механика сложных сетей» (PDF) . Обзоры современной физики . 74 (47): 47–97. arXiv : cond-mat / 0106096 . Bibcode : 2002RvMP ... 74 ... 47 . CiteSeerX 10.1.1.242.4753 . DOI : 10.1103 / RevModPhys.74.47 . Архивировано из оригинального (PDF) 24 августа 2015 года.
- ^ а б Барабаши, Альберт-Ласло ; Альберт, Река (октябрь 1999 г.). «Появление масштабирования в случайных сетях» (PDF) . Наука . 286 (5439): 509–512. arXiv : cond-mat / 9910332 . Bibcode : 1999Sci ... 286..509B . DOI : 10.1126 / science.286.5439.509 . PMID 10521342 . Архивировано из оригинального (PDF) 17 апреля 2012 года.
- ^ Корн, А .; Шуберт, А .; Телч, А. (2009). «Индекс лобби в сети». Physica . 388 (11): 2221–2226. arXiv : 0809.0514 . Bibcode : 2009PhyA..388.2221K . DOI : 10.1016 / j.physa.2009.02.013 .
- ^ Коэн, Реувен; Хавлин, Шломо (2003). «Безмасштабные сети - сверхмалые». Письма с физическим обзором . 90 (5): 058701. arXiv : cond-mat / 0205476 . Bibcode : 2003PhRvL..90e8701C . DOI : 10.1103 / PhysRevLett.90.058701 . ISSN 0031-9007 . PMID 12633404 .
- ^ Р. Коэн, К. Эрез, Д. Бен-Авраам, С. Хэвлин (2000). «Устойчивость Интернета к случайным сбоям». Phys. Rev. Lett . 85 : 4626.CS1 maint: использует параметр авторов ( ссылка )
- ^ Р. Коэн, К. Эрез, Д. Бен-Авраам, С. Хэвлин (2001). «Обрыв Интернета при преднамеренной атаке». Phys. Rev. Lett . 86 : 3682.CS1 maint: использует параметр авторов ( ссылка )
- ^ а б Фотухи, Бабак; Раббат, Майкл (2013). «Степенная корреляция в безмасштабных графиках». Европейский физический журнал B . 86 (12): 510. arXiv : 1308.5169 . Bibcode : 2013EPJB ... 86..510F . DOI : 10.1140 / epjb / e2013-40920-6 .
- ^ Klemm, K .; Эгуилуз, ВК (2002). «Растущие безмасштабные сети с поведением маленького мира». Physical Review E . 65 (5): 057102. arXiv : cond-mat / 0107607 . Bibcode : 2002PhRvE..65e7102K . DOI : 10.1103 / PhysRevE.65.057102 . hdl : 10261/15314 . PMID 12059755 .
- ^ Боллобаш, Б. (2003). «Математические результаты по безмасштабным случайным графам». Справочник по графам и сетям . С. 1–37. CiteSeerX 10.1.1.176.6988 .
- ^ «Математические результаты по безмасштабным случайным графам». 2003: 1–37. CiteSeerX 10.1.1.176.6988 . Цитировать журнал требует
|journal=
( помощь ) - ^ Альберт, Река; Барабаши, Альберт-Ласло; Холист, Януш А (2003). "Теория среднего поля для коэффициентов кластеризации в сетях Барабаши-Альберта". Phys. Rev. E . 68 (4): 046126. arXiv : cond-mat / 0306255 . DOI : 10.1103 / PhysRevE.68.046126 . PMID 14683021 .
- ^ Дороговцев С.Н.; Гольцев, А.В.; Мендес, JFF (25 июня 2002 г.). «Псевдофрактальная безмасштабная паутина». Physical Review E . 65 (6): 066122. arXiv : cond-mat / 0112143 . Bibcode : 2002PhRvE..65f6122D . DOI : 10.1103 / PhysRevE.65.066122 . PMID 12188798 .
- ^ Farkas, IJ; Derényi, I .; Barabási, A.-L .; Вичек, Т. (20 июля 2001 г.) [19 февраля 2001 г.]. «Спектры« реальных »графов: Вне закона полукруга». Physical Review E . 64 (2): 026704. arXiv : cond-mat / 0102335 . Bibcode : 2001PhRvE..64b6704F . DOI : 10.1103 / PhysRevE.64.026704 . HDL : 2047 / d20000692 . PMID 11497741 .
- ^ MK Hassan, MZ Hassan и NI Pavel, «Динамическое масштабирование, коллапс данных и самоподобие в сетях Барабаши-Альберта» J. Phys. A: Математика. Теор. 44 175101 (2011) https://dx.doi.org/10.1088/1751-8113/44/17/175101
- ^ Пекоз, Эрол; Роллин, А .; Росс, Н. (2012). «Границы полной вариации и локальной предельной погрешности геометрического приближения» . Бернулли .
- ^ Крапивский, ПЛ; Redner, S .; Лейвраз, Ф. (20 ноября 2000 г.). «Связность растущих случайных сетей». Письма с физическим обзором . 85 (21): 4629–4632. arXiv : конд-мат / 0005139 . DOI : 10.1103 / PhysRevLett.85.4629 .
- ^ Крапивский, Павел; Криуков, Дмитрий (21 августа 2008 г.). «Безмасштабные сети как преасимптотические режимы сверхлинейной преимущественной привязанности». Physical Review E . 78 (2): 026114. arXiv : 0804.1366 . DOI : 10.1103 / PhysRevE.78.026114 .
- ^ Альберт-Ласло, Барабаши (2012). «Замок или причина». Природа . 489 (7417): 507–508. DOI : 10.1038 / nature11486 . PMID 22972190 .
- ^ Саймон, Герберт А. (декабрь 1955 г.). «Об одном классе функций косого распределения». Биометрика . 42 (3–4): 425–440. DOI : 10.1093 / Biomet / 42.3-4.425 .
- ^ Прайс, ди-джей де Солла (сентябрь 1976 г.). «Общая теория библиометрических и других процессов накопления преимуществ». Журнал Американского общества информационных наук . 27 (5): 292–306. CiteSeerX 10.1.1.161.114 . DOI : 10.1002 / asi.4630270505 .
Внешние ссылки
- «Этот человек мог править миром»
- "Реализация Java для Барабаши – Альберта"
- "Создание графов модели Барабаши – Альберта в коде"