Безмасштабная сеть

Распределение степеней для сети с 150000 вершинами и средней степенью = 6, созданной с использованием модели Барабаши – Альберта (синие точки). Распределение следует аналитической форме, заданной отношением двух гамма-функций (черная линия), которое аппроксимируется степенным законом.

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

Безмасштабная сеть представляет собой сеть , чья степень распределения следует степенному закону , по крайней мере , асимптотический. То есть, фракция Р ( к ) узлов в сети , имеющей K соединения с другими узлами идет при больших значениях к , как

${\ Displaystyle Р (к) \ \ сим \ к ^ {\ boldsymbol {- \ gamma}}}$

где - параметр, значение которого обычно находится в диапазоне 2 << 3 (где второй момент ( параметр масштаба ) бесконечен, но первый момент конечен), хотя иногда он может выходить за эти границы. ^{[1] [2]}${\ displaystyle \ gamma}$${\ displaystyle \ gamma}$${\ Displaystyle к ^ {\ boldsymbol {- \ gamma}}}$

Сообщается, что многие сети не масштабируются, хотя статистический анализ опроверг многие из этих утверждений и серьезно поставил под сомнение другие. ^{[3] [4]} Кроме того, некоторые утверждали, что знание того, является ли распределение степеней жестким , более важно, чем знание того, является ли сеть безмасштабируемой согласно статистически строгим определениям. ^{[5] [6]} Предпочтительное присоединение и фитнес-модель были предложены в качестве механизмов для объяснения предполагаемых степенных распределений степеней в реальных сетях. Альтернативные модели, такие как суперлинейное предпочтительное креплениеможет показаться, что предпочтительное присоединение второго соседа порождает переходные безмасштабные сети, но степень распределения отклоняется от степенного закона, поскольку сети становятся очень большими. ^{[7] [8]}

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

В исследованиях сетей цитирования между научными статьями Дерек де Солла Прайс показал в 1965 году, что количество ссылок на статьи, т. Е. Количество цитирований, которые они получают, имеет распределение с тяжелыми хвостами в соответствии с распределением Парето или степенным законом , и таким образом, сеть цитирования не требует масштабирования. Однако он не использовал термин «безмасштабная сеть», который появился несколько десятилетий спустя. В более поздней статье в 1976 году Прайс также предложил механизм для объяснения возникновения степенных законов в сетях цитирования, который он назвал «кумулятивным преимуществом», но который сегодня более известен под названием « предпочтительное присоединение» .

Недавний интерес к безмасштабным сетям начался в 1999 году с работы Альберта-Ласло Барабаши и его коллег из Университета Нотр-Дам, которые составили карту топологии части всемирной паутины ^[9].обнаружив, что некоторые узлы, которые они назвали «концентраторами», имели гораздо больше соединений, чем другие, и что сеть в целом имела степенное распределение количества ссылок, соединяющихся с узлом. Обнаружив, что несколько других сетей, включая некоторые социальные и биологические сети, также имеют распределение степеней с тяжелым хвостом, Барабаши и его сотрудники придумали термин «безмасштабная сеть» для описания класса сетей, которые демонстрируют степенное распределение степеней. Однако, изучая семь примеров сетей в социальных, экономических, технологических, биологических и физических системах, Amaral et al. среди этих семи примеров не удалось найти немасштабируемую сеть. Только один из этих примеров, сеть киноактеров, имел распределение степеней P ( k) следуя степенному режиму для умеренных k , хотя в конечном итоге за этим степенным режимом последовало резкое обрезание, показывающее экспоненциальное затухание для больших k . ^[10]

Барабаши и Река Альберт предложили порождающий механизм для объяснения появления степенных распределений, который они назвали « преимущественной привязкой » и который по сути совпадает с предложенным Прайсом. Были представлены аналитические решения для этого механизма (также аналогично решению цена) в 2000 году Дороговцев, Мендес и Самухин ^[11] и независимо друг от друга Крапивский, Реднер и Leyvraz, а затем строго доказано математиком Бела Боллобас . ^[12] Примечательно, однако, что этот механизм создает только определенное подмножество сетей в безмасштабном классе, и с тех пор было обнаружено множество альтернативных механизмов. ^[13]

История безмасштабных сетей также включает некоторые разногласия. На эмпирическом уровне безмасштабный характер некоторых сетей был поставлен под сомнение. Например, три брата Фалаутсос считали, что Интернет имеет степенное распределение степеней на основе данных трассировки ; однако было высказано предположение, что это иллюзия уровня 3, созданная маршрутизаторами, которые выглядят как узлы высокого уровня, скрывая при этом внутреннюю структуру уровня 2 AS, которые они соединяют. ^[14]

