Том 11. Карты метро и нейронные сети. Теория графов

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

Изучение социальных сетей восходит к XIX веку. Здесь можно вспомнить Эмиля Дюркгейма и Фердинанда Тенниса. В начале XX века это направление интенсивно развивалось усилиями Георга Зиммеля. В первых исследованиях на эту тему рассматривались такие темы, как трудовые отношения между группами и отдельными работниками, отношения между культурными сообществами и так далее. Во второй половине XX столетия эти исследования охватили все сферы общества. Этой темой занимались группы ученых из Гарвардского (Харрисон Уайт, Толкотт Парсонс), Калифорнийского (Линтон Фриман), Чикагского, Торонтского и других университетов.

Анализ социальных сетей использовался при изучении распространения болезней (СПИДа, малярии, туберкулеза), инноваций, анализе воздействия политических решений и даже при изучении распространения слухов.

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

* * *

ДРУЗЬЯ ПОЛИТИКА

В математическом фольклоре эта задача известна уже много лет. Допустим, что в группе людей, состоящей как минимум из трех человек, у любых двух ее членов есть ровно один общий друг. Следовательно, всегда существует человек (так называемый политик), который будет другом всех членов группы. Пол Эрдёш и Альфред Реньи формализовали и решили эту задачу с помощью графов: если граф имеет n вершин (n >= 3) и для любой пары вершин существует вершина, смежная им обеим, то должна существовать вершина, смежная всем вершинам графа.

* * *

«Маленький мир» Стэнли Милгрэма

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

Графы и расписания

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

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

Рассмотрим последовательность повседневных действий, например покупку продуктов в нескольких магазинах и приготовление ужина. При выполнении этих действий можно следовать такому алгоритму.

1. Пронумеровать все задачи и оценить сроки их выполнения.

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