Сеть маленького мира

Пример сети маленького мира
Хабы больше, чем другие узлы

Средняя степень = 3,833
Средняя длина кратчайшего пути = 1,803.
Коэффициент кластеризации = 0,522

Случайный график
Средняя степень = 2,833
Средняя длина кратчайшего пути = 2,109.
Коэффициент кластеризации = 0,167

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

$L\propto \log N$

в то время как глобальный коэффициент кластеризации не мал.

В контексте социальной сети это приводит к феномену маленького мира , когда незнакомцы связаны короткой цепочкой знакомств . Многие эмпирические графики демонстрируют эффект тесного мира, включая социальные сети , вики, такие как Arc.Ask3.Ru, генные сети и даже лежащую в основе архитектуру Интернета . Это вдохновение для многих сетевых архитектур в современном компьютерном оборудовании .

как класс случайных графов Определенная категория сетей маленького мира была определена Дунканом Уоттсом и Стивеном Строгацем в 1998 году. Они отметили, что графы можно классифицировать по двум независимым структурным характеристикам, а именно по коэффициенту кластеризации между узлами и среднему расстоянию (также известному как средняя длина кратчайшего пути ). Чисто случайные графы, построенные в соответствии с моделью Эрдеша-Реньи (ER) , демонстрируют небольшую среднюю длину кратчайшего пути (обычно варьирующуюся как логарифм количества узлов) наряду с небольшим коэффициентом кластеризации. Уоттс и Строгац подсчитали, что на самом деле многие реальные сети имеют небольшую среднюю длину кратчайшего пути, но при этом коэффициент кластеризации значительно выше, чем ожидалось по случайности. Затем Уоттс и Строгац предложили новую графовую модель, в настоящее время называемую моделью Уоттса и Строгаца , с (i) небольшой средней длиной кратчайшего пути и (ii) большим коэффициентом кластеризации. Переход в модели Уоттса-Строгаца между «большим миром» (таким как решетка) и маленьким миром был впервые описан Бартелеми и Амаралом в 1999 году. За этой работой последовало множество исследований, в том числе с точными результатами (Баррат и Вейгт, 1999; Дороговцев и Мендес ; Бармпутис и Мюррей, 2010).

Свойства сетей маленького мира

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

Тесность сетевого мира количественно оценивается с помощью коэффициента малого $\sigma$, рассчитанный путем сравнения кластеризации и длины пути данной сети с моделью Эрдеша – Реньи в среднем с той же степенью.

$\sigma ={\frac {\frac {C}{C_{r}}}{\frac {L}{L_{r}}}}$

если $\sigma >1$ ( ${\textstyle C\gg C_{r}}$ и ${\textstyle L\approx {L_{r}}}$), сеть — это маленький мир. Однако известно, что этот показатель работает плохо, поскольку на него сильно влияет размер сети.

Другой метод количественной оценки тесноты сети использует исходное определение сети малого мира, сравнивая кластеризацию данной сети с эквивалентной решетчатой ​​сетью и длину ее пути с эквивалентной случайной сетью. Мера маленького мира ( $\omega$) определяется как

$\omega ={\frac {L_{r}}{L}}-{\frac {C}{C_{\ell }}}$

Если характерная длина пути L и коэффициент кластеризации C рассчитываются на основе тестируемой сети, C _ℓ — это коэффициент кластеризации для эквивалентной решетчатой ​​сети, а L _r — характерная длина пути для эквивалентной случайной сети.

Еще один метод количественной оценки тесноты мира нормализует как кластеризацию сети, так и длину пути относительно этих характеристик в эквивалентной решетке и случайных сетях. Индекс маленького мира (SWI) определяется как

${\text{SWI}}={\frac {L-L_{\ell }}{L_{r}-L_{\ell }}}\times {\frac {C-C_{r}}{C_{\ell }-C_{r}}}$

И ω ′, и SWI находятся в диапазоне от 0 до 1 и, как было показано, отражают аспекты тесноты мира. Однако они придерживаются несколько разных концепций идеального маленького мира. Для данного набора ограничений (например, размера, плотности, распределения степеней) существует сеть, для которой ω ′ = 1, и, таким образом , ω стремится охватить степень, в которой сеть с заданными ограничениями является настолько маленькой, насколько это возможно. Напротив, может не существовать сети, для которой SWI = 1, поэтому SWI стремится определить степень, в которой сеть с заданными ограничениями приближается к теоретическому идеальному маленькому миру сети, где C ≈ C _ℓ и L ≈ L _r .

Примеры сетей маленького мира

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

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

Примеры сетей немаленького мира

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

Точно так же количество ретрансляционных станций, через которые должно пройти сообщение, не всегда было небольшим. В те дни, когда почту доставляли вручную или верхом на лошади, количество раз, когда письмо переходило из рук в руки от источника к месту назначения, было бы намного больше, чем сегодня. Количество раз, когда сообщение переходило из рук в руки во времена визуального телеграфа (около 1800–1850 гг.), определялось требованием, чтобы две станции были соединены прямой видимостью.

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

Надежность сети

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

В небольшой мировой сети со степенным распределением степеней удаление случайного узла редко приводит к резкому увеличению средней длины кратчайшего пути (или резкому уменьшению коэффициента кластеризации ). Это следует из того, что большинство кратчайших путей между узлами проходят через хабы , и удаление периферийного узла вряд ли будет мешать проходу между другими периферийными узлами. Поскольку доля периферийных узлов в маленькой мировой сети намного превышает долю хабов , вероятность удаления важного узла очень мала. Например, если бы небольшой аэропорт в Сан-Вэлли, штат Айдахо , был закрыт, это не увеличило бы среднее количество рейсов, которые другим пассажирам, путешествующим по Соединенным Штатам, пришлось бы совершать, чтобы добраться до соответствующих пунктов назначения. Однако если случайное удаление узла случайно затронет концентратор, средняя длина пути может значительно увеличиться. Это можно наблюдать ежегодно, когда северные узловые аэропорты, такие как Чикаго, Аэропорт О'Хара закрыт из-за снега; многим людям приходится совершать дополнительные рейсы.

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

