Мир тесен (граф)

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Пример графа «Мир тесен», выделены вершины — хабы.
Средняя степень вершины = 1,917
Средняя длина кратчайшего пути = 1.803.
Коэффициент кластеризации = 0.522
Случайный граф
Средняя степень вершины = 1,417
Средняя длина кратчайшего пути = 2.109.
Коэффициент кластеризации = 0.167

Граф «Мир тéсен» (ма́ленький мир) — разновидность графа, который имеет следующее свойство: если взять две произвольные вершины a и b, то они с большой вероятностью не являются смежными, однако одна достижима из другой посредством небольшого количества переходов через другие вершины. А именно, граф «Мир тесен» определяется как сеть, в которой типичное расстояние L между двумя произвольно выбранными вершинами (количество шагов, необходимых, чтобы достичь одну из другой) растёт пропорционально логарифму от числа вершин N в сети, таким образом[1]:

L \propto \log N

В контексте социальной сети это приводит к феномену «Мир тесен», то есть незнакомых людей связывает небольшое количество промежуточных знакомых. Много реально существующих графов хорошо моделируются через графы «Мир тесен». Социальные сети, связность сети Интернет, вики-сайты, такие, как Википедия[⇨], и генные сети проявляют свойства графа «Мир тесен». Дункан Ватц и Стивен Строгац (англ.)русск. в 1998 году идентифицировали определённую категорию графов «Мир тесен» как класс случайных графов[1]. Они отметили, что такие графы могут быть классифицированы в соответствии с двумя независимыми структурными особенностями, а именно коэффициент кластеризации и расстояние от одной вершины до другой в среднем (также известное как длина кратчайшего пути в среднем). [⇨] Совершенно случайные графы, построенные в соответствии с моделью Эрдёша — Реньи (англ.)русск., имеют малую длину кратчайшего пути в среднем (она растёт как логарифм от количества вершин в графе) и маленький коэффициент кластеризации. Ватц и Строгац выяснили, что большинство реально существующих сетей имеют малую длину кратчайшего пути в среднем, но коэффициент кластеризации в них существенно выше, чем ожидается при случайном выборе. После этого Ватц и Строгац предложили новую модель графа, в настоящее время называемую модель Ватца и Строгаца (англ.)русск., для которой характерны (i) малая длина кратчайшего пути в среднем, и (ii) большой коэффициент кластеризации. Пересечение в модели Ватца и Строгаца между «большим миром» (таким, как решётчатый граф) и маленьким миром было впервые описано Бартелми и Амарал в 1999[2]. За этой работой последовало большое количество исследований[3][4][5].

Свойства графа «Мир тесен»[править | править вики-текст]

Графы «Мир тесен» имеют тенденцию содержать в себе клики и почти-клики, под которыми понимают подсети, имеющие связи почти между всеми вершинами в них. Это следует из определения такого свойства графа, как высокий коэффициент кластеризации[en]. Во-вторых, большинство пар вершин будут соединены хотя бы одним коротким путём. Более строго: расстояние от одной вершины до другой в среднем (также известное как длина кратчайшего пути в среднем) относительно мало. Длина кратчайшего пути в среднем высчитывается по следующей формуле[6]:

 L = \frac{1}{N(N-1)}\sum_{i,j \in N, i \ne j}d_{i j}
 d_{i j} — расстояние от вершины i до вершины j
N  — количество вершин в графе

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

Для анализа этого свойства (а именно, наличия хабов) учитывают долю вершин в сети, которые имеют специфическое количество входящих соединений (степень распределения сети (англ.)русск.). Сети с бо́льшим количеством хабов, чем ожидается, будут иметь бо́льшую долю вершин с высокой степенью, следовательно, степень распределения будет увеличиваться до высоких значений. В разговорной речи это называется «распределение тяжёлого хвоста»[en]. Наличие у сети высокой степени распределения, соответствующей критерию согласия со степенным законом распределения[en], является признаком того, что сеть является графом «Мир тесен». Сети со степенным законом распределения также известны как «безмасштабные сети». Графы очень разной топологии классифицируются как графы «Мир тесен» до тех пор, пока выполняются указанные выше два условия (высокая степень распределения и соответствие степенному закону).

