Сеть без масштабирования

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

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

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

где γ {\ displaystyle \ gamma}\gamma - параметр, значение которого обычно находится в диапазоне 2 <γ {\ displaystyle \ gamma}\gamma < 3 (wherein the second moment (параметр масштаба ) k - γ {\ displaystyle k ^ {\ boldsymbol {- \ gamma}}}{\displaystyle k^{\boldsymbol {-\gamma }}}бесконечно, но первый момент конечен), хотя иногда он может выходить за эти границы.

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

Содержание

  • 1 История
  • 2 Обзор
  • 3 Характеристики
    • 3.1 Перколяция
    • 3.2 Кластеризация
    • 3.3 Расстояние в сетях без масштаба
    • 3.4 Фрактальные сети без масштаба
    • 3.5 Иммунизация
  • 4 Примеры
  • 5 Генеративные модели
  • 6 Обобщенная безмасштабная модель
    • 6.1 Характеристики
    • 6.2 Примеры
      • 6.2.1 Модель Барабаши – Альберта
      • 6.2.2 Два- модель сети уровня
      • 6.2.3 Модель подключения, управляемого посредником (MDA)
      • 6.2.4 Нелинейное предпочтительное подключение
      • 6.2.5 Иерархическая сетевая модель
      • 6.2.6 Фитнес-модель
      • 6.2. 7 Гиперболические геометрические графы
      • 6.2.8 Двойное преобразование ребер для создания графов без масштабирования с желаемыми свойствами
      • 6.2.9 Модель Uniform-Preferential-Attachment (модель UPA)
  • 7 Безмасштабные идеальные сети
  • 8 Характеристики романа
  • 9 См. Также
  • 10 Ссылки
  • 11 Дополнительная литература

История

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

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

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

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

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

s (G) = ∑ (u, v) ∈ E deg ⁡ (u) ⋅ deg ⁡ (v). {\ displaystyle s (G) = \ sum _ {(u, v) \ in E} \ deg (u) \ cdot \ deg (v).}s(G) = \sum_{(u,v) \in E} \deg(u) \cdot \deg(v).

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

S (G) = s (G) s max, {\ displaystyle S (G) = {\ frac {s (G)} {s _ {\ max}}},}S(G)={\frac {s(G)}{s_{\max }}},

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

Обзор

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

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

Случайная сеть (a) и безмасштабная сеть (b). В безмасштабной сети выделены более крупные концентраторы. Сложное распределение степени сети случайных и безмасштабных

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

Перколяция

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

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

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

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

Расстояние в сетях без масштаба

Еще одна характеристика касается среднего расстояния между двумя вершинами в сети. Как и в большинстве неупорядоченных сетей, таких как модель сети малого мира, это расстояние очень мало по сравнению с высокоупорядоченной сетью, такой как решетчатый граф. Примечательно, что некоррелированный степенной граф, имеющий 2 < γ < 3 will have ultrasmall diameter d ~ ln ln N where N is the number of nodes in the network, as proved by Cohen and Havlin. Thus, the diameter of a growing scale-free network might be considered almost constant in practice.

сетей без фрактального масштаба

Розенфельд и др. Предложили метод создания детерминированных сетей без фрактального масштаба

Иммунизация

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

Произошел всплеск активности в области моделирования безмасштабных сложных сетей. Рецепту Барабаши и Альберта последовали несколько вариаций и обобщений, а также переработка предыдущих математических работ. Пока в модели существует степенное распределение , это безмасштабная сеть, а модель этой сети - безмасштабная модель.

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

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

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

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

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

Примеры

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

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

Например, первая безмасштабная модель, модель Барабаши – Альберта, имеет предпочтительную линейную привязку Π (ки) = ки ∑ jkj {\ displaystyle \ Pi (k_ {i}) = {\ frac {k_ {i}} {\ sum _ {j} k_ {j}}}}\Pi(k_i)=\frac{k_i}{\sum_j k_j}и добавляет по одному новому узлу на каждом временном шаге.

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

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

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

Π (ки) знак равно ки + С ∑ (я, j) ​​kj ∑ jkj + C ∑ jkj 2, {\ displaystyle \ Pi (k_ {i}) = {\ frac {k_ {i} + C \ sum _ {(i, j)} k_ {j}} {\ sum _ {j} k_ {j} + C \ sum _ {j} k_ {j} ^ {2}}},}{\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.

Модель подключения, управляемого посредником (MDA)

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

Π (i) = ki N ∑ j = 1 ki 1 kjki. {\ displaystyle \ Pi (i) = {\ frac {k_ {i}} {N}} {\ frac {\ sum _ {j = 1} ^ {k_ {i}} {\ frac {1} {k_ { j}}}} {k_ {i}}}.}{\displaystyle \Pi (i)={\frac {k_{i}}{N}}{\frac {\sum _{j=1}^{k_{i}}{\frac {1}{k_{j}}}}{k_{i}}}.}

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

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

Нелинейная предпочтительная привязанность

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

Крапивский, Реднер и Лейвраз демонстрируют, что безмасштабный характер сети разрушается из-за нелинейного предпочтительного присоединения. Единственный случай, когда топология сети не масштабируется, - это тот случай, когда предпочтительное присоединение асимптотически линейно, то есть Π (ki) ∼ a ∞ ki {\ displaystyle \ Pi (k_ { i}) \ sim a _ {\ infty} k_ {i}}\Pi(k_i) \sim a_\infty k_ias ki → ∞ {\ displaystyle k_ {i} \ to \ infty}k_i \to \infty. В этом случае уравнение скорости приводит к

P (k) ∼ k - γ с γ = 1 + μ a ∞. {\ displaystyle P (k) \ sim k ^ {- \ gamma} {\ text {with}} \ gamma = 1 + {\ frac {\ mu} {a _ {\ infty}}}.}{\displaystyle P(k)\sim k^{-\gamma }{\text{ with }}\gamma =1+{\frac {\mu }{a_{\infty }}}.}

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

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

Существует еще один вид безмасштабной модели, которая растет согласно к некоторым шаблонам, таким как иерархическая сетевая модель.

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

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

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

p (x i, x j) = δ x i x j 1 + δ x i x j. {\ displaystyle p (x_ {i}, x_ {j}) = {\ frac {\ delta x_ {i} x_ {j}} {1+ \ delta x_ {i} x_ {j}}}.}{\displaystyle p(x_{i},x_{j})={\frac {\delta x_{i}x_{j}}{1+\delta x_{i}x_{j}}}.}

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

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

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

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

Uniform-Preferential-Attachment model (UPA model)

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

Безмасштабные идеальные сети

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

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

Для немасштабируемой сети с n {\ displaystyle n}nузлами и показателем степени β>3 {\ displaystyle \ beta>3}{\displaystyle \beta>3} , индуцированный подграф, построенный из вершин со степенью больше log ⁡ n × log ∗ ⁡ n {\ displaystyle \ log {n} \ times \ log ^ {*} {n}}{\displaystyle \log {n}\times \log ^{*}{n}}- это сеть без масштабирования с β ′ = 2 {\ displaystyle \ beta '= 2}{\displaystyle \beta '=2}, почти наверняка (as).

См. Также

Ссылки

Дополнительная литература

Последняя правка сделана 2021-06-07 04:29:39
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте