Scientific problem

Математик Андрей Райгородский о структуре графа, вопросе надежности компьютерной сети и о том, как ловить спам

В проекте ScienceHub главный редактор проекта ПостНаука Ивар Максутов беседует с учеными в их лабораториях о новых технологиях, перспективах исследований и новых профессиях, которые появятся благодаря научным открытиям.

ПостНаука побывала в отделе теоретических и прикладных исследований компании «Яндекс», которым руководит Андрей Райгородский, чтобы подробнее разобраться в теории графов, понять, как она работает в мире современных технологий, и узнать, кто спасет нас от спама в будущем.

Для человека, который совсем не знает, что такое граф, правильно рассказывать в совершенно конкретных терминах. Представьте себе, что у вас есть большая пространственная молекула, которая состоит из жестких шариков, не важно, из чего сделанных (из картона, из металла). И эти шарики между собой перелинкованы, то есть соединены проволочками, прямолинейными отрезками. Получается жесткая конструкция, которую в математике принято называть графом. Это чисто наглядная интерпретация — в виде молекулы. Хотя мне думается, она кажется удобной всякому, кто пытается представить, что такое граф. Абстрактно же граф устроен таким образом: у него есть множество вершин и множество ребер. Собственно, те шарики, которые мы видим в пространстве, — это вершины графа. А проволочки, которые их соединяют, — это ребра графа. Если говорить в абстрактных терминах, вершины — это просто некоторые конечные множества каких-то элементов.

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

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

Источник: http://postnauka.ru/tv/19240