На теоретическом уровне были предложены уточнения абстрактного определения безмасштабности. Например, Ли и др. (2005) недавно предложили потенциально более точную «безмасштабную метрику». Вкратце, пусть G - граф с множеством ребер E , и обозначим степень вершины (то есть количество инцидентных ребер ) через . Определять${\ displaystyle v}$${\ displaystyle v}$${\ Displaystyle \ deg (v)}$

${\ Displaystyle s (G) = \ sum _ {(u, v) \ in E} \ deg (u) \ cdot \ deg (v).}$

Это максимизируется, когда узлы высокого уровня подключены к другим узлам высокого уровня. Теперь определим

${\ Displaystyle S (G) = {\ гидроразрыва {s (G)} {s _ {\ max}}},}$

где s _макс максимальное значение х ( Н ) для H в множестве всех графов с распределением степени идентичны таковым  G . Это дает метрику от 0 до 1, где граф G с малым S ( G ) является «масштабируемым», а граф G с S ( G ), близким к 1, является «безмасштабным». Это определение отражает понятие самоподобия, подразумеваемое в названии «безмасштабный».

Обзор [ править ]

Есть два основных компонента, которые объясняют появление свойства безмасштабности в сложных сетях: рост и предпочтительное присоединение. ^[15] Под «ростом» понимается процесс роста, при котором в течение продолжительного периода времени новые узлы присоединяются к уже существующей системе, сети (например, всемирной паутине, которая за 10 лет выросла на миллиарды веб-страниц). Наконец, «предпочтительным присоединением» называется новый приходящий узел, который предпочитает подключаться к другому узлу, который уже имеет определенное количество связей с другими. Таким образом, существует высокая вероятность того, что все больше и больше узлов будет связывать себя с той одной , которая уже много ссылок, ведущих этот узел к концентратору в-штрафа . ^[9]В зависимости от сети концентраторы могут быть либо ассортативными, либо дезассортативными. Ассортативность можно найти в социальных сетях, в которых известные / известные люди будут лучше узнавать друг друга. Дизассортативность можно найти в технологических (Интернет, World Wide Web) и биологических (взаимодействие белков, метаболизм) сетях. ^[15]

Характеристики [ править ]

Наиболее примечательной характеристикой безмасштабной сети является относительная общность вершин со степенью, значительно превышающей среднее значение. Узлы наивысшего уровня часто называют «концентраторами», и считается, что они служат определенным целям в своих сетях, хотя это во многом зависит от домена.

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

Свойство безмасштабности сильно коррелирует с устойчивостью сети к сбоям. Оказывается, за крупными узлами следуют более мелкие. За этими меньшими узлами, в свою очередь, следуют другие узлы с еще меньшей степенью и так далее. Эта иерархия допускает отказоустойчивое поведение. Если отказы происходят случайно и подавляющее большинство узлов имеют небольшую степень, вероятность того, что это повлияет на концентратор, почти ничтожна. Даже если произойдет сбой концентратора, сеть, как правило, не потеряет связность., за счет оставшихся хабов. С другой стороны, если мы выберем несколько крупных хабов и вытащим их из сети, сеть превратится в набор довольно изолированных графов. Таким образом, концентраторы являются одновременно сильной стороной и слабостью безмасштабных сетей. Эти свойства были изучены аналитически с использованием теории перколяции Коэном и др. ^{[16] [17]} и Каллавей и др. ^[18] Коэн и др. ^[19] доказали, что для широкого диапазона безмасштабных сетей для критического порога перколяции . Это означает, что случайное удаление любой части узлов из сети не приведет к разрушению сети. В этом отличие от графа Эрдеша – Реньи, где , где${\ Displaystyle 2 <\ гамма <3}$ ${\ displaystyle p_ {c} = 0}$${\ displaystyle p_ {c} = 1 / {\ bar {k}}}$${\ displaystyle {\ bar {k}}}$это средняя степень. Обсуждаемые выше отказы случайны, как это обычно предполагается в теории перколяции. Однако при обобщении перколяции также на неслучайные, но целевые атаки, например, на узлы наивысшей степени, результаты, такие как , значительно изменяются. ^{[17] [18]} Недавно был разработан новый тип сбоев в сетях, названный локализованными атаками. ^[20] В этом случае случайным образом выбирается узел и удаляются его соседи и следующие ближайшие соседи до тех пор, пока не будет удалена часть 1-p узлов. Локализованные атаки делают масштабируемую сеть более уязвимой по сравнению со случайными атаками и${\ displaystyle p_ {c}}$${\ displaystyle p_ {c}> 0}$. Критические показатели просачивания в безмасштабных сетях отличаются от случайных сетей Эрдеша – Реньи. ^ [16a] Таким образом, безмасштабные сети относятся к другому классу универсальности, чем сети Эрдеша – Реньи.^[21]

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

