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

Сеть, распределение степеней которой подчиняется степенному закону

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

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

${\displaystyle P(k)\ \sim \ k^{\boldsymbol {-\gamma }}}$

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

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

История

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

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

Барабаши и Река Альберт предложили генеративный механизм для объяснения появления степенных распределений, который они назвали « предпочтительным присоединением » и который по сути совпадает с предложенным Прайсом. Аналитические решения для этого механизма (также похожие на решение Прайса) были представлены в 2000 году Дороговцевым, Мендесом и Самухиным ^[11] и независимо Крапивским, Реднером и Лейвразом, а позже строго доказаны математиком Белой Боллобашем . ^[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)={\frac {s(G)}{s_{\max }}},}$

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

Обзор

Когда концепция «безмасштабности» была первоначально введена в контексте сетей, ^[9] она в первую очередь относилась к определенной черте: степенному распределению для заданной переменной , выраженному как . Это свойство сохраняет свою форму при непрерывном масштабном преобразовании , вызывая параллели с методами ренормгруппы в статистической теории поля. ^{[15] [16]} ${\displaystyle k}$ ${\displaystyle f(k)\propto k^{-\gamma }}$ ${\displaystyle k\to k+\epsilon k}$

Однако есть ключевое различие. В статистической теории поля термин «масштаб» часто относится к размеру системы. В сфере сетей «масштаб» — это мера связности, обычно определяемая степенью узла, то есть числом связей, присоединенных к нему. Сети с большим числом узлов высокой степени считаются имеющими большую связность. ${\displaystyle k}$

Распределение степенных степеней позволяет нам делать «безмасштабные» утверждения о распространенности узлов высокой степени. ^[17] Например, мы можем сказать, что «узлы с тройной средней связностью встречаются в два раза реже, чем узлы со средней связностью». Конкретное численное значение того, что составляет «среднюю связность», становится неважным, будь то сотня или миллион. ^[18]

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

Случайная сеть (а) и безмасштабная сеть (б)

Сложное распределение степеней сети случайных и безмасштабных

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

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

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

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

Иммунизация

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

Свойства случайного графа могут изменяться или оставаться инвариантными при преобразованиях графа. Например, Машаги А. и др. продемонстрировали, что преобразование, которое преобразует случайные графы в их реберно-дуальные графы (или линейные графы), создает ансамбль графов с почти таким же распределением степеней, но с корреляциями степеней и значительно более высоким коэффициентом кластеризации. Графы без масштаба, как таковые, остаются без масштаба при таких преобразованиях. ^[19]

Примеры

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

• Некоторые социальные сети , включая сети сотрудничества. Два примера, которые были тщательно изучены, — это сотрудничество актеров в фильмах и соавторство математиков в статьях .
• Множество видов компьютерных сетей , включая Интернет и веб-графику Всемирной паутины .
• Некоторые финансовые сети, такие как межбанковские платежные сети ^{[20] [21]}
• Сети белок-белкового взаимодействия .
• Семантические сети . ^[22]
• Сети авиакомпаний.

Снимок взвешенной плоской стохастической решетки (WPSL)

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

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

Генеративные модели

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

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

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

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

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

Однако рост сетей (добавление новых узлов) не является необходимым условием для создания безмасштабной сети (см. Dangalchev ^[30] ). Одна из возможностей (Caldarelli et al. 2002) состоит в том, чтобы рассматривать структуру как статическую и проводить связь между вершинами в соответствии с определенным свойством двух вовлеченных вершин. После того, как определено статистическое распределение для этих свойств вершин (приспособленности), оказывается, что в некоторых обстоятельствах статические сети также развивают безмасштабные свойства.

Обобщенная безмасштабная модель

Наблюдается всплеск активности в моделировании масштабно-независимых комплексных сетей . Рецепт Барабаши и Альберта ^[31] был продолжен несколькими вариациями и обобщениями ^{[32] [33] [34] [35] [27]} и переработкой предыдущих математических работ. ^[36]

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

Функции

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

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

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

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

Примеры

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

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

Модель Барабаши–Альберта , ненаправленная версия модели Прайса, имеет линейное предпочтительное присоединение и добавляет один новый узел на каждом временном шаге. ${\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}$

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

Дангалчев (см. ^[30] ) строит модель 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, но замаскированно. ^[37] ${\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)}$

