Русская Википедия:Мир тесен (граф)

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Значения

Файл:Small-world-network-example.png
Пример графа «Мир тесен», выделены вершины — хабы.
Средняя степень вершины = 3,833
Средняя длина кратчайшего пути = 1.803.
Коэффициент кластеризации = 0.522
Файл:Random graph gephi.png
Случайный граф
Средняя степень вершины = 2,833
Средняя длина кратчайшего пути = 2.109.
Коэффициент кластеризации = 0.167

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

<math>L \propto \log N</math>,

но при этом глобальный Шаблон:Iw не является малым.[1]

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

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

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

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

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

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

Принадлежность к классу графов «Мир тесен» оценивается сравнением кластеризации и длины путей данной сети с соответствующими параметрами эквивалентной случайной сети с такой же средней степенью вершин Шаблон:Sfn. Другой метод оценивания принадлежности сети к классу графов «Мир тесен» использует исходное определение графа «Мир тесен», сравнивая степень кластеризации данной сети со степенью кластеризации эквивалентного графа-решётки и длину среднего пути с длиной среднего пути в произвольном графеШаблон:Sfn. Мера принадлежности графа к классу «Мир тесен» (<math>\omega</math>) определяется, как

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

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

<math>L \propto \log \log N</math>

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

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

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

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

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

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

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

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

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

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

Основной механизм конструирования графов «Мир тесен» - Шаблон:Нп5

Построение графов «Мир тесен» с временным запаздываниемШаблон:Sfn, позволяет создавать не только фракталы, но и хаос при правильных условияхШаблон:Sfn или переход к хаосу в динамических сетяхШаблон:Sfn.

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

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

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

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

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

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

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

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

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

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

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

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

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

Шаблон:Main Анатомические соединения в мозгуШаблон:Sfn и сети синхронизации корковых нейроновШаблон:Sfn представляют собой примеры графов «Мир тесен».

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Cite web
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Мир_тесен_(граф)&oldid=10384470