07.02.2014

Математики МТИ упростили анализ социальных и транспортных сетей

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

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

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

Источники:

1. osp.ru