Строительство сетей маленького мира

См. Также: Агрегация, ограниченная диффузией , и формирование паттернов.

Основным механизмом построения сетей маленького мира является механизм Уоттса-Строгаца .

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

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

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

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

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

Сети маленького мира могут перейти от безмасштабного класса к широкомасштабному классу, распределение связности которого имеет резкое ограничение в соответствии со степенным законом из-за ограничений, ограничивающих добавление новых каналов. При достаточно сильных ограничениях безмасштабные сети могут даже стать одномасштабными сетями, распределение связности которых характеризуется как быстро затухающее. Аналитически было также показано, что безмасштабные сети очень малы, а это означает, что расстояние масштабируется в соответствии с $L\propto \log \log N$.

Приложения

Приложения к социологии

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

Модель сети маленького мира напрямую применима к теории аффинити-групп, представленной в социологических аргументах Уильямом Финнеганом . Группы по интересам — это небольшие и полунезависимые группы социальных движений, приверженные более широкой цели или функции. Хотя они в основном не связаны на уровне узлов, несколько членов с высокой связностью функционируют как узлы связности, связывая различные группы через сеть. Эта модель маленького мира оказалась чрезвычайно эффективной тактикой организации протеста против действий полиции. Клэй Ширки утверждает, что чем крупнее социальная сеть, созданная посредством создания сетей маленького мира, тем более ценными являются узлы с высокой связностью внутри сети. То же самое можно сказать и о модели группы по интересам, где небольшое количество людей внутри каждой группы, связанных с внешними группами, обеспечивает значительную мобилизацию и адаптацию. Практическим примером этого является создание сетей маленького мира через группы по интересам, которые Уильям Финнеган обрисовал в общих чертах в связи с протестами ВТО в Сиэтле в 1999 году .

Приложения к наукам о Земле

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

Приложения к вычислениям

Сети маленького мира использовались для оценки удобства использования информации, хранящейся в больших базах данных. Эта мера называется «Мера преобразования данных маленького мира». Чем больше ссылки базы данных соответствуют сети маленького мира, тем больше вероятность того, что пользователь сможет извлекать информацию в будущем. Такое удобство использования обычно достигается за счет объема информации, которая может храниться в одном репозитории.

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

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

Нейронные сети маленького мира в мозге

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

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

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

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

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

См. также

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

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

Книги

• Бьюкенен М (2003). Нексус: маленькие миры и новаторская теория сетей . Norton, WW & Company, Inc. ISBN  978-0-393-32442-6 .
• Дороговцев С.Н., Мендес Ж.Ф. (2003). Эволюция сетей: от биологических сетей к Интернету и WWW . Издательство Оксфордского университета. ISBN  978-0-19-851590-6 .
• Уоттс-ди-джей (1999). Маленькие миры: динамика сетей между порядком и случайностью . Издательство Принстонского университета. ISBN  978-0-691-00541-6 .
• Фаулер Дж. Х. (2005). «Явка в маленьком мире». В Цукермане А (ред.). Социальная логика политики . Издательство Университета Темпл. стр. 269–287.

Журнальные статьи

• Альберт Р., Барабаси А.Л. (2002). «Статистическая механика сложных сетей». Преподобный Мод. Физ . 74 (1): 47–97. arXiv : cond-mat/0106096 . Бибкод : 2002РвМП...74...47А . дои : 10.1103/RevModPhys.74.47 . S2CID   60545 .
• Барабаси А.Л., Альберт Р. (октябрь 1999 г.). «Появление масштабирования в случайных сетях». Наука . 286 (5439): 509–12. arXiv : cond-mat/9910332 . Бибкод : 1999Sci...286..509B . дои : 10.1126/science.286.5439.509 . ПМИД   10521342 . S2CID   524106 .
• Бартелеми М., Амарал Л.А. (1999). «Сети маленького мира: свидетельства перекрестной картины». Физ. Преподобный Летт . 82 (15): 3180–3183. arXiv : cond-mat/9903108 . Бибкод : 1999PhRvL..82.3180B . дои : 10.1103/PhysRevLett.82.3180 . S2CID   119398712 .
• Дороговцев С.Н., Мендес Ж.Ф. (2000). «Точно решаемая аналогия сетей маленького мира». Еврофиз. Летт . 50 (1): 1–7. arXiv : cond-mat/9907445 . Бибкод : 2000EL.....50....1D . дои : 10.1209/epl/i2000-00227-1 . S2CID   11334862 .
• Милгрэм С. (1967). «Проблема маленького мира». Психология сегодня . 1 (1): 60–67.
• Ньюман М. (2003). «Структура и функции сложных сетей». Обзор СИАМ . 45 (2): 167–256. arXiv : cond-mat/0303516 . Бибкод : 2003SIAMR..45..167N . дои : 10.1137/S003614450342480 . S2CID   65837 . pdf. Архивировано 14 марта 2021 г. в Wayback Machine.
• Равид Д., Рафаэли С. (2004). «Асинхронные дискуссионные группы как маленький мир и сети без масштабирования» . Первый понедельник . 9 (9). дои : 10.5210/fm.v9i9.1170 . S2CID   6388295 . [1]

Внешние ссылки

• Динамические сети близости , Сет Дж. Чендлер, Демонстрационный проект Wolfram .
• Запись о сетях малого мира в Scholarpedia (Мейсон А. Портер)