Другой важной характеристикой безмасштабных сетей является распределение коэффициента кластеризации , которое уменьшается с увеличением степени узла. Это распределение также следует степенному закону. Это означает, что узлы с низкой степенью принадлежат очень плотным подграфам, и эти подграфы связаны друг с другом через концентраторы. Рассмотрим социальную сеть, узлами которой являются люди, а ссылками - отношения знакомства между людьми. Легко видеть, что люди склонны образовывать сообщества, т. Е. Небольшие группы, в которых каждый знает всех (такое сообщество можно представить как полный граф). Кроме того, у членов сообщества также есть несколько знакомых отношений с людьми за пределами этого сообщества. Однако некоторые люди связаны с большим количеством сообществ (например, знаменитости, политики). Этих людей можно считать центрами, ответственными за феномен маленького мира .

В настоящее время более конкретные характеристики безмасштабных сетей зависят от генеративного механизма, используемого для их создания. Например, сети, созданные с помощью предпочтительного присоединения, обычно размещают вершины с высокой степенью в середине сети, соединяя их вместе, чтобы сформировать ядро, а узлы с прогрессивной более низкой степенью составляют области между ядром и периферией. Случайное удаление даже большой части вершин очень мало влияет на общую связность сети, предполагая, что такие топологии могут быть полезны для безопасности., в то время как целевые атаки очень быстро разрушают связность. Другие безмасштабные сети, в которых вершины высокой степени размещаются на периферии, не проявляют этих свойств. Точно так же коэффициент кластеризации безмасштабных сетей может значительно варьироваться в зависимости от других топологических деталей.

Расстояние в безмасштабных сетях [ править ]

Еще одна характеристика касается среднего расстояния между двумя вершинами в сети. Как и в случае большинства неупорядоченных сетей, таких как модель сети малого мира , это расстояние очень мало по сравнению с высокоупорядоченной сетью, такой как решетчатый граф . Примечательно, что некоррелированный степенной граф, имеющий 2 <γ <3, будет иметь ультрамалый диаметр d ~ ln ln  N, где N - количество узлов в сети, как доказали Коэн и Хэвлин. ^[22] Таким образом, диаметр растущей безмасштабной сети на практике можно считать почти постоянным.

Иммунизация [ править ]

Вопрос о том, как иммунизировать эффективно масштабируемые свободные сети, которые представляют собой реалистичные сети, такие как Интернет и социальные сети, широко изучался. Одна из таких стратегий - иммунизация узлов с наибольшей степенью, то есть целенаправленные (преднамеренные) атаки ^{[16] [17],} поскольку в этом случае p относительно велико и требуется иммунизация меньшего количества узлов. Однако во многих реальных случаях глобальная структура недоступна, а узлы наибольшей степени неизвестны. Для таких случаев разработан метод ознакомительной иммунизации. ^[23] В этом случае, что довольно эффективно, узлы выбираются случайным образом, но иммунизируются их соседи. Другой, еще более эффективный метод основан на методе разбиения графов  ^[24]   .${\ displaystyle c}$

Свойства случайного графа могут изменяться или оставаться инвариантными при преобразованиях графа. Mashaghi A. et al., Например, продемонстрировали, что преобразование, которое преобразует случайные графы в их дуальные по ребрам графы (или линейные графы), дает ансамбль графов с почти одинаковым распределением степеней, но со степенью корреляции и значительно более высокой кластеризацией. коэффициент. Графы без масштабирования, как таковые, остаются без масштабирования при таких преобразованиях. ^[25]

Примеры [ править ]

Хотя многие сети реального мира считаются немасштабируемыми, доказательства часто остаются неубедительными, в первую очередь из-за растущего понимания более строгих методов анализа данных. ^[3] Таким образом, безмасштабный характер многих сетей все еще обсуждается в научном сообществе. Вот несколько примеров сетей, заявленных как немасштабируемые:

• Некоторые социальные сети , включая сети для совместной работы. Два примера, которые были тщательно изучены, - это сотрудничество киноактеров в фильмах и соавторство математиков в статьях .
• Многие виды компьютерных сетей , включая Интернет и веб-страницы во всемирной паутине .
• Графы зависимостей программного обеспечения, ^[26] некоторые из них описываются с помощью генеративной модели. ^[27]
• Некоторые финансовые сети, такие как сети межбанковских платежей ^{[28] [29]}
• Сети белок-белкового взаимодействия .
• Семантические сети . ^[30]
• Авиационные сети.

