Граф «Мир те́сен» (ма́ленький мир) — разновидность графа, который имеет следующее свойство: если взять две произвольные вершины a и b, то они с большой вероятностью не являются смежными, однако одна достижима из другой посредством небольшого количества переходов через другие вершины. А именно, граф «Мир тесен» определяется как сеть, в которой типичное расстояние L между двумя произвольно выбранными вершинами (количество шагов, необходимых, чтобы достичь одну из другой) растёт пропорционально логарифму от числа вершин N в сети, таким образом: , но при этом глобальный коэффициент кластеризации не является малым.
В контексте социальной сети это приводит к феномену «Мир тесен», то есть незнакомых людей связывает небольшое количество промежуточных знакомых. Много реально существующих графов хорошо моделируются через графы «Мир тесен». Социальные сети, связность сети Интернет, вики-сайты, такие, как Википедия, и проявляют свойства графа «Мир тесен». Дункан Уоттс и Стивен Строгац в 1998 году идентифицировали определённую категорию графов «Мир тесен» как класс случайных графов. Они отметили, что такие графы могут быть классифицированы в соответствии с двумя независимыми структурными особенностями, а именно коэффициент кластеризации и расстояние от одной вершины до другой в среднем (также известное как длина кратчайшего пути в среднем). Совершенно случайные графы, построенные в соответствии с моделью Эрдёша — Реньи, имеют малую длину кратчайшего пути в среднем (она растёт как логарифм от количества вершин в графе) и маленький коэффициент кластеризации. Уоттс и Строгац выяснили, что большинство реально существующих сетей имеют малую длину кратчайшего пути в среднем, но коэффициент кластеризации в них существенно выше, чем ожидается при случайном выборе. После этого Уоттс и Строгац предложили новую модель графа, в настоящее время называемую , для которой характерны (i) малая длина кратчайшего пути в среднем, и (ii) большой коэффициент кластеризации. Пересечение в модели Уоттса и Строгаца между «большим миром» (таким, как решётчатый граф) и маленьким миром было впервые описано Бартелми и Амарал в 1999. За этой работой последовало большое количество исследований.
Свойства графа «Мир тесен» Графы «Мир тесен» имеют тенденцию содержать в себе клики и почти-клики, под которыми понимают подсети, имеющие связи почти между всеми вершинами в них. Это следует из определения такого свойства графа, как высокий коэффициент кластеризации. Во-вторых, большинство пар вершин будут соединены хотя бы одним коротким путём. Более строго: расстояние от одной вершины до другой в среднем (также известное как длина кратчайшего пути в среднем) относительно мало. Длина кратчайшего пути в среднем высчитывается по следующей формуле:
— расстояние от вершины до вершины — количество вершин в графе
Некоторые другие особенности, которые будут описаны далее, часто присутствуют в графах «Мир тесен». Обычно в таких графах много хабов — вершин, степень которых значительно (во много раз) больше чем степени большинства вершин графа. Именно эти хабы уменьшают средний кратчайший путь графа. Типичным примером графа «Мир тесен» является сеть авиарейсов с узлами-аэропортами. Между любыми двумя городами в мире потребуется, вероятно, не больше трёх перелётов из-за того, что большинство авиарейсов проходят через узловые аэропорты.
Для анализа этого свойства (а именно, наличия хабов) учитывают долю вершин в сети, которые имеют большую степень. Сети с бо́льшим количеством хабов, чем ожидается, будут иметь бо́льшую долю вершин с высокой степенью, и очень много вершин с малыми степенями. Следовательно распределение степеней вершин графа будет . Графы очень разной топологии классифицируются как графы «Мир тесен», если выполняются указанные выше два условия.
Принадлежность к классу графов «Мир тесен» оценивается сравнением кластеризации и длины путей данной сети с соответствующими параметрами эквивалентной случайной сети с такой же средней степенью вершин . Другой метод оценивания принадлежности сети к классу графов «Мир тесен» использует исходное определение графа «Мир тесен», сравнивая степень кластеризации данной сети со степенью кластеризации эквивалентного графа-решётки и длину среднего пути с длиной среднего пути в произвольном графе. Мера принадлежности графа к классу «Мир тесен» () определяется, как
— средняя длина кратчайшего пути в рассматриваемом графе — степень кластеризации рассматриваемого графа — длина кратчайшего пути в среднем в случайном графе — степень кластеризации графа-решётки
Р. Коуэн и Шломо Хавлин показали аналитически, что безмасштабные сети — ультра-малые миры. В этом случае, из-за хабов, кратчайшие пути становятся существенно короче и масштабируются как
Примеры графов «мир тесен» Свойства графа «мир тесен» были обнаружены во многих объектах реального мира, включая карты дорог, пищевые цепочки, электрические сети, сети протекания метаболизма (metabolite processing networks), нейронные сети, сети избирателей, граф телефонных звонков и сети социального влияния.
Белок-белковые взаимодействия имеют такое свойство графа «Мир тесен», как соответствие степенному закону распределения.
Аналогично, свойствами графа «Мир тесен» обладает регуляция транскрипции, в которой вершинам соответствуют гены, причём они связаны, если один ген имеет вверх- или вниз-регулирующее генетическое влияние на другой.
Надёжность сети Некоторыми исследователями (например, Barabási ) было высказано предположение, что распространённость графов «Мир тесен» в биологических системах может отражать эволюционное преимущество такой топологии. Поводом к такому предположению стала гипотеза, что графы «Мир тесен» более устойчивы при различных внешних воздействиях по сравнению с другими топологиями сети. Если бы эта гипотеза была верна, то это обеспечило бы преимущество биологическим системам, которые являются субъектами мутаций и вирусных инфекций.
В графах «Мир тесен» со степенным законом распределения степеней вершин удаление случайной вершины редко служит причиной существенного увеличения кратчайшего пути в среднем (или существенного уменьшения коэффициента кластеризации). Это следует из того факта, что большинство кратчайших путей проходят через хаб, и если периферическая вершина удаляется, маловероятно, что она вмешается в прохождение между другими периферийными вершинами. Поскольку доля периферийных вершин в графе «Мир тесен» существенно выше, чем доля хабов, вероятность удаления важной вершины крайне мала. Например, если маленький аэропорт в Петрозаводске перестанет функционировать, то это не увеличит среднее количество полётов, которые требуются пассажирам, чтобы добраться до точки назначения. Тем не менее, если случайное удаление попадает в хаб, длина кратчайшего пути в среднем может вырасти весьма существенно. Это можно увидеть ежегодно, когда какой-либо аэропорт, располагающийся в северных штатах в США, такой, как Чикагский аэропорт О’Хара (штат Иллинойс) заносит снегом, и многие люди вынуждены лететь с пересадками и добираться до пункта назначения окольными путями.
В отличие от графа «Мир тесен», в случайной сети, в которой все вершины имеют приблизительно одинаковое количество соединений, удаление случайной вершины увеличивает длину кратчайшего пути в среднем незначительно, но одинаково для любой удаляемой вершины. В этом смысле случайные сети уязвимы для случайных возмущений, в то время как графы «Мир тесен» устойчивы. Однако графы «Мир тесен» уязвимы для направленных атак на хабы, в то время как в случайных сетях нельзя выбрать цели, уничтожение которых приведёт к катастрофическим последствиям.
Соответственно, вирусы эволюционировали таким образом, чтобы взаимодействовать с протеинами-хабами, такими как p53, тем самым внося существенные изменения в поведение клеток, благоприятствующие воспроизведению вирусов.
Конструирование графов «Мир тесен» Основной механизм конструирования графов «Мир тесен» -
Построение графов «Мир тесен» с временным запаздыванием, позволяет создавать не только фракталы, но и хаос при правильных условиях или переход к хаосу в динамических сетях.
При решении задачи о степени диаметра конструируется граф, в котором количество соседей каждой вершины ограничено, в то время как расстояние между любой парой вершин (диаметр сети) минимизируется. Конструирование таких графов «Мир тесен» осуществляется в рамках усилий нахождения графов порядка, близкого к пределу Мура.
Другой путь конструирования графов «Мир тесен» с нуля показан у Бармпутиса и Мюррея, где строится сеть с очень маленьким средним расстоянием и очень большой средней кластеризацией. Быстрый алгоритм константной сложности дан вместе с измерениями надёжности полученных графов. В зависимости от области, можно начать с одного такого «ultra small-world» графа, и затем заново включить некоторые рёбра, или использовать некоторые маленькие такие сети как подграф большего графа.
Применение и приложения Граф «Мир тесен» используют для моделирования в различных областях.
Приложения в социологии Одно из преимуществ графов «Мир тесен» для общественного движения состоит в их защищённости от фильтрующих аппаратов, использующих сильно связанные вершины. Другое преимущество — лучшая эффективность в передаче информации при сохранении количества ссылок, необходимых для подключения к сети на минимальном уровне.
Модель графа «Мир тесен» напрямую применима к теории аффинити-групп, представленной в социологических аргументах Уильямом Финнеганом. Аффинити-группы — это общественные движения, являющиеся маленькими и полунезависимыми, но ставящие перед собой значительные цели и задачи. Несмотря на то, что отдельные участники относительно независимы и самостоятельны, несколько участников, обладающих высокой степенью связности, соответствуют хабам в графе «Мир тесен» — являются соединяющими вершинами, связывающими различные группы. Такая модель графа «Мир тесен» доказала чрезвычайно эффективную тактику организации протеста против действий полиции. утверждает, что чем больше социальная сеть основывается на малых сетях, образуя граф «Мир тесен», тем более ценны вершины высокой степени связности в этой сети. То же самое может быть сказано и о модели аффинити-групп, где несколько людей в каждой группе соединены с внешними группами, которым позволена значительно большая степень мобилизации и адаптации. Практический пример этого — граф «Мир тесен» через аффинити-группы, который Уильям Финнеган наметил в общих чертах в .
Приложение к наукам о Земле Много сетей, изучаемых в геологии и геофизике, по характеристикам похожи на граф «Мир тесен». Сети, определённые в системе трещин и пористых субстанций, демонстрируют эти характеристики. Сейсмические сети региона Южной Калифорнии могут быть графами «Мир тесен». Приведенные выше примеры встречаются на самых разных пространственных масштабах, демонстрируя масштабную инвариантность феномена в науках о Земле.
Приложения к вычислениям Графы «Мир тесен» были использованы для оценки возможности использования информации, хранящейся в больших базах данных. Мера оценки называется «Small World Data Transformation Measure». Чем больше связи базы данных похожи на граф «Мир тесен» — тем более вероятно, что пользователь будет в состоянии извлечь информацию в будущем. Это удобство обычно достигается за счёт количества информации, которое может храниться в том же хранилище.
P2P-сеть Freenet образует граф «Мир тесен», предоставляя возможность хранения и нахождения информации таким образом, чтобы эффективно масштабироваться при росте сети.
Графы «Мир тесен» в нейронных сетях головного мозга
Анатомические соединения в мозгу и сети синхронизации корковых нейронов представляют собой примеры графов «Мир тесен».