Принадлежность к классу графов «Мир тесен» оценивается сравнением кластеризации и длины путей данной сети с соответствующими параметрами эквивалентной случайной сети с такой же степенью распределения[7]. Другой метод оценивания принадлежности сети к классу графов «Мир тесен» использует исходное определение графа «Мир тесен», сравнивая степень кластеризации данной сети со степенью кластеризации эквивалентного графа-решётки и длину среднего пути с длиной среднего пути в произвольном графе[8]. Мера принадлежности графа к классу «Мир тесен» (\omega) определяется, как

\omega = \tfrac{L_r}{L} - \tfrac{C}{C_l}
 L — длина кратчайшего пути в среднем в рассматриваемом графе
 C — степень кластеризации рассматриваемого графа
 L_{r} — длина кратчайшего пути в среднем в случайном графе
 C_{l} — степень кластеризации графа-решётки

Р. Коуэн и Шломо Хавлин[en] [9][10] показали аналитически, что безмасштабные сети — ультра-малые миры. В этом случае, из-за хабов, кратчайшие пути становятся существенно короче и масштабируются, как

L \propto \log \log N

Примеры графов «мир тесен»[править | править вики-текст]

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

Белок-белковые взаимодействия имеют такое свойство графа «Мир тесен», как соответствие степенному закону распределения[11].

Аналогично, свойствами графа «Мир тесен» обладает регуляция транскрипции, в которой вершинам соответствуют гены, причём они связаны, если один ген имеет вверх- или вниз-регулирующее генетическое влияние на другой[12].

Надёжность сети[править | править вики-текст]

Некоторыми исследователями (например, Barabási[en] ) было высказано предположение, что распространённость графов «Мир тесен» в биологических системах может отражать эволюционное преимущество такой топологии. Поводом к такому предположению стала гипотеза, что графы «Мир тесен» более устойчивы при различных внешних воздействиях по сравнению с другими топологиями сети. Если бы эта гипотеза была верна, то это обеспечило бы преимущество биологическим системам, которые являются субъектами мутаций и вирусных инфекций[13].

В графах «Мир тесен» со степенным законом[en] распределения степеней вершин удаление случайной вершины редко служит причиной существенного увеличения кратчайшего пути в среднем (или существенного уменьшения коэффициента кластеризации[en]). Это следует из того факта, что большинство кратчайших путей проходят через хабы[en], и если периферическая вершина удаляется, маловероятно, что она вмешается в прохождение между другими периферийными вершинами. Поскольку доля периферийных вершин в графе «Мир тесен» существенно выше, чем доля хабов[en], вероятность удаления важной вершины крайне мала[14]. Например, если маленький аэропорт в Петрозаводске перестанет функционировать, то это не увеличит среднее количество полётов, которые требуются пассажирам, чтобы добраться до точки назначения. Тем не менее, если случайное удаление попадает в хаб, длина кратчайшего пути в среднем может вырасти весьма существенно. Это можно увидеть ежегодно, когда северный аэропорт в США, такой, как Чикагский аэропорт О’Хара заносит снегом, и многие люди вынуждены лететь с пересадками и добираться до пункта назначения окольными путями.

В отличие от графа «Мир тесен», в случайной сети, в которой все вершины имеют приблизительно одинаковое количество соединений, удаление случайной вершины увеличивает длину кратчайшего пути в среднем незначительно, но одинаково для любой удаляемой вершины. В этом смысле случайные сети уязвимы к случайным возмущениям, в то время как графы «Мир тесен» устойчивы[15]. Однако графы «Мир тесен» уязвимы к направленным атакам на хабы, в то время как в случайных сетях нельзя выбрать цели, уничтожение которых приведёт к катастрофическим последствиям[16][17].

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

Конструирование графов «Мир тесен»[править | править вики-текст]

Основной механизм конструирования графов «Мир тесен» - Модель Ватца-Строгаца[en]

Построение графов «Мир тесен» с временным запаздыванием[19], позволяет создавать не только фракталы, но и хаос при правильных условиях[20] или переход к хаосу в динамических сетях[21].

При решении задачи о степени диаметра[en] конструируется граф, в котором количество соседей каждой вершины ограничено, в то время как расстояние между любой парой вершин (диаметр сети) минимизируется. Конструирование таких графов «Мир тесен» осуществляется в рамках усилий нахождения графов порядка, близкого к пределу Мура.

Другой путь конструирования графов «Мир тесен» с нуля показан у Бармпутиса и Мюррея[22], где строится сеть с очень маленьким средним расстоянием и очень большой средней кластеризацией. Быстрый алгоритм константной сложности дан вместе с измерениями надёжности полученных графов. В зависимости от области, можно начать с одного такого «ultra small-world» графа, и затем заново включить некоторые рёбра, или использовать некоторые маленькие такие сети как подграф большего графа.

