Сеть малого мира - Small-world network

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

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

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

{\ Displaystyle L \ propto \ log N}

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

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

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

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

Компактность сети количественно оценивается с помощью коэффициента малых размеров, рассчитываемого путем сравнения кластеризации и длины пути данной сети с эквивалентной случайной сетью в среднем с той же степенью. ${\ displaystyle \ sigma}$

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

если ( и ), сеть - это маленький мир. Однако известно, что эта метрика плохо работает, поскольку на нее сильно влияет размер сети.

{\ displaystyle \ sigma> 1}

{\ textstyle C \ gg C_ {r}}

{\ textstyle L \ приблизительно {L_ {r}}}

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

{\ displaystyle \ omega = {\ frac {L_ {r}} {L}} - {\ frac {C} {C _ {\ ell}}}}}

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

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

{\ displaystyle {\ 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 .

Р. Коэн и Хэвлин аналитически показали, что безмасштабные сети - это сверхмалые миры. В этом случае из-за концентраторов кратчайшие пути становятся значительно меньше и масштабируются по мере увеличения.

{\ Displaystyle L \ propto \ log \ log N}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Маленький мир с распределением длины ссылки

Модель SW включает в себя равномерное распределение линий дальней связи. Когда распределение длин каналов следует распределению по степенному закону, среднее расстояние между двумя сайтами изменяется в зависимости от мощности распределения.

Приложения

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

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

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

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

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

Приложения для вычислений

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

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

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

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

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

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

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

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

Смотрите также

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

использованная литература

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

Книги

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

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

Альберт Р., Барабаши А.Л. (2002). «Статистическая механика сложных сетей». Ред. Мод. Phys . 74 (1): 47–97. arXiv : cond-mat / 0106096 . Bibcode : 2002RvMP ... 74 ... 47 . DOI : 10.1103 / RevModPhys.74.47 . S2CID 60545 .
Барабаши А.Л., Альберт Р. (октябрь 1999 г.). «Возникновение масштабирования в случайных сетях». Наука . 286 (5439): 509–12. arXiv : cond-mat / 9910332 . Bibcode : 1999Sci ... 286..509B . DOI : 10.1126 / science.286.5439.509 . PMID 10521342 . S2CID 524106 .
Бартелеми М., Амарал Л.А. (1999). «Сети малого мира: свидетельство кроссоверной картины». Phys. Rev. Lett . 82 (15): 3180–3183. arXiv : cond-mat / 9903108 . Bibcode : 1999PhRvL..82.3180B . DOI : 10.1103 / PhysRevLett.82.3180 . S2CID 119398712 .
Дороговцев С.Н., Мендес Дж.Ф. (2000). «Точно решаемая аналогия сетей малого мира». Europhys. Lett . 50 (1): 1–7. arXiv : cond-mat / 9907445 . Bibcode : 2000EL ..... 50 .... 1D . DOI : 10,1209 / EPL / i2000-00227-1 . S2CID 11334862 .
Милгрэм С. (1967). «Проблема маленького мира». Психология сегодня . 1 (1): 60–67.
Ньюман М (2003). «Структура и функции сложных сетей». SIAM Обзор . 45 (2): 167–256. arXiv : cond-mat / 0303516 . Bibcode : 2003SIAMR..45..167N . DOI : 10.1137 / S003614450342480 . S2CID 65837 . pdf
Равид Д., Рафаэли С. (2004). «Асинхронные дискуссионные группы как Small World и Scale Free Networks». Первый понедельник . 9 (9). DOI : 10.5210 / fm.v9i9.1170 . S2CID 6388295 . [1]
Паршани Р., Булдырев С.В., Хавлин С. (январь 2011 г.). «Критическое влияние групп зависимостей на функции сетей» . Труды Национальной академии наук Соединенных Штатов Америки . 108 (3): 1007–10. arXiv : 1010,4498 . Bibcode : 2011PNAS..108.1007P . DOI : 10.1073 / pnas.1008404108 . PMC 3024657 . PMID 21191103 .
Булдырев С.В., Паршани Р., Пол Г., Стэнли Х.Э., Хэвлин С. (апрель 2010 г.). «Катастрофический каскад отказов во взаимозависимых сетях» . Природа . 464 (7291): 1025–8. arXiv : 0907.1182 . Bibcode : 2010Natur.464.1025B . DOI : 10,1038 / природа08932 . PMID 20393559 . S2CID 1836955 .

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

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

Languages

In other projects