Крапивский, Реднер и Лейвраз ^[34] демонстрируют, что безмасштабная природа сети разрушается для нелинейного предпочтительного присоединения. Единственный случай, в котором топология сети является безмасштабной, это когда предпочтительное присоединение асимптотически линейно, т.е. как . В этом случае уравнение скорости приводит к ${\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 }$

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

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

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

Фитнес-модель

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

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

Гиперболические геометрические графы

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

Двойственное преобразование ребер для создания безмасштабных графов с желаемыми свойствами

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

Модель равномерной предпочтительной привязанности (модель UPA)

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

Идеальные сети без масштабирования

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

Новые характеристики

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

Оценка показателя степенного закона

Оценка показателя степени безмасштабной сети обычно выполняется с использованием оценки максимального правдоподобия со степенями нескольких равномерно выбранных узлов. ^[3] Однако, поскольку равномерная выборка не получает достаточного количества выборок из важного тяжелого хвоста распределения степенного закона, этот метод может дать большое смещение и дисперсию. Недавно было предложено выбирать случайных друзей (т. е. случайные концы случайных связей), которые с большей вероятностью попадают из хвоста распределения степеней в результате парадокса дружбы . [ ^{45] [46]} Теоретически оценка максимального правдоподобия со случайными друзьями приводит к меньшему смещению и меньшей дисперсии по сравнению с классическим подходом, основанным на равномерной выборке. ^[46] ${\displaystyle \gamma }$

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

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

Ссылки