Смотрите также: en:Diffusion-limited aggregation, en:pattern formation

Применение и приложения[править | править вики-текст]

Граф «Мир тесен» используют для моделирования в различных областях.

Приложения в социологии[править | править вики-текст]

Одно из преимуществ графов «Мир тесен» для общественного движения состоит в их защищённости от фильтрующих аппаратов, использующих сильно связанные вершины. Другое преимущество — лучшая эффективность в передаче информации при сохранении количества ссылок, необходимых для подключения к сети на минимальном уровне[23].

Модель графа «Мир тесен» напрямую применима к теории аффинных групп[en], представленной в социологических аргументах Уильямом Финнеганом[en]. Аффинные группы — это общественные движения, являющиеся маленькими и полунезависимыми, но ставящие перед собой значительные цель и задачи. Несмотря на то, что отдельные участники относительно независимы и самостоятельны, несколько участников, обладающих высокой степенью связности, соотвествуют хабам в графе «Мир тесен» — являются соединяющими вершинами, связывающими различные группы. Такая модель графа «Мир тесен» доказала чрезвычайно эффективную тактику организации протеста против действия полиции[24]. Клей Ширки[en] утверждает, что чем больше социальная сеть основывается на малых сетях, образуя граф «Мир тесен», тем более ценны вершины высокой степени связности в этой сети[23]. То же самое может быть сказано и о модели аффинных групп, где несколько людей в каждой группе соединены с внешними группами, которым позволена значительно большая степень мобилизации и адаптации. Практический пример этого — граф «Мир тесен» через аффинные группы, который Уильям Финнеган наметил в общих чертах в протестах 1999 года в Сиэтле[en].

Приложение к наукам о Земле[править | править вики-текст]

Много сетей, изучаемых в геологии и геофизике, по характеристикам похожи на граф «Мир тесен». Сети, определённые в системе трещин и пористых субстанций, демонстрируют эти характеристики[25]. Сейсмические сети региона Южной Калифорнии могут быть графами «Мир тесен»[26]. Приведенные выше примеры встречаются на самых разных пространственных масштабах, демонстрируя масштабную инвариантность феномена в науках о Земле.

Приложения к вычислениям[править | править вики-текст]

Графы «Мир тесен» были использованы для оценки возможности использования информации, хранящейся в больших базах данных. Мера оценки называется «Small World Data Transformation Measure»[27][28]. Чем больше связи базы данных похожи на граф «Мир тесен» — тем более вероятно, что пользователь будет в состоянии извлечь информацию в будущем. Это удобство обычно достигается за счёт количества информации, которое может храниться в том же хранилище.

P2P-сеть Freenet образует граф «Мир тесен»,[29] предоставляя возможность хранения и нахождения информации таким образом, чтобы эффективно масштабироваться при росте сети.

Графы «Мир тесен» в нейронных сетях головного мозга[править | править вики-текст]

Анатомические соединения в мозгу[30] и сети синхронизации корковых нейронов[31] представляют собой примеры графов «Мир тесен».

Граф «Мир тесен» из нейронов может проявлять свойства рабочей памяти. Компьютерная модель, разработанная Солла и др.[32][33], имеет два стабильных состояния; это свойство называется бистабильностью (англ.)русск.и считается важным в хранении памяти. Активирующий импульс генерируется самоподдерживающимися петлями коммуникационной активности среди нейронов. Второй импульс заканчивает эту активность. Пульсы переключают систему между стабильными состояниями: поток (запись «памяти») и состояние покоя (хранение памяти).

На более общем уровне многие крупные нейронные сети головного мозга, такие как зрительная система и ствол головного мозга, проявляют свойства графа «Мир тесен»[34].

Граф «Мир тесен» в вычислительной лингвистике и в задачах по обработке текста[править | править вики-текст]

Об истории и развитии языков известно мало. А ведь речь — одно из величайших достижений человеческой эволюции! У всех языков есть общие признаки: например, синтаксические и семантические категории. Для большинства языков характерен закон Ципфа. Для изучения различных свойств языков используются сети слов (то есть сети, в которых вершинам соответствуют слова, а рёбрам — какие-либо связи между словами). Также они могут быть использованы для обоснования различных гипотез о развитии языков. Например, исходя из сходства языков делается вывод о наличии у них общего предка. Однако сходство может быть вызвано влиянием языков друг на друга и заимствованием слов[35].

