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

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

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

,

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

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

Свойства графа «Мир тесен»

[править | править код]

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

 — расстояние от вершины до вершины
 — количество вершин в графе

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

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

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

 — средняя длина кратчайшего пути в рассматриваемом графе
 — степень кластеризации рассматриваемого графа
 — длина кратчайшего пути в среднем в случайном графе
 — степень кластеризации графа-решётки

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

Примеры графов «мир тесен»

[править | править код]

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

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

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

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

[править | править код]

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

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

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

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

Конструирование графов «Мир тесен»

[править | править код]

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

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

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

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

Применение и приложения

[править | править код]

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

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

[править | править код]

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

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

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

[править | править код]

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

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

[править | править код]

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

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

Графы «Мир тесен» в нейронных сетях головного мозга

[править | править код]

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

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

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

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

[править | править код]

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

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

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

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

Граф «Мир тесен» с распределением длины ссылок

[править | править код]

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

Децентрализованный алгоритм поиска

[править | править код]

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

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

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

Примечания

[править | править код]
  1. 1 2 Collective dynamics of small-world networks.
  2. Алексей Савватеев: Модели интернета и социальных сетей / Хабр. Дата обращения: 27 апреля 2022. Архивировано 27 апреля 2022 года.
  3. Barthelmy and Amaral, 1999.
  4. Barrat and Weigt.
  5. Dorogovtsev and Mendes.
  6. Barmpoutis and Murray.
  7. Complex networks Structure and dynamics, с. 8.
  8. Humphries, 2007.
  9. Telesford, Joyce, Hayasaka, Burdette, Laurienti, 2011.
  10. Cohen and Havlin and ben-Avraham, 2002.
  11. Scale-free networks are ultrasmall, 2003.
  12. Proteins, 2004, с. 292–299.
  13. Gene network, 2004, с. 280—4.
  14. Che, Ali, Reynolds, 2010.
  15. Handbook on Biological Networks, 2010, p. 23.
  16. patent.
  17. Lamanna, Longo, 2007, p. 90.
  18. Designing Robust Road Networks, 2010, p. 13.
  19. Protein Interaction, 2006, p. 17.
  20. Fractals with time-delay, 2002, с. 215—219.
  21. Chaos in small-world networks, 2001.
  22. Transition to chaos.
  23. Barmpoutis, Murray, 2010.
  24. 1 2 Shirky, 2008.
  25. Finnegan, 2003.
  26. Yang, 2001.
  27. Jimenez, Tiampo, Posadas, 2008.
  28. Information Theory & Business Intelligence Strategy.
  29. Hillard, 2010.
  30. Sandberg.
  31. Sporns, 2004.
  32. Yu, 2008.
  33. Cohen.
  34. Solla.
  35. Humphries, 2007, с. 367—375.
  36. Sole.
  37. WordNet, p. 1.
  38. WordNet.
  39. Antiqueira, p. 4.
  40. Antiqueira.
  41. Masucci.
  42. Dimension of spatially embedded networks, 2011.
  43. Kleinberg, 2006, p. 5.
  44. 1 2 Kleinberg, 2006, p. 6.

Литература

[править | править код]