Глоссарий

Выберите одно из ключевых слов слева ...

Графики и СетиГрафики в повседневной жизни

Время чтения: ~15 min
Эта страница была автоматически переведена и может содержать ошибки. Пожалуйста, свяжитесь с нами, если вы хотите помочь нам пересмотреть переводы!

Мы видели много разных применений теории графов в предыдущих главах, хотя некоторые из них были немного надуманными. Оказывается, однако, что графики лежат в основе многих объектов, концепций и процессов в повседневной жизни.

Например, Интернет - это огромный виртуальный граф. Каждая вершина является отдельной веб-страницей, и каждое ребро означает, что между двумя страницами есть гиперссылка. Обратите внимание, что ссылки идут только в одну сторону, поэтому этот график и что этот график очень, очень, большой.

Некоторые веб-сайты, такие как Википедия или Facebook, имеют много входящих ссылок, в то время как многие меньшие сайты могут иметь очень мало входящих ссылок. Это основная концепция, которую Google использует для сортировки результатов поиска.

Сайты с большим количеством входящих ссылок, как правило, более высокого качества и должны отображаться в верхней части результатов поиска. Например, при поиске «Лондон» официальные туристические информационные сайты показываются перед небольшими магазинами в Лондоне или блогами людей, которые живут в Лондоне. Эта простая идея из теории графов, алгоритм Page Rank , сделала Google значительно лучше, чем другие ранние поисковые системы.

Интернет - самая большая сеть, когда-либо созданная человечеством. Это изображение показывает очень небольшую долю всех серверов, подключенных к Интернету:

© LyonLabs, LLC and Barrett Lyon, 2014

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

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

Графики также играют важную роль в транспортировке и навигации. Все сети рейсов, поездов и метро образуют графики, которые можно использовать при создании эффективных расписаний. Один из самых узнаваемых графиков - карта лондонского метро:

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

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

На этом изображении показана сеть рейсов коммерческих авиакомпаний по всей Северной Европе.

Есть множество других графиков в науке, технике или повседневной жизни:

Связи между атомами в молекулах и кристаллических решетках образуют график.

Распространение болезней и эпидемий можно смоделировать с помощью сети.

В биологии эволюционные деревья, которые показывают происхождение видов, образуют график.

Различные компоненты электрических цепей и компьютерных чипов образуют сеть.

Грамматическая структура языков может быть смоделирована с использованием графиков, например, для создания алгоритмов перевода.

Графы также имеют много приложений в области вероятности , теории игр и финансовой математики .

Социальные сети

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

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

В 2014 году у Facebook было 1,4 миллиарда активных пользователей и более 200 миллиардов друзей. Половина всех пользователей Facebook имеет более 200 друзей, а поскольку у большинства наших друзей такое же количество друзей, у нас легко могут быть десятки тысяч друзей друзей .

Теперь волнующим вопросом будет: если вы выберете двух случайных пользователей Facebook, сколько «дружеских сторон» вам понадобится, чтобы перейти от одного к другому? Например, расстояние между друзьями равно , расстояние между друзьями друзей равно , и так далее.

В 2016 году Facebook провел исследование, чтобы определить, как его пользователи связаны друг с другом. Они обнаружили, что в среднем вы подключены к кому-либо еще на Facebook через не более 3,57 других людей. И это включает в себя знаменитостей, политиков или даже роялти!

Другими словами, если вы выберете любого из миллиардов пользователей Facebook по всему миру, у них, вероятно, будет друг друга, который знает друга одного из ваших друзей. Мы говорим, что есть 3,57 степени разделения .

Geographic visualisation of all Facebook friendships in 2010.

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

В 1967 году Стэнли Милгрэм провел первый эмпирический эксперимент, в котором 296 участников, живущих в Небраске и Канзасе, попросили доставить письмо конкретному человеку, живущему в Бостоне, штат Массачусетс. Все они должны были выбрать друга, чтобы отправить письмо, который затем выбрал другого друга. На каждом шагу письмо приближалось к Бостону. Милгрэм обнаружил, что в среднем было только 5,2 промежуточных друзей - 5,2 степени разделения.

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