В семантической сети английского языка WordNet полисемия имеет огромное влияние на организацию семантического графа. Из-за неё семантический граф является графом «Мир тесен»[36]. Вершинами с высокой степенью (хабами), являются вершины, представляющие абстрактные понятия, такие как линия, голова, или круг[37].

Одна из задач обработки естественного языка — задача идентификации авторства текста. Один из методов — нахождение авторского инварианта. Сначала текст обрабатывается, из него удаляются шумовые слова (предлоги, союзы и т. п.). Затем строится сеть, в которой вершины соответствуют словам, а рёбра проводятся между вершинами, которые соответствуют словам, которые в тексте расположены рядом. Установлено, что полученный граф является графом «Мир тесен»[38]. Если посчитать у сети, построенной по литературному произведению, некоторые параметры (например, среднюю степень вершины, коэффициент кластеризации, корреляцию степени вершин), то можно заметить, что в произведениях одного автора эти параметры изменяются в относительно небольшом диапазоне, в то время как у разных авторов эти параметры отличаются гораздо сильнее[39].

Если представить статьи Википедии как вершины, а ссылки между страницами представить рёбрами между соответствующими вершинами, то получается граф, обладающий свойствами графа «Мир тесен». Причинами этого являются уже указанная выше принадлежность к классу графов «Мир тесен» семантической сети слов, а так же наличие в Википедии списков и категорий, выполняющих роль хабов. Высокая степень связности Википедии дополнительно поддерживается проектом «Связность»[40]. На этом свойстве Википедии основана игра, цель которой — за 5 шагов добраться от случайной статьи до заданной.

Граф «Мир тесен» с распределением длины ссылок[править | править вики-текст]

Модель графа «Мир тесен» включает равномерное распределение длин ссылок, подчиняющееся степенному закону распределения, среднее расстояние между двумя вершинами изменяется в зависимости от силы распределения[41].

Децентрализованный алгоритм поиска[править | править вики-текст]

Если в эксперименте Стэнли Милгрэма исследователю требуется найти именно кратчайший путь, то ему надо отправить письма всем своим знакомым и заставить их сделать то же самое. Такой «флуд» в сети достигнет цели так быстро, как только возможно, но такая массовая рассылка практически невозможна. Другой вариант эксперимента — отправлять письмо только одному человеку за раз. В результате проведения эксперимента Мир тесен было совершено поразительное алгоритмическое открытие: в графе «Мир тесен» людям, не знающим всю структуру графа, а имеющим только локальную информацию (о своих знакомых), удаётся коллективно найти относительно короткий путь к цели (наличие относительно короткого пути является известным свойством графов типа «Мир тесен»)[42].

Возникает вопрос: почему социальная сеть структурирована таким образом, что такой децентрализованный алгоритм поиска даёт оптимальные результаты? Подобные децентрализованные алгоритмы поиска работают также во Всемирной паутине, в нейронных сетях и во множестве других областей. Следовательно, понимание алгоритмов работы децентрализованных поисковых алгоритмов обеспечит их широкое применение[43].

Для дальнейших рассуждений необходимо сформулировать более строгое определение децентрализованного алгоритма поиска. Алгоритм рекурсивный: мы стоим в вершине v, нам нужно достичь вершины t, мы знаем лишь соседей вершины v, среди них нужно выбрать вершину w и запустить алгоритм от неё. Децентрализованный алгоритм оценивается временем доставки — ожидаемым количеством шагов, необходимых для достижения цели, при этом граф «Мир тесен», стартовая и целевая вершины генерируются случайным образом. Цель исследований — найти полилогарифмические[en] относительно n алгоритмы децентрализованного поиска. Эти исследования проводил Джон Клейнберг[en] в работе «Complex networks and decentralized search algorithms»[43].

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

  • V.Van Noort, B.Snel, MA.Huynen (Mar 2004). «The yeast coexpression network has a small-world, scale-free architecture and can be explained by a simple model». EMBO Rep. 5 (3): 280–284. DOI:10.1038/sj.embor.7400090. PMID 14968131.
  • D.Barmpoutis and R.M. Murray (2010). «Networks with the Smallest Average Distance and the Largest Average Clustering».

Ссылки[править | править вики-текст]