Безмасштабная топология также была обнаружена в высокотемпературных сверхпроводниках. ^[31] Свойства высокотемпературного сверхпроводника - соединения, в котором электроны подчиняются законам квантовой физики и движутся идеально синхронно, без трения - по-видимому, связаны с фрактальным расположением кажущихся случайными атомами кислорода и искажением решетки. ^[32]

Ячеистая структура, заполняющая пространство, взвешенная плоская стохастическая решетка (WPSL)недавно был предложен, распределение координационных чисел которого подчиняется степенному закону. Это означает, что в решетке есть несколько блоков, у которых есть удивительно большое количество соседей, с которыми они имеют общие границы. Его построение начинается с инициатора, скажем, квадрата единичной площади, и генератора, который случайным образом делит его на четыре блока. После этого генератор последовательно применяется снова и снова только к одному из доступных блоков, выбранных предпочтительно по отношению к их площадям. Это приводит к разделению квадрата на все более мелкие взаимоисключающие прямоугольные блоки. Двойник WPSL (DWPSL) получается путем замены каждого блока узлом в его центре, а общая граница между блоками с ребром, соединяющим две соответствующие вершины, получается как сеть, распределение степеней которой следует степенному закону.^{[33] [34]} Причина в том, что он растет в соответствии с правилом модели привязанности, основанной на посредничестве, которое также воплощает правило предпочтительной привязанности, но замаскировано.

Генеративные модели [ править ]

Безмасштабные сети возникают не случайно. Эрдеш и Реньи (1960) изучали модель роста графов, в которой на каждом шаге два узла выбираются равномерно случайным образом и между ними вставляется связь. Свойства этих случайных графов отличаются от свойств, обнаруженных в безмасштабных сетях, и поэтому необходима модель для этого процесса роста.

Наиболее широко известной генеративной моделью для подмножества безмасштабных сетей является генеративная модель богатого обогащения Барабаши и Альберта (1999), в которой каждая новая веб-страница создает ссылки на существующие веб-страницы с распределением вероятностей, которое не является равномерным, но пропорциональным текущее количество веб-страниц. Эта модель была первоначально изобретена Дереком Дж. Де Солла Прайсом в 1965 году под термином кумулятивное преимущество , но не стала популярной, пока Барабаши заново не открыл результаты под своим нынешним названием ( Модель BA.). Согласно этому процессу, страница с большим количеством внутренних ссылок будет привлекать больше внутренних ссылок, чем обычная страница. Это генерирует степенной закон, но результирующий граф отличается от реального веб-графа другими свойствами, такими как наличие небольших тесно связанных сообществ. Были предложены и изучены более общие модели и характеристики сети. Например, Pachon et al. (2018) предложили вариант генеративной модели `` богатые становятся богатыми '', которая учитывает два разных правила привязки: предпочтительный механизм привязки и единый выбор только для самых последних узлов. ^[35] См. Рецензию в книге Дороговцева и Мендеса . ^{[ необходима цитата ]} Некоторые механизмы, такие каксверхлинейное предпочтительное присоединение и присоединение второго соседа создают сети, которые временно не масштабируются, но отклоняются от степенного закона по мере роста сетей. ^{[7] [8]}

Несколько иную модель генерации веб-ссылок предложили Pennock et al. (2002). Они исследовали сообщества, интересующиеся определенной темой, например домашние страницы университетов, государственных компаний, газет или ученых, и отказались от основных узлов сети. В этом случае распределение ссылок больше не было степенным, а напоминало нормальное распределение . Основываясь на этих наблюдениях, авторы предложили генеративную модель, которая сочетает предпочтительную привязанность с базовой вероятностью получения ссылки.

Другой генеративной моделью является модель копирования, изученная Kumar et al. ^[36] (2000), в котором новые узлы выбирают существующий узел случайным образом и копируют часть связей существующего узла. Это также порождает степенной закон.

Рост сетей (добавление новых узлов) не является необходимым условием для создания безмасштабной сети. Одна из возможностей (Калдарелли и др., 2002) - рассматривать структуру как статическую и рисовать связь между вершинами в соответствии с определенным свойством двух задействованных вершин. После определения статистического распределения для этих свойств вершин (пригодности) оказывается, что в некоторых случаях также статические сети развивают безмасштабные свойства.

Обобщенная безмасштабная модель [ править ]

Эта статья требует внимания специалиста-математика . Добавьте причину или параметр обсуждения в этот шаблон, чтобы объяснить проблему со статьей. WikiProject Mathematics может помочь нанять эксперта. ( Июнь 2009 г. )

Наблюдается всплеск активности в области моделирования безмасштабных сложных сетей . Рецепт Барабаши и Альберта ^[37] сопровождался несколькими вариациями и обобщениями ^{[38] [39] [40] [41] [35]} и переработкой предыдущих математических работ. ^[42] Пока в модели есть степенное распределение, это безмасштабная сеть, а модель этой сети - безмасштабная модель.

Особенности [ править ]

Многие реальные сети (приблизительно) безмасштабные и, следовательно, требуют безмасштабных моделей для их описания. В схеме Прайса для построения безмасштабной модели необходимы два ингредиента:

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

2. Предпочтительное подключение : вероятность того, что новые узлы будут подключены к «старому» узлу.${\ displaystyle \ Pi}$

Обратите внимание, что фитнес-модели (см. Ниже) могут работать также статически, без изменения количества узлов. Следует также иметь в виду, что тот факт, что модели «предпочтительного присоединения» приводят к появлению безмасштабных сетей, не доказывает, что это механизм, лежащий в основе эволюции реальных безмасштабных сетей, поскольку могут существовать различные механизмы в работают в реальных системах, которые, тем не менее, требуют масштабирования.

Примеры [ править ]

Было предпринято несколько попыток создать безмасштабные свойства сети. Вот некоторые примеры:

Модель Барабаши – Альберта [ править ]

Модель Барабаши-Альберта , неориентированная версия модели цен, имеет линейную предпочтительную привязку и добавляет один новый узел на каждом временном шаге.${\ displaystyle \ Pi (k_ {i}) = {\ frac {k_ {i}} {\ sum _ {j} k_ {j}}}}$

(Обратите внимание, что еще одна общая черта в реальных сетях состоит в том , что существует ненулевая вероятность того, что новый узел присоединится к изолированному узлу. Таким образом, в общем случае имеет вид , где - начальная привлекательность узла.)${\displaystyle \Pi (k)}$${\displaystyle \Pi (0)\neq 0}$${\displaystyle \Pi (k)}$${\displaystyle \Pi (k)=A+k^{\alpha }}$${\displaystyle A}$

Двухуровневая сетевая модель [ править ]

Дангалчев ^[43] строит модель 2-L, учитывая важность каждого из соседей целевого узла в предпочтительном присоединении. Привлекательность узла в модели 2-L зависит не только от количества узлов, связанных с ним, но и от количества связей в каждом из этих узлов.

${\displaystyle \Pi (k_{i})={\frac {k_{i}+C\sum _{(i,j)}k_{j}}{\sum _{j}k_{j}+C\sum _{j}k_{j}^{2}}},}$

где C - коэффициент от 0 до 1.

Вариант модели 2-L, модель k2, где первый и второй соседние узлы в равной степени способствуют привлекательности целевого узла, демонстрирует появление переходных безмасштабных сетей. ^[8] В модели k2 распределение степеней кажется приблизительно безмасштабным, пока сеть относительно мала, но по мере роста сети появляются значительные отклонения от безмасштабного режима. Это приводит к тому, что относительная привлекательность узлов в разной степени меняется со временем, что также наблюдается в реальных сетях.

Модель привязанности, управляемой агрегатором (MDA) [ править ]

В модели привязки, управляемой посредничеством (MDA) , новый узел, имеющий ребра, выбирает существующий связанный узел случайным образом, а затем соединяется сам, но не с этим, а со своими соседями, также выбранными случайным образом. Вероятность того, что выбранный узел существующего узла равна${\displaystyle m}$${\displaystyle m}$${\displaystyle \Pi (i)}$${\displaystyle i}$

${\displaystyle \Pi (i)={\frac {k_{i}}{N}}{\frac {\sum _{j=1}^{k_{i}}{\frac {1}{k_{j}}}}{k_{i}}}.}$

Фактор является обратной величиной гармонического среднего (IHM) степеней соседей узла . Обширные численные исследования показывают, что приблизительно для среднего значения IHM в большом пределе становится постоянным, что означает . Это означает, что чем выше количество ссылок (степень) у узла, тем выше его шанс получить больше ссылок, поскольку они могут быть достигнуты большим количеством способов через посредников, которые, по сути, воплощают интуитивную идею механизма обогащения и обогащения (или предпочтительного правило присоединения модели Барабаши – Альберта). Таким образом, можно увидеть, что сеть MDA следует правилу PA, но замаскировано. ^[44]${\displaystyle {\frac {\sum _{j=1}^{k_{i}}{\frac {1}{k_{j}}}}{k_{i}}}}$${\displaystyle k_{i}}$${\displaystyle i}$${\displaystyle m>14}$${\displaystyle N}$${\displaystyle \Pi (i)\propto k_{i}}$

Однако, поскольку он описывает механизм, победитель получает все, поскольку мы обнаруживаем, что почти все узлы имеют степень один, а один - супербогатый по степени. По мере увеличения ценности неравенство между сверхбогатыми и бедными уменьшается, и по мере того, как мы находим механизм перехода от богатого становиться сверхбогатым к богатому - становиться богаче.${\displaystyle m=1}$${\displaystyle 99\%}$${\displaystyle m}$${\displaystyle m>14}$

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

Модель Барабаши-Альберта предполагает, что вероятность того, что узел присоединится к узлу , пропорциональна степени узла . Это предположение включает две гипотезы: во-первых, это зависит от , в отличие от случайных графов, в которых , и во-вторых, что функциональная форма линейна по . Точная форма не обязательно является линейной, и недавние исследования показали, что распределение степеней сильно зависит от${\displaystyle \Pi (k)}$${\displaystyle i}$ ${\displaystyle k}$${\displaystyle i}$${\displaystyle \Pi (k)}$${\displaystyle k}$${\displaystyle \Pi (k)=p}$${\displaystyle \Pi (k)}$${\displaystyle k}$${\displaystyle \Pi (k)}$${\displaystyle \Pi (k)}$

Крапивский, Реднер и Лейвраз ^[40] демонстрируют, что безмасштабный характер сети разрушается из-за нелинейного предпочтительного присоединения. Единственный случай, когда топология сети не требует масштабирования, - это тот, в котором предпочтительное присоединение является асимптотически линейным, т . Е. Как . В этом случае уравнение скорости приводит к${\displaystyle \Pi (k_{i})\sim a_{\infty }k_{i}}$${\displaystyle k_{i}\to \infty }$

${\displaystyle P(k)\sim k^{-\gamma }{\text{ with }}\gamma =1+{\frac {\mu }{a_{\infty }}}.}$

Таким образом, показатель степени распределения может быть настроен на любое значение от 2 до .${\displaystyle \infty }$

Иерархическая сетевая модель [ править ]

Иерархические сетевые модели по своей конструкции не требуют масштабирования и имеют высокую кластеризацию узлов. ^[45]

В итерационной конструкции приводит к иерархической сети. Начиная с полностью подключенного кластера из пяти узлов, мы создаем четыре идентичные реплики, соединяющие периферийные узлы каждого кластера с центральным узлом исходного кластера. Из этого мы получаем сеть из 25 узлов ( N  = 25). Повторяя тот же процесс, мы можем создать еще четыре реплики исходного кластера - четыре периферийных узла каждого из них подключаются к центральному узлу узлов, созданных на первом этапе. Это дает N  = 125, и процесс может продолжаться бесконечно.

Фитнес-модель [ править ]

Идея состоит в том, что связь между двумя вершинами назначается не случайным образом с вероятностью p, равной для всех пар вершин. Скорее, для каждой вершины j существует внутренняя пригодность x _j, и связь между вершиной i и j создается с вероятностью . ^[46] В случае Всемирной торговой сети возможно реконструировать все свойства, используя в качестве пригодности страны их ВВП, и принимая${\displaystyle p(x_{i},x_{j})}$

${\displaystyle p(x_{i},x_{j})={\frac {\delta x_{i}x_{j}}{1+\delta x_{i}x_{j}}}.}$^[47]

Гиперболические геометрические графики [ править ]

Предполагая, что в основе сети лежит гиперболическая геометрия, можно использовать структуру пространственных сетей для создания безмасштабных распределений степеней. Это неоднородное распределение степеней тогда просто отражает отрицательную кривизну и метрические свойства лежащей в основе гиперболической геометрии. ^[48]

Край двойного преобразования для генерации свободных графиков масштаба с заданными свойствами [ редактировать ]

Начиная с графов без шкалы с низкой степенью корреляции и коэффициентом кластеризации, можно генерировать новые графы с гораздо более высокой степенью корреляции и коэффициентами кластеризации, применяя преобразование с двойным ребром. ^[25]

Модель Uniform-Preferential-Attachment (модель UPA) [ править ]

Модель UPA - это вариант модели предпочтительной привязанности (предложенной Пачоном и др.), Которая учитывает два разных правила привязанности: механизм предпочтительной привязанности (с вероятностью 1-p), который подчеркивает систему «богатый становится богаче», и единый выбор. (с вероятностью p) для самых последних узлов. Эта модификация интересна для изучения устойчивости безмасштабного поведения распределения степеней. Аналитически доказано сохранение асимптотически степенного распределения степеней. ^[35]

Безмасштабные идеальные сети [ править ]

