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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

Обзор

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

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

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

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

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

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

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

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

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

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

Иммунизация

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Функции

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

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

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

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

Примеры

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

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

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

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

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

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

$\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, в которой первый и второй соседние узлы в равной степени способствуют привлекательности целевого узла, демонстрирует появление переходных безмасштабных сетей. В модели k2 распределение степеней выглядит приблизительно безмасштабным, пока сеть относительно мала, но значительные отклонения от безмасштабного режима возникают по мере увеличения сети. Это приводит к тому, что относительная привлекательность узлов разной степени меняется со временем, что также наблюдается в реальных сетях.

Модель прикрепления на основе медиации (MDA)

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

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

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

Однако для $m=1$ он описывает механизм «победитель получает все», поскольку мы обнаруживаем, что почти $99\%$ из всех узлов имеет степень один, а один — сверхбогатый по степени. Как $m$ стоимость увеличивается, неравенство между сверхбогатыми и бедными уменьшается, и по мере того, как $m>14$ мы обнаруживаем переход от механизма «богатые становятся супербогаче» к механизму «богатые становятся еще богаче».

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

См. Также: Нелинейное преимущественное прикрепление.

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

При нелинейной преимущественной привязанности форма $\Pi (k)$ не является линейным, и недавние исследования показали, что распределение степеней сильно зависит от формы функции $\Pi (k)$

Krapivsky, Redner, and Leyvraz продемонстрировать, что безмасштабная природа сети разрушается из-за нелинейного предпочтительного присоединения. Единственный случай, когда топология сети немасштабна, — это случай, когда предпочтительное присоединение асимптотически линейно, т.е. $\Pi (k_{i})\sim a_{\infty }k_{i}$ как $k_{i}\to \infty$. В этом случае уравнение скорости приводит к

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

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

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

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

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

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

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

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

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

Основная статья: Гиперболический геометрический граф

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

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

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

Модель единых льготных вложений (модель UPA)

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

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

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

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

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

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

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

См. также

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

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

• Альберт Р.; Барабаши А.-Л. (2002). «Статистическая механика сложных сетей» . Преподобный Мод. Физ . 74 (1): 47–97. arXiv : cond-mat/0106096 . Бибкод : 2002РвМП...74...47А . дои : 10.1103/RevModPhys.74.47 . S2CID   60545 .
• Амарал ЛАН, Скала А, Бартелеми М, Стэнли Х.Э. (2000). «Классы сетей маленького мира» . ПНАС . 97 (21): 11149–52. arXiv : cond-mat/0001458 . Бибкод : 2000PNAS...9711149A . дои : 10.1073/pnas.200327197 . ПМК   17168 . ПМИД   11005838 .
• Барабаши, Альберт-Ласло (2004). Связано: как все связано со всем остальным . Персей Паб. ISBN  0-452-28439-2 .
• Барабаши, Альберт-Ласло; Бонабо, Эрик (май 2003 г.). «Безмасштабные сети» (PDF) . Научный американец . 288 (5): 50–9. Бибкод : 2003SciAm.288e..60B . doi : 10.1038/scientificamerican0503-60 . ПМИД   12701331 .
• Дэн Браха; Янир Бар-Ям (2004). «Топология крупномасштабных сетей решения инженерных задач» (PDF) . Физ. Преподобный Е. 69 (1): 016113. Бибкод : 2004PhRvE..69a6113B . дои : 10.1103/PhysRevE.69.016113 . ПМИД   14995673 . S2CID   1001176 .
• Калдарелли Г. « Безмасштабные сети» Oxford University Press, Оксфорд (2007).
• Кальдарелли Г.; Капоччи А.; Де Лос Риос П.; Муньос М.А. (2002). «Безмасштабные сети с различной внутренней пригодностью вершин». Письма о физических отзывах . 89 (25): 258702. arXiv : cond-mat/0207366 . Бибкод : 2002PhRvL..89y8702C . doi : 10.1103/PhysRevLett.89.258702 . ПМИД   12484927 .
• Дангалчев, Ч. (2004). «Модели генерации безмасштабных сетей» . Физика А. 338 (3–4): 659–671. Бибкод : 2004PhyA..338..659D . дои : 10.1016/j.physa.2004.01.056 .
• Дороговцев С.Н.; Мендес, JFF; Самухин, АН (2000). «Структура растущих сетей: точное решение модели Барабаши-Альберта». Физ. Преподобный Летт . 85 (21): 4633–6. arXiv : cond-mat/0004434 . Бибкод : 2000PhRvL..85.4633D . doi : 10.1103/PhysRevLett.85.4633 . ПМИД   11082614 . S2CID   118876189 .
• Дороговцев С.Н.; Мендес, JFF (2003). Эволюция сетей: от биологических сетей к Интернету и WWW . Издательство Оксфордского университета. ISBN  0-19-851590-1 .
• Дороговцев С.Н.; Гольцев А.В.; Мендес, JFF (2008). «Критические явления в сложных сетях». Преподобный Мод. Физ . 80 (4): 1275–1335. arXiv : 0705.0010 . Бибкод : 2008РвМП...80.1275Д . дои : 10.1103/RevModPhys.80.1275 . S2CID   3174463 .
• Дороговцев С.Н.; Мендес, JFF (2002). «Эволюция сетей». Достижения физики . 51 (4): 1079–1187. arXiv : cond-mat/0106144 . Бибкод : 2002AdPhy..51.1079D . дои : 10.1080/00018730110112519 . S2CID   429546 .
• Эрдеш, П .; Реньи, А. (1960). Об эволюции случайных графов (PDF) . Том. 5. Издание Математического института Венгерской академии наук. стр. 17–61.
• Фалуцсос, М.; Фалуцсос, П.; Фалуцсос, К. (1999). «О степенных отношениях топологии Интернета». Комп. Комм. Преподобный . 29 (4): 251–262. дои : 10.1145/316194.316229 .
• Ли, Л.; Олдерсон, Д.; Танака, Р.; Дойл, Дж. К.; Виллинджер, В. (2005). «К теории безмасштабных графов: определение, свойства и последствия (расширенная версия)». arXiv : cond-mat/0501169 .
• Кумар, Р.; Рагхаван, П.; Раджагопалан, С.; Сивакумар, Д.; Томкинс, А.; Упфал, Э. (2000). «Стохастические модели веб-графа» (PDF) . Материалы 41-го ежегодного симпозиума по основам информатики (FOCS) . Редондо-Бич, Калифорния: IEEE CS Press. стр. 57–65.
• Матлис, Январь (4 ноября 2002 г.). «Безмасштабные сети» .
• Ньюман, Марк Э.Дж. (2003). «Структура и функции сложных сетей». Обзор СИАМ . 45 (2): 167–256. arXiv : cond-mat/0303516 . Бибкод : 2003SIAMR..45..167N . дои : 10.1137/S003614450342480 . S2CID   221278130 .
• Пастор-Саторрас Р.; Веспиньяни, А. (2004). Эволюция и структура Интернета: подход статистической физики . Издательство Кембриджского университета. ISBN  0-521-82698-5 .
• Пеннок, DM; Флейк, Г.В.; Лоуренс, С.; Гловер, Э.Дж.; Джайлз, CL (2002). «Победители не получают все: характеристика конкуренции за ссылки в сети» . ПНАС . 99 (8): 5207–11. Бибкод : 2002PNAS...99.5207P . дои : 10.1073/pnas.032085699 . ПМЦ   122747 . ПМИД   16578867 .
• Робб, Джон. Безмасштабные сети и терроризм , 2004.
• Келлер, Э.Ф. (2005). «Возвращаясь к «безмасштабным» сетям» . Биоэссе . 27 (10): 1060–8. doi : 10.1002/bies.20294 . ПМИД   16163729 . Архивировано из оригинала 13 августа 2011 г.
• Оноди, Р.Н.; де Кастро, Пенсильвания (2004). «Комплексное сетевое исследование бразильского футболиста». Физ. Преподобный Е. 70 (3): 037103. arXiv : cond-mat/0409609 . Бибкод : 2004PhRvE..70c7103O . дои : 10.1103/PhysRevE.70.037103 . ПМИД   15524675 . S2CID   31653489 .
• Кастуриратна, Д.; Пиравенан, М. (2015). «Комплексное сетевое исследование бразильского футболиста». наук. Представитель . В Прессе.