Войти
Пример сети в маленьком мире. Концентраторы больше других узлов. Среднее градуса = 3,833. Средняя длина кратчайшего пути = 1,803.. Коэффициент кластеризации = 0,522 
Случайный график. Среднее градус = 2,833. Средняя длина кратчайшего пути = 2,109.. Коэффициент кластеризации = 0,167 A сеть малого мира - это тип математический граф, в котором большинство узлов не являются соседями друг друга, но соседи любого данного узла, вероятно, будут соседями друг друга, и к большинству узлов можно добраться из любого другого узла за небольшое количество переходов или шагов. В частности, сеть малого мира определяется как сеть, в которой типичное расстояние L между двумя случайно выбранными узлами (количество требуемых шагов) растет пропорционально логарифму количества узлов N в сети., то есть:
, а коэффициент кластеризации не мал. В контексте социальной сети это приводит к феномену маленького мира, когда незнакомцы связываются короткой цепочкой знакомых. Многие эмпирические графики показывают эффект маленького мира, включая социальные сети, вики-сайты, такие как Википедия, генные сети и даже базовую архитектуру Интернета. Это источник вдохновения для многих архитектур сети на кристалле в современном компьютерном оборудовании.
Определенная категория сетей малого мира была идентифицирована как класс случайных графов Авторы Дункан Уоттс и Стивен Строгац в 1998 году. Они отметили, что графы можно классифицировать по двум независимым структурным характеристикам, а именно по коэффициенту кластеризации и среднему узлу- расстояние до узла (также известное как средняя длина кратчайшего пути ). Чисто случайные графы, построенные в соответствии с моделью Эрдеша – Реньи (ER), демонстрируют небольшую среднюю длину кратчайшего пути (обычно варьирующуюся как логарифм числа узлов) вместе с небольшим коэффициентом кластеризации. Уоттс и Строгац измерили, что на самом деле многие реальные сети имеют небольшую среднюю длину кратчайшего пути, но также и коэффициент кластеризации, значительно превышающий ожидаемый случайным образом. Затем Уоттс и Строгац предложили новую графическую модель, в настоящее время называемую моделью Уоттса и Строгаца, с (i) небольшой средней длиной кратчайшего пути и (ii) большим коэффициентом кластеризации. Кроссовер в модели Уоттса – Строгаца между «большим миром» (таким как решетка) и маленьким миром был впервые описан Бартелеми и Амаралом в 1999 году. За этой работой последовало множество исследований, включая точные результаты (Barrat and Weigt, 1999; Дороговцев и Мендес ; Бармпутис и Мюррей, 2010). Браунштейн и др. Обнаружили, что для взвешенных сетей ER, где веса имеют очень широкое распределение, оптимальные масштабы пути становятся значительно длиннее и масштабируются как N.
Сети малых миров, как правило, содержат клики и почти- клики, то есть подсети, которые имеют связи между почти любыми двумя узлами внутри них. Это следует из определяющего свойства высокого коэффициента кластеризации. Во-вторых, большинство пар узлов будут связаны хотя бы одним коротким путем. Это следует из определяющего свойства, что средняя длина кратчайшего пути мала. Некоторые другие свойства часто ассоциируются с сетями малого мира. Обычно концентраторов слишком много - узлов в сети с большим количеством подключений (известных как узлы с высокой степенью ). Эти концентраторы служат в качестве общих соединений, обеспечивающих короткие пути между другими краями. По аналогии, небольшая сеть рейсов авиакомпаний имеет небольшую среднюю протяженность пути (то есть между любыми двумя городами вам, вероятно, придется совершить три или меньше рейсов), потому что многие рейсы проходят через хабы города.. Это свойство часто анализируется, рассматривая долю узлов в сети, которые имеют определенное количество подключений, входящих в них (степень распределения сети). Сети с большим, чем ожидалось, числом концентраторов будут иметь большую долю узлов с высокой степенью, и, следовательно, распределение степеней будет обогащено при высоких значениях степени. В просторечии это известно как распределение с толстым хвостом. Графы с очень разной топологией квалифицируются как сети малого мира, если они удовлетворяют двум указанным выше требованиям к определению.
Компактность сети была определена количественно малым коэффициентом 
(
и 
), сеть - это маленький мир. Однако известно, что этот показатель плохо работает, потому что он слишком зависит от размера сети.Другой метод для количественной оценки сети малого мира использует исходное определение сети малого мира, сравнивая кластеризацию данной сети с эквивалентной сетью решетки и длину ее пути в эквивалентную случайную сеть. Мера малого мира (
Если характерная длина пути L и коэффициент кластеризации C рассчитываются на основе тестируемой сети, C ℓ - коэффициент кластеризации для эквивалентной решетчатой сети, а L r - характерная длина пути для эквивалентной случайной сети.
Еще один метод количественной оценки «малости» нормализует как кластеризацию сети, так и длину пути относительно этих характеристик в эквивалентной решетке и случайных сетях. Индекс малого мира (SWI) определяется как
Оба значения ω 'и SWI находятся в диапазоне от 0 до 1, и было показано, что они отражают аспекты ограниченности мира. Однако они принимают несколько иные концепции идеального тесного мира. Для данного набора ограничений (например, размера, плотности, распределения степеней) существует сеть, для которой ω ′ = 1, и, таким образом, ω стремится уловить степень, в которой сеть с данными ограничениями настолько мала, насколько это возможно. Напротив, сеть, для которой SWI = 1, может не существовать, поэтому SWI стремится определить степень приближения сети с заданными ограничениями к теоретическому идеалу малого мира сети, где C ≈ C ℓ и L ≈ L r.
R. Коэн и Хэвлин аналитически показали, что сети без масштабирования - это сверхмалые миры. В этом случае из-за концентраторов кратчайшие пути становятся значительно меньше и масштабируются как
Свойства маленького мира обнаруживаются во многих явлениях реального мира, включая веб-сайты с меню навигации, пищевые сети, электросети, сети обработки метаболитов, сети нейронов мозга, сети избирателей, телефонный звонок графики, сети аэропортов и социальные сети влияния. Культурные сети, семантические сети и словесные сети совместной встречаемости также оказались сетями небольшого мира.
Сети из связанных белков обладают свойствами небольшого мира, такими как степенное распределение, подчиняющееся распределению степеней. Точно так же транскрипционные сети, в которых узлами являются гены, и они связаны, если один ген оказывает повышающее или понижающее генетическое влияние на другой, обладают свойствами малых мировых сетей. 49>
В другом примере известная теория «шести степеней разделения » между людьми неявно предполагает, что область дискурс - это совокупность людей, живущих в любой момент времени. Число степеней разделения между Альбертом Эйнштейном и Александром Великим почти наверняка больше 30, и эта сеть не имеет свойств маленького мира. Аналогичным образом ограниченная сеть была бы сетью «ходил в школу с»: если два человека учились в одном колледже с разницей в десять лет друг от друга, маловероятно, что у них есть общие знакомые среди студентов.
Точно так же количество ретрансляционных станций, через которые должно пройти сообщение, не всегда было небольшим. В те дни, когда почту возили в руке или верхом, количество раз, когда письмо переходило из рук в руки от источника к месту назначения, было бы намного больше, чем сегодня. Количество раз, когда сообщение переходило из рук в руки во времена визуального телеграфа (около 1800–1850), определялось требованием, чтобы две станции были соединены прямой видимостью.
Молчаливые предположения, если их не исследовать, могут вызвать искажение в литературе по графикам в пользу поиска сетей малого мира (пример эффекта файлового ящика, возникающего из-за предвзятости публикации ).
Некоторые исследователи, такие как Барабаши, выдвинули гипотезу о том, что преобладание малых мировых сетей в биологических системах может отражать эволюционное преимущество такой архитектуры.. Одна из возможностей состоит в том, что сети малого мира более устойчивы к возмущениям, чем другие сетевые архитектуры. Если бы это было так, это дало бы преимущество биологическим системам, которые могут быть повреждены мутацией или вирусной инфекцией.
в небольшой мировой сети со степенью распределения, следующей за степенной закон, удаление случайного узла редко вызывает резкое увеличение длины (или резкое снижение коэффициента кластеризации ). Это следует из того факта, что наиболее короткие пути между узлами проходят через концентраторы, и если периферийный узел удален, он вряд ли будет мешать прохождению между другими периферийными узлами. Поскольку доля периферийных узлов в небольшой мировой сети намного выше, чем доля концентраторов, вероятность удаления важного узла очень мала. Например, если небольшой аэропорт в Сан-Вэлли, штат Айдахо был закрыт, это не увеличило бы среднее количество рейсов, которые другим пассажирам, путешествующим в США, пришлось бы предпринять, чтобы прибыть в свои пункты назначения. Однако, если случайное удаление узла случайно попадает в концентратор, средняя длина пути может резко увеличиться. Это можно наблюдать ежегодно, когда северные узловые аэропорты, такие как аэропорт О'Хара в Чикаго, закрываются из-за снегопада; многим людям приходится брать дополнительные рейсы.
Напротив, в случайной сети, в которой все узлы имеют примерно одинаковое количество подключений, удаление случайного узла может немного, но значительно увеличить длину среднего кратчайшего пути почти для любого удаленного узла. В этом смысле случайные сети уязвимы для случайных возмущений, в то время как сети малых миров надежны. Однако небольшие сети уязвимы для целенаправленной атаки концентраторов, тогда как случайные сети не могут быть нацелены на катастрофический отказ.
Соответственно, вирусы эволюционировали, чтобы вмешиваться в активность белков-концентраторов, таких как p53, тем самым вызывая массивные изменения клеточного поведения, которые способствуют репликации вируса. Полезным методом анализа устойчивости сети является теория перколяции.
Основным механизмом построения сетей малого мира является механизм Уоттса – Строгаца.
Сети малого мира также могут быть введены с задержкой по времени, которая будет не только создавать фракталы, но и создавать хаос при определенных условиях или переходить к хаосу в динамических сетях.
График степени – диаметра строится таким образом, что количество соседей, которые имеет каждая вершина в сети, ограничено, в то время как расстояние от любой данной вершины сети до любой другой вершины (диаметр сети) минимизировано. Построение таких сетей малого мира выполняется как часть усилий по поиску графов порядка, близких к границе Мура.
Другой способ построения сети малых миров с нуля описан в Barmpoutis et al., Где сеть с очень малым средним расстоянием и очень большим средним кластеризацией. Дан быстрый алгоритм постоянной сложности, а также измерения устойчивости результирующих графиков. В зависимости от применения каждой сети, можно начать с одной такой сети «сверхмалого мира», а затем перенастроить некоторые ребра или использовать несколько таких небольших сетей в качестве подграфов для более крупного графа.
Свойства маленького мира могут возникнуть естественным образом в социальных сетях и других реальных системах в процессе двухфазной эволюции. Это особенно часто встречается там, где временные или пространственные ограничения ограничивают добавление соединений между вершинами. Механизм обычно включает периодические сдвиги между фазами, при этом соединения добавляются во время «глобальной» фазы и усиливаются или удаляются во время «локальной» фазы.
Сети малых размеров могут измениться от класса без масштабирования к классу широких масштабов, распределение связности которых резко ограничено в соответствии с режимом степенного закона из-за ограничений, ограничивающих добавление новых каналов. При достаточно сильных ограничениях безмасштабные сети могут даже стать одномасштабными сетями, распределение связности которых характеризуется как быстро затухающий.
См. Также: Агрегация, ограниченная диффузией, Формирование паттернов
Преимущества сетей малого мира для групп социальных движений - это их сопротивление изменениям из-за устройства фильтрации, использующего узлы с высокой степенью связи, и его лучшая эффективность в передаче информации при сохранении минимального количества ссылок, необходимых для подключения к сети.
Сетевая модель маленького мира напрямую применима к теории аффинити-группы, представленной в социологических аргументах Уильямом Финнеганом. Аффинити-группы - это группы социальных движений, которые являются небольшими и полунезависимыми, приверженными более широкой цели или функции. Хотя в основном они не аффилированы на уровне узлов, некоторые члены с высокой связностью действуют как узлы связи, связывая различные группы через сеть. Эта модель маленького мира оказалась чрезвычайно эффективной тактикой протестных организаций против действий полиции. Клэй Ширки утверждает, что чем крупнее социальная сеть, созданная с помощью сетей малого мира, тем ценнее узлы с высокой связностью внутри сети. То же самое можно сказать и о модели аффинити-группы, где небольшое количество людей в каждой группе, подключенных к внешним группам, позволило в значительной степени мобилизоваться и адаптироваться. Практическим примером этого является создание сетей небольшого мира через группы по интересам, которые Уильям Финнеган описывает в связи с протестами ВТО в Сиэтле в 1999 году.
Было показано множество сетей, изучаемых в геологии и геофизике. иметь характеристики сетей малого мира. Сети, определенные в системах трещин и пористых веществах, продемонстрировали эти характеристики. Сейсмическая сеть в регионе Южной Калифорнии может быть сетью небольшого мира. Приведенные выше примеры встречаются в очень разных пространственных масштабах, демонстрируя масштабную инвариантность явления в науках о Земле. Климатические сети можно рассматривать как сети малого мира, в которых каналы имеют разную длину.
Сети малого мира использовались для оценки пригодности информации, хранящейся в больших базах данных. Эта мера называется мерой преобразования данных малого мира. Чем больше ссылки базы данных соответствуют небольшой сети, тем больше вероятность, что пользователь сможет извлекать информацию в будущем. Такое удобство использования обычно достигается за счет количества информации, которая может храниться в одном репозитории.
Одноранговая сеть Freenet при моделировании формирует небольшую сеть, позволяя хранить и извлекать информацию таким образом, чтобы эффективность масштабировалась по мере роста сети..
И анатомические связи в мозге, и сети синхронизации корковых нейронов демонстрируют топологию маленького мира.
Маленькая сеть нейронов может обладать кратковременной памятью. Компьютерная модель, разработанная Solla et al. имел два стабильных состояния, свойство (называемое бистабильностью ), которое считается важным для памяти хранилища. Активирующий импульс генерировал самоподдерживающиеся петли коммуникативной активности между нейронами. Второй импульс положил конец этой активности. Импульсы переключали систему между стабильными состояниями: потоком (запись «памяти») и стазисом (удержание ее). Нейронные сети малого мира также использовались в качестве моделей для понимания приступов.
На более общем уровне многие крупномасштабные нейронные сети в мозгу, такие как зрительная система и ствол мозга, проявляют свойства маленького мира.
Модель SW включает равномерное распределение звеньев большой дальности. Когда распределение длин линий следует по степенному закону, среднее расстояние между двумя участками изменяется в зависимости от мощности распределения.
