Введение

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

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

где γ – параметр, значение которого обычно находится в диапазоне (2 < γ < 3) (при этом второй момент (масштабный параметр) распределения бесконечен, но первый момент конечен), хотя иногда он может выходить за эти пределы. Название "безмасштабная" можно объяснить тем, что некоторые моменты распределения степеней не определены, и, следовательно, сеть не имеет характерного масштаба или "размера". О многих сетях сообщалось как о безмасштабных, однако статистический анализ опроверг многие из этих утверждений и серьезно поставил под сомнение другие. Кроме того, некоторые утверждают, что знание о том, что распределение степеней имеет "тяжелый хвост", важнее, чем определение того, является ли сеть безмасштабной в соответствии со строгими статистическими определениями. Механизмы предпочтительного присоединения и модель пригодности были предложены для объяснения предполагаемых степенных распределений степеней в реальных сетях. Альтернативные модели, такие как суперлинейное предпочтительное присоединение и присоединение по второму соседу, могут создавать временные безмасштабные сети, но распределение степеней отклоняется от степенного закона по мере роста сети.

История

В исследованиях сетей цитирования между научными работами Дерек де Солла Прайс показал в 1965 году, что количество ссылок на статьи, то есть количество цитирований, которые они получают, имеет распределение с тяжелым хвостом, соответствующее распределению Парето или степенному закону, и, следовательно, сеть цитирования является безмасштабной. Однако он не использовал термин «безмасштабная сеть», который был введен в употребление лишь несколько десятилетий спустя. В более поздней статье 1976 года Прайс также предложил механизм для объяснения возникновения степенных законов в сетях цитирования, который он назвал «кумулятивным преимуществом», но который сегодня чаще известен как преференциальное присоединение. Возросший интерес к безмасштабным сетям начался в 1999 году с работы Альберта-Ласло Барабаши и Реки Альберт в Университете Нотр-Дам, которые отобразили топологию части Всемирной паутины и обнаружили, что некоторые узлы, которые они назвали «хабами», имеют гораздо больше связей, чем другие, и что сеть в целом имеет степенное распределение числа связей, приходящихся на узел. После того, как было установлено, что некоторые другие сети, включая социальные и биологические сети, также имеют распределения степеней с тяжелым хвостом, Барабаши и Река Альберт ввели термин «безмасштабная сеть» для описания класса сетей, демонстрирующих степенное распределение степеней. Однако, изучив семь примеров сетей в социальных, экономических, технологических, биологических и физических системах, Амаралу и др. не смогли обнаружить безмасштабную сеть среди этих семи примеров. Только один из этих примеров, сеть актеров кино, демонстрировал распределение степеней P(k), соответствующее степенному режиму для умеренных значений k, хотя в конечном итоге за этим режимом следовал резкий обрыв, показывающий экспоненциальный спад для больших значений k. Барабаши и Река Альберт предложили генеративный механизм для объяснения появления степенных распределений, который они назвали «преференциальным присоединением», и который по сути совпадает с механизмом, предложенным Прайсом. Аналитические решения для этого механизма (также аналогичные решению Прайса) были представлены в 2000 году Дороговцевым, Мендесом и Самухиным и независимо от них Крапивским, Реднером и Лейвразом, а позже строго доказаны математиком Белой Боллобасом. Однако этот механизм производит лишь определенное подмножество сетей в безмасштабном классе, и с тех пор было обнаружено множество альтернативных механизмов. История безмасштабных сетей также включает в себя некоторые разногласия. На эмпирическом уровне безмасштабный характер нескольких сетей был поставлен под сомнение. Например, братья Фалуцос считали, что Интернет имеет степенное распределение степеней на основе данных трассировки; однако было предположено, что это иллюзия третьего уровня, созданная маршрутизаторами, которые выглядят как узлы высокой степени, скрывая внутреннюю структуру второго уровня AS, которые они соединяют. На теоретическом уровне были предложены уточнения абстрактного определения безмасштабности. Например, Ли и др. (2005) предложили потенциально более точную «безмасштабную метрику». Кратко, пусть G — граф с набором ребер E, и пусть степень вершины (то есть количество ребер, инцидентных вершине) обозначается как Define. Эта величина максимизируется, когда узлы высокой степени соединены с другими узлами высокой степени. Теперь определим, где smax — максимальное значение s(H) для H из множества всех графов с распределением степеней, идентичным распределению G. Это дает метрику в диапазоне от 0 до 1, где граф G с малым S(G) является «богатым масштабом», а граф G с S(G), близким к 1, является «безмасштабным». Это определение отражает понятие самоподобия, подразумеваемое в названии «безмасштабная сеть».

Обзор

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

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

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

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

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

Иммунизация

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

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

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

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

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

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

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

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

Для сети, свободной от масштаба, с *n* узлами и показателем степенного закона γ, индуцированный подграф, построенный на вершинах со степенями, превышающими *k*, является сетью, свободной от масштаба, с показателем γ, почти наверное.

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

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