В контексте сетевой теории безмасштабная идеальная сеть является случайной сетью с распределением степени после безмасштабной идеального газа распределения плотности . Эти сети способны воспроизводить распределение по размерам городов и результаты выборов, раскрывая распределение социальных групп по размеру с помощью теории информации в сложных сетях, когда к сети применяется процесс роста конкурентных кластеров. ^{[49] [50]} В моделях безмасштабных идеальных сетей можно продемонстрировать, что число Данбара является причиной явления, известного как « шесть степеней разделения ».

Характеристики романа [ править ]

Для безмасштабной сети с узлами и степенным показателем индуцированный подграф, построенный из вершин со степенями больше, чем безмасштабная сеть с , почти наверняка . ^[51]${\displaystyle n}$${\displaystyle \gamma >3}$${\displaystyle \log {n}\times \log ^{*}{n}}$${\displaystyle \gamma '=2}$

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

• Случайный граф  - график, созданный случайным процессом
• Модель Эрдеша – Реньи  - две тесно связанные модели для генерации случайных графов.
• Нелинейная предпочтительная привязка
• Конденсация Бозе – Эйнштейна (теория сетей)
• Масштабная инвариантность
• Сложная сеть  - Сеть с нетривиальными топологическими характеристиками.
• Webgraph
• Модель Барабаши – Альберта
• Модель Бьянкони – Барабаши

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

Дальнейшее чтение [ править ]

• Альберт Р .; Барабаши А.-Л. (2002). «Статистическая механика сложных сетей» . Ред. Мод. Phys . 74 (1): 47–97. arXiv : cond-mat / 0106096 . Bibcode : 2002RvMP ... 74 ... 47 . DOI : 10.1103 / RevModPhys.74.47 . S2CID  60545 .
• Amaral LAN, Scala A, Barthelemy M, Stanley HE (2000). «Классы сетей малого мира» . PNAS . 97 (21): 11149–52. arXiv : cond-mat / 0001458 . Bibcode : 2000PNAS ... 9711149A . DOI : 10.1073 / pnas.200327197 . PMC  17168 . PMID  11005838 .
• Барабаши, Альберт-Ласло (2004). Связано: как все связано со всем остальным . ISBN 0-452-28439-2.
• Барабаши, Альберт-Ласло; Бонабо, Эрик (май 2003 г.). «Безмасштабные сети» (PDF) . Scientific American . 288 (5): 50–9. Bibcode : 2003SciAm.288e..60B . DOI : 10.1038 / Scientificamerican0503-60 . PMID  12701331 .
• Дан Браха; Янир Бар-Ям (2004). «Топология крупномасштабных инженерных сетей для решения проблем» (PDF) . Phys. Rev. E . 69 (1): 016113. Bibcode : 2004PhRvE..69a6113B . DOI : 10.1103 / PhysRevE.69.016113 . PMID  14995673 . S2CID  1001176 .
• Калдарелли Г. " Безмасштабные сети", издательство Оксфордского университета, Оксфорд (2007).
• Caldarelli G .; Capocci A .; De Los Rios P ​​.; Муньос М.А. (2002). «Безмасштабные сети с изменяющейся внутренней пригодностью вершин». Письма с физическим обзором . 89 (25): 258702. arXiv : cond-mat / 0207366 . Bibcode : 2002PhRvL..89y8702C . DOI : 10.1103 / PhysRevLett.89.258702 . PMID  12484927 .
• Р. Коэн; К. Эрез; Д. бен-Авраам; С. Хавлин (2000). «Устойчивость Интернета к случайным сбоям». Phys. Rev. Lett . 85 (21): 4626–8. arXiv : cond-mat / 0007048 . Полномочный код : 2000PhRvL..85.4626C . DOI : 10.1103 / PhysRevLett.85.4626 . PMID  11082612 . S2CID  15372152 .
• Р. Коэн; К. Эрез; Д. бен-Авраам; С. Хавлин (2001). «Разрушение Интернета при преднамеренной атаке». Phys. Rev. Lett . 86 (16): 3682–5. arXiv : cond-mat / 0010251 . Bibcode : 2001PhRvL..86.3682C . DOI : 10.1103 / PhysRevLett.86.3682 . PMID  11328053 . S2CID  3852896 .
• Р. Коэн; К. Эрез; Д. бен-Авраам; С. Хавлин (2002). «Безмасштабные сети на решетках» . Phys. Rev. Lett . 89 (21): 218701. arXiv : cond-mat / 0205613 . Bibcode : 2002PhRvL..89u8701R . DOI : 10.1103 / physrevlett.89.218701 . PMID  12443452 . S2CID  13379794 .
• Дангалчев, Ч. (2004). «Модели генерации безмасштабных сетей» . Physica . 338 (3–4): 659–671. Bibcode : 2004PhyA..338..659D . DOI : 10.1016 / j.physa.2004.01.056 .
• Дороговцев С. Н.; Mendes, JFF; Самухин, АН (2000). «Структура растущих сетей: точное решение модели Барабаши-Альберта». Phys. Rev. Lett . 85 (21): 4633–6. arXiv : cond-mat / 0004434 . Bibcode : 2000PhRvL..85.4633D . DOI : 10.1103 / PhysRevLett.85.4633 . PMID  11082614 .
• Дороговцев С. Н.; Мендес, JFF (2003). Эволюция сетей: от биологических сетей к Интернету и WWW . Издательство Оксфордского университета. ISBN 0-19-851590-1.
• Дороговцев С. Н.; Гольцев А.В.; Мендес, JFF (2008). «Критические явления в сложных сетях». Ред. Мод. Phys . 80 (4): 1275–1335. arXiv : 0705.0010 . Bibcode : 2008RvMP ... 80.1275D . DOI : 10.1103 / RevModPhys.80.1275 . S2CID  3174463 .
• Дороговцев С. Н.; Мендес, JFF (2002). «Эволюция сетей». Успехи физики . 51 (4): 1079–1187. arXiv : cond-mat / 0106144 . Bibcode : 2002AdPhy..51.1079D . DOI : 10.1080 / 00018730110112519 . S2CID  429546 .
• Erdős, P .; Реньи, А. (1960). Об эволюции случайных графов (PDF) . 5 . Издание Математического института Венгерской академии наук. С. 17–61.
• Faloutsos, M .; Faloutsos, P .; Фалуцос, К. (1999). «О степенных отношениях топологии Интернет». Комп. Comm. Ред . 29 (4): 251–262. DOI : 10.1145 / 316194.316229 .
• Li, L .; Alderson, D .; Tanaka, R .; Дойл, JC; Виллинджер, В. (2005). «К теории безмасштабных графов: определение, свойства и значения (расширенная версия)». arXiv : cond-mat / 0501169 .
• Kumar, R .; Raghavan, P .; Rajagopalan, S .; Sivakumar, D .; Tomkins, A .; Упфаль, Э. (2000). «Стохастические модели для веб-графа» (PDF) . Материалы 41-го ежегодного симпозиума по основам информатики (FOCS) . Редондо-Бич, Калифорния: IEEE CS Press. С. 57–65.
• Матлис, янв (4 ноября 2002 г.). «Безмасштабные сети» .
• Ньюман, Марк EJ (2003). «Структура и функции сложных сетей». SIAM Обзор . 45 (2): 167–256. arXiv : cond-mat / 0303516 . Bibcode : 2003SIAMR..45..167N . DOI : 10.1137 / S003614450342480 . S2CID  221278130 .
• Pastor-Satorras, R .; Веспиньяни, А. (2004). Эволюция и структура Интернета: подход статистической физики . Издательство Кембриджского университета. ISBN 0-521-82698-5.
• Пеннок, DM; Flake, GW; Лоуренс, S .; Гловер, EJ; Джайлз, CL (2002). «Победители не получают все: характеристика конкуренции за ссылки в сети» . PNAS . 99 (8): 5207–11. Bibcode : 2002PNAS ... 99.5207P . DOI : 10.1073 / pnas.032085699 . PMC  122747 . PMID  16578867 .
• Робб, Джон. Безмасштабные сети и терроризм , 2004 г.
• Келлер, EF (2005). «Пересмотр« безмасштабных »сетей» . BioEssays . 27 (10): 1060–8. DOI : 10.1002 / bies.20294 . PMID  16163729 . Архивировано из оригинала на 2011-08-13.
• Оноды, РН; де Кастро, Пенсильвания (2004). «Комплексное сетевое исследование бразильского футболиста». Phys. Rev. E . 70 (3): 037103. arXiv : cond-mat / 0409609 . Bibcode : 2004PhRvE..70c7103O . DOI : 10.1103 / PhysRevE.70.037103 . PMID  15524675 . S2CID  31653489 .
• Реувен Коэн; Шломо Хавлин (2003). «Безмасштабные сети - это сверхмалые размеры» . Phys. Rev. Lett . 90 (5): 058701. arXiv : cond-mat / 0205476 . Bibcode : 2003PhRvL..90e8701C . DOI : 10.1103 / PhysRevLett.90.058701 . PMID  12633404 . S2CID  10508339 .
• Kasthurirathna, D .; Пиравеенан, М. (2015). «Комплексное сетевое исследование бразильского футболиста». Sci. Rep . В прессе.