1. Оннела, Ж.-П.; Сарамаки, Дж.; Хювонен, Дж.; Сабо, Г.; Лазер, Д.; Каски, К.; Кертес, Дж.; Барабаши, А. -Л. (2007). «Структура и прочность связей в сетях мобильной связи». Труды Национальной академии наук . 104 (18): 7332–7336. arXiv : physics/0610104 . Bibcode : 2007PNAS..104.7332O. doi : 10.1073/pnas.0610245104 . PMC  1863470. PMID  17456605 .
2. Хороманьски, К.; Матушак, М.; Мицкиш, Дж. (2013). «Безмасштабный граф с предпочтительным присоединением и развивающейся внутренней структурой вершин». Журнал статистической физики . 151 (6): 1175–1183. Bibcode : 2013JSP...151.1175C. doi : 10.1007/s10955-013-0749-1 .
3. Clauset, Aaron; Cosma Rohilla Shalizi; ME J Newman (2009). «Распределения степенного закона в эмпирических данных». SIAM Review . 51 (4): 661–703. arXiv : 0706.1062 . Bibcode : 2009SIAMR..51..661C. doi : 10.1137/070710111. S2CID  9155618.
4. Бройдо, Анна; Аарон Клаузет (2019-03-04). «Сети без масштабирования редки». Nature Communications . 10 (1): 1017. arXiv : 1801.03400 . Bibcode : 2019NatCo..10.1017B. doi : 10.1038/s41467-019-08746-5. PMC 6399239. PMID  30833554. 
5. Холм, Петтер (декабрь 2019 г.). «Редко и везде: Перспективы безмасштабных сетей». Nature Communications . 10 (1): 1016. Bibcode : 2019NatCo..10.1016H. doi : 10.1038/s41467-019-09038-8 . PMC 6399274. PMID  30833568 . 
6. Stumpf, MPH; Porter, MA (10 февраля 2012 г.). «Критические истины о степенных законах». Science . 335 (6069): 665–666. Bibcode :2012Sci...335..665S. doi :10.1126/science.1216142. PMID  22323807. S2CID  206538568.
7. Крапивский, Пол; Крюков, Дмитрий (21 августа 2008 г.). "Безмасштабные сети как предасимптотические режимы сверхлинейного предпочтительного присоединения". Physical Review E . 78 (2): 026114. arXiv : 0804.1366 . Bibcode :2008PhRvE..78b6114K. doi :10.1103/PhysRevE.78.026114. PMID  18850904. S2CID  14292535.
8. Фалькенберг, Макс; Ли, Чон-Хёк; Амано, Шун-ити; Огава, Кен-итиро; Яно, Казуо; Мияке, Ёсихиро; Эванс, Тим С.; Кристенсен, Ким (18 июня 2020 г.). «Определение зависимости от времени в росте сети». Physical Review Research . 2 (2): 023352. arXiv : 2001.09118 . Bibcode : 2020PhRvR...2b3352F. doi : 10.1103/PhysRevResearch.2.023352 .
9. Барабаси, Альберт-Ласло ; Альберт, Река. (15 октября 1999 г.). «Появление масштабирования в случайных сетях». Наука . 286 (5439): 509–512. arXiv : cond-mat/9910332 . Бибкод : 1999Sci...286..509B. дои : 10.1126/science.286.5439.509. MR  2091634. PMID  10521342. S2CID  524106.
10. Среди семи примеров, изученных Амаралом и др., шесть из них были одномасштабными и только в примере iii сеть киноактера имела режим степенного закона, за которым следовал резкий срез. Ни один из примеров Амарала и др. не подчинялся режиму степенного закона для больших k , т. е. ни один из этих семи примеров не был показан как не зависящий от масштаба. См. особенно начало раздела обсуждения Amaral LAN, Scala A, Barthelemy M, Stanley HE (2000). "Classes of small-world networks". PNAS . 97 (21): 11149–52. arXiv : cond-mat/0001458 . Bibcode :2000PNAS...9711149A. doi : 10.1073/pnas.200327197 . PMC 17168 . PMID  11005838. 
11. Дороговцев, С.; Мендес, Дж.; Самухин, А. (2000). «Структура растущих сетей с предпочтительным связыванием». Physical Review Letters . 85 (21): 4633–4636. arXiv : cond-mat/0004434 . Bibcode : 2000PhRvL..85.4633D. doi : 10.1103/PhysRevLett.85.4633. PMID  11082614. S2CID  118876189.
12. Боллобас, Б .; Риордан, О.; Спенсер, Дж.; Туснади, Г. (2001). «Последовательность степеней случайного графового процесса без масштабирования». Случайные структуры и алгоритмы . 18 (3): 279–290. doi :10.1002/rsa.1009. MR  1824277. S2CID  1486779.
13. Дороговцев, СН; Мендес, Дж. Ф. Ф. (2002). «Эволюция сетей». Успехи физики . 51 (4): 1079–1187. arXiv : cond-mat/0106144 . Bibcode :2002AdPhy..51.1079D. doi :10.1080/00018730110112519. S2CID  429546.
14. Виллингер, Уолтер; Дэвид Олдерсон; Джон К. Дойл (май 2009 г.). «Математика и Интернет: источник огромной путаницы и большого потенциала» (PDF) . Уведомления AMS . 56 (5). Американское математическое общество: 586–599. Архивировано (PDF) из оригинала 15.05.2011 . Получено 03.02.2011 .
15. Ициксон, Клод; Друфф, Жан-Мишель (1989). Статистическая теория поля: Том 1, От броуновского движения к перенормировке и теории решеточной калибровки (1-е изд.). Нью-Йорк: Cambridge University Press. ISBN 978-0-521-34058-8.
16. Ициксон, Клод; Друфф, Жан-Мишель (1989). Статистическая теория поля: Том 2, Сильная связь, методы Монте-Карло, конформная теория поля и случайные системы (1-е изд.). Нью-Йорк: Cambridge University Press. ISBN 978-0-521-37012-7.
17. Meng, Xiangyi; Zhou, Bin (2023). "Безмасштабные сети за пределами степенного распределения степеней". Хаос, солитоны и фракталы . 176 : 114173. arXiv : 2310.08110 . Bibcode : 2023CSF...17614173M. doi : 10.1016/j.chaos.2023.114173. S2CID  263909425.
18. Танака, Рейко (2005). «Масштабные метаболические сети». Phys. Rev. Lett . 94 (16): 168101. Bibcode : 2005PhRvL..94p8101T. doi : 10.1103/PhysRevLett.94.168101. PMID  15904266.
19. Ramezanpour, A.; Karimipour, V.; Mashaghi, A. (2003). "Создание коррелированных сетей из некоррелированных". Phys. Rev. E . 67 (4): 046107. arXiv : cond-mat/0212469 . Bibcode :2003PhRvE..67d6107R. doi :10.1103/PhysRevE.67.046107. PMID  12786436. S2CID  33054818.
20. Де Маси, Джулия и др. (2006). «Модель пригодности для итальянского межбанковского денежного рынка». Physical Review E. 74 ( 6): 066112. arXiv : physics/0610108 . Bibcode : 2006PhRvE..74f6112D. doi : 10.1103/PhysRevE.74.066112. PMID  17280126. S2CID  30814484.
21. Сорамяки, Киммо и др. (2007). «Топология межбанковских платежных потоков». Physica A: Статистическая механика и ее приложения . 379 (1): 317–333. Bibcode :2007PhyA..379..317S. doi :10.1016/j.physa.2006.11.093. hdl : 10419/60649 .
22. Стейверс, Марк; Джошуа Б. Тененбаум (2005). «Крупномасштабная структура семантических сетей: статистический анализ и модель семантического роста». Cognitive Science . 29 (1): 41–78. arXiv : cond-mat/0110012 . doi :10.1207/s15516709cog2901_3. PMID  21702767. S2CID  6000627.
23. Фратини, Микела; Почча, Никола; Риччи, Алессандро; Кампи, Гаэтано; Бургаммер, Манфред; Эппли, Габриэль; Бьянкони, Антонио (2010). «Безмасштабная структурная организация межузельных атомов кислорода в La2CuO4+y». Природа . 466 (7308): 841–4. arXiv : 1008.2015 . Бибкод : 2010Natur.466..841F. дои : 10.1038/nature09260. PMID  20703301. S2CID  4405620.
24. Почча, Никола; Риччи, Алессандро; Кампи, Гаэтано; Фратини, Микела; Пури, Алессандро; Ди Джоаккино, Даниэле; Марчелли, Аугусто; Рейнольдс, Майкл; Бургаммер, Манфред; Сайни, Науранг Л.; Эппли, Габриэль; Бьянкони, Антонио (2012). «Оптимальная неоднородность локальных искажений решетки в La2CuO4+y». ПНАС . 109 (39): 15685–15690. arXiv : 1208.0101 . Бибкод : 2012PNAS..10915685P. дои : 10.1073/pnas.1208492109 . ПМЦ 3465392 . PMID  22961255. 
25. Хассан, МК; Хассан, МЗ; Павел, НИ (2010). «Безмасштабная сетевая топология и мультифрактальность во взвешенной плоской стохастической решетке». New Journal of Physics . 12 (9): 093045. arXiv : 1008.4994 . Bibcode :2010NJPh...12i3045H. doi : 10.1088/1367-2630/12/9/093045 .
26. Хассан, МК; Хассан, МЗ; Павел, НИ (2010). «Безмасштабный беспорядок координационного числа и мультифрактальный беспорядок размера в взвешенной плоской стохастической решетке». J. Phys.: Conf. Ser . 297 : 01.
27. Pachon, Angelica; Sacerdote, Laura; Yang, Shuyi (2018). «Поведение сетей без масштабирования с соприсутствием предпочтительных и однородных правил прикрепления». Physica D: Nonlinear Phenomena . 371 : 1–12. arXiv : 1704.08597 . Bibcode : 2018PhyD..371....1P. doi : 10.1016/j.physd.2018.01.005. S2CID  119320331.
28. Кумар, Рави; Рагхаван, Прабхакар (2000). Стохастические модели для веб-графа (PDF) . Основы компьютерной науки, 41-й ежегодный симпозиум. стр. 57–65. doi :10.1109/SFCS.2000.892065. Архивировано (PDF) из оригинала 2016-03-03 . Получено 2016-02-10 .
29. Барабаси, Альберт-Ласло ; Золтан Н., Олтвай. (2004). «Сетевая биология: понимание функциональной организации клетки». Обзоры природы Генетика . 5 (2): 101–113. дои : 10.1038/nrg1272. PMID  14735121. S2CID  10950726.
30. Dangalchev, Chavdar (июль 2004 г.). "Модели генерации для сетей без масштаба". Physica A: Статистическая механика и ее приложения . 338 (3–4): 659–671. Bibcode :2004PhyA..338..659D. doi :10.1016/j.physa.2004.01.056.
31. Барабаши, А.-Л. и Р. Альберт, Science 286 , 509 (1999).
32. Р. Альберт и А. Л. Барабаси, Phys. Преподобный Летт. 85 , 5234 (2000).
33. С. Н. Дороговцев, Дж. Ф. Мендес и А. Н. Самухим, cond-mat/0011115.
34. PL Krapivsky, S. Redner и F. Leyvraz, Phys. Rev. Lett. 85 , 4629 (2000).
35. Б. Тадич, Physica A 293 , 273 (2001).
36. С. Бомхольдт и Х. Эбель, cond-mat/0008465; Х. А. Симон, Биметрика 42 , 425 (1955).
37. Хассан, МК; Ислам, Лиана; Арефинул Хак, Сайед (2017). «Распределение степеней, распределение рангов и настойчивость лидеров в сетях привязанности, управляемых посредничеством». Physica A. 469 : 23–30. arXiv : 1411.3444 . Bibcode : 2017PhyA..469...23H. doi : 10.1016/j.physa.2016.11.001. S2CID  51976352.
38. Равас, Э.; Барабаши (2003). «Иерархическая организация в сложных сетях». Физ. Преподобный Е. 67 (2): 026112. arXiv : cond-mat/0206130 . Бибкод : 2003PhRvE..67b6112R. doi : 10.1103/physreve.67.026112. PMID  12636753. S2CID  17777155.
39. Caldarelli, G.; et al. (2002). "Безмасштабные сети с переменной внутренней пригодностью вершин" (PDF) . Phys. Rev. Lett . 89 (25): 258702. Bibcode :2002PhRvL..89y8702C. doi :10.1103/physrevlett.89.258702. PMID  12484927.
40. Гарлашелли, Д.; и др. (2004). "Зависящие от приспособленности топологические свойства Всемирной торговой сети". Phys. Rev. Lett . 93 (18): 188701. arXiv : cond-mat/0403051 . Bibcode : 2004PhRvL..93r8701G. doi : 10.1103/physrevlett.93.188701. PMID  15525215. S2CID  16367275.
41. Крюков, Дмитрий; Пападопулос, Фрагкискос; Кицак, Максим; Вахдат, Амин; Богунья, Мариан (2010). «Гиперболическая геометрия сложных сетей». Физический обзор E . 82 (3): 036106. arXiv : 1006.5169 . Бибкод : 2010PhRvE..82c6106K. doi : 10.1103/PhysRevE.82.036106. PMID  21230138. S2CID  6451908.
42. А. Эрнандо; Д. Виллуэндас; К. Весперинас; М. Абад; А. Пластино (2009). «Раскрытие распределения размеров социальных групп с помощью теории информации в сложных сетях». arXiv : 0905.3704 [physics.soc-ph]., представлено в European Physical Journal B
43. Андре А. Морейра; Деметриус Р. Паула; Раймундо Н. Коста Фильо; Хосе С. Андраде-младший (2006). «Конкурентоспособный рост кластеров в сложных сетях». Физический обзор E . 73 (6): 065101. arXiv : cond-mat/0603272 . Бибкод : 2006PhRvE..73f5101M. doi : 10.1103/PhysRevE.73.065101. PMID  16906890. S2CID  45651735.
44. Хейдари, Х.; Тахери, СМ; Кавех, К. (2018). «Распределенный максимальный независимый набор в сетях без масштабирования». arXiv : 1804.02513 [cs.DC].
45. Eom, Young-Ho; Jo, Hang-Hyun (2015-05-11). "Tail-scope: использование друзей для оценки тяжелых хвостов распределений степеней в крупномасштабных сложных сетях". Scientific Reports . 5 (1): 9752. arXiv : 1411.6871 . Bibcode :2015NatSR...5E9752E. doi : 10.1038/srep09752 . ISSN  2045-2322. PMC 4426729 . PMID  25959097. 
46. Nettasinghe, Buddhika; Krishnamurthy, Vikram (2021-05-19). «Оценка максимального правдоподобия распределений степенного закона с помощью выборки на основе парадокса дружбы». ACM Transactions on Knowledge Discovery from Data . 15 (6): 1–28. arXiv : 1908.00310 . doi : 10.1145/3451166 . ISSN  1556-4681.

Дальнейшее чтение

• Альберт Р.; Барабаши А.-Л. (2002). "Статистическая механика сложных сетей". Rev. Mod. Phys . 74 (1): 47–97. arXiv : cond-mat/0106096 . Bibcode :2002RvMP...74...47A. 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) . Научный американец . 288 (5): 50–9. Бибкод : 2003SciAm.288e..60B. doi : 10.1038/scientificamerican0503-60. ПМИД  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.; Muñoz MA (2002). "Безмасштабные сети с различной внутренней пригодностью вершин". Physical Review Letters . 89 (25): 258702. arXiv : cond-mat/0207366 . Bibcode : 2002PhRvL..89y8702C. doi : 10.1103/PhysRevLett.89.258702. PMID  12484927.
• Дангалчев, Ч. (2004). «Модели генерации для безмасштабных сетей». Physica A. 338 ( 3–4): 659–671. Bibcode : 2004PhyA..338..659D. doi : 10.1016/j.physa.2004.01.056.
• Дороговцев, СН; Мендес, ДЖФФ; Самухин, АН (2000). «Структура растущих сетей: точное решение модели Барабаши—Альберта». Phys. Rev. Lett . 85 (21): 4633–6. arXiv : cond-mat/0004434 . Bibcode :2000PhRvL..85.4633D. doi :10.1103/PhysRevLett.85.4633. PMID  11082614. S2CID  118876189.
• Дороговцев, СН; Мендес, Дж. Ф. Ф. (2003). Эволюция сетей: от биологических сетей до Интернета и WWW . Oxford University Press. ISBN 0-19-851590-1.
• Дороговцев, СН; Гольцев АВ; Мендес, Дж. Ф. Ф. (2008). «Критические явления в сложных сетях». Rev. Mod. Phys . 80 (4): 1275–1335. arXiv : 0705.0010 . Bibcode :2008RvMP...80.1275D. doi :10.1103/RevModPhys.80.1275. S2CID  3174463.
• Дороговцев, СН; Мендес, Дж. Ф. Ф. (2002). «Эволюция сетей». Успехи физики . 51 (4): 1079–1187. arXiv : cond-mat/0106144 . Bibcode :2002AdPhy..51.1079D. doi :10.1080/00018730110112519. S2CID  429546.
• Эрдёш, П.; Реньи , А. (1960). Об эволюции случайных графов (PDF) . Том 5. Издание Математического института Венгерской академии наук. С. 17–61.
• Фалуцос, М.; Фалуцос, П.; Фалуцос, К. (1999). «О степенных отношениях топологии интернета». Comp. Comm. Rev. 29 ( 4): 251–262. doi :10.1145/316194.316229.
• Ли, Л.; Олдерсон, Д.; Танака, Р.; Дойл, Дж. К.; Виллингер, В. (2005). «К теории безмасштабных графов: определение, свойства и следствия (расширенная версия)». arXiv : cond-mat/0501169 .
• Кумар, Р.; Рагхаван, П.; Раджагопалан, С.; Сивакумар, Д.; Томкинс, А.; Упфал, Э. (2000). «Стохастические модели для веб-графа» (PDF) . Труды 41-го ежегодного симпозиума по основам компьютерной науки (FOCS) . Редондо-Бич, Калифорния: IEEE CS Press. стр. 57–65.
• Матлис, Ян (4 ноября 2002 г.). «Сети без масштабирования».
• Newman, Mark EJ (2003). «Структура и функции сложных сетей». SIAM Review . 45 (2): 167–256. arXiv : cond-mat/0303516 . Bibcode : 2003SIAMR..45..167N. doi : 10.1137/S003614450342480. S2CID  221278130.
• Пастор-Саторрас, Р.; Веспиньяни, А. (2004). Эволюция и структура Интернета: статистический физический подход . Cambridge University Press. ISBN 0-521-82698-5.
• Pennock, DM; Flake, GW; Lawrence, S.; Glover, EJ; Giles, CL (2002). «Победители не забирают все: характеристика конкуренции за ссылки в Интернете». PNAS . 99 (8): 5207–11. Bibcode :2002PNAS...99.5207P. doi : 10.1073/pnas.032085699 . PMC  122747 . PMID  16578867.
• Робб, Джон. Масштабируемые сети и терроризм, 2004.
• Келлер, ЭФ (2005). «Возвращаясь к сетям «без масштаба». BioEssays . 27 (10): 1060–8. doi :10.1002/bies.20294. PMID  16163729. Архивировано из оригинала 13.08.2011.
• Оноди, Р. Н.; де Кастро, П. А. (2004). «Комплексное сетевое исследование бразильского футболиста». Phys. Rev. E. 70 ( 3): 037103. arXiv : cond-mat/0409609 . Bibcode : 2004PhRvE..70c7103O. doi : 10.1103/PhysRevE.70.037103. PMID  15524675. S2CID  31653489.
• Кастуриратна, Д.; Пиравинан, М. (2015). «Комплексное сетевое исследование бразильского футболиста». Sci. Rep . In Press.