Исследователи из Мадридского университета имени Карлоса III (Universidad Carlos III de Madrid, UC3M) разработали алгоритм, основанный на поведении муравьёв при поиске еды. Данный алгоритм, как утверждают авторы, ускоряет поиск связей между элементами социальных сетей.
Одним из основных технических вопросов в области социальных сетей, которые становятся всё более и более разнообразными, является поиск цепочки связей, которая ведет от одного человека к другому. Наибольшую проблему здесь представляет огромный размер таких сетей. При этом результат поиска должен быть получен относительно быстро, так как конечный пользователь ожидает получить быстрый ответ на свой запрос. Чтобы решить эту проблему исследователи из UC3M разработали алгоритм SoSACO, ускоряющий поиск пути между двумя узлами графа, представляющего выбранную социальную сеть.
Принципы работы SoSACO основаны на поведении, оттачиваемом в течение тысячелетий самыми дисциплинированными из насекомых нашей планеты при поиске еды. Алгоритмы, используемые колониями муравьев, позволяют им найти короткий путь между муравейником и источником еды. Муравьи отмечают путь к еде при помощи химических веществ, называемых феромонами. «В проведенном нами исследовании»,- объясняют авторы,- «помимо путей, помеченных феромонами, мы создали пути, помеченные запахом еды, что позволило муравьям найти еду гораздо быстрее». Основные результаты данного исследования, проведенного Джессикой Ривьеро в лаборатории LABDA (Laboratorio de Bases de Datos Avanzadas) в рамках работы над её докторской диссертацией, приведены в статье «Using the ACO algorithm for path searches in social networks» («Использование алгоритма АСО для поиска путей в социальных сетях»), опубликованной в журнале Applied Intelligence.
«Первые полученные результаты показывают, что применение данного алгоритма в реальных социальных сетях позволяет получать оптимальный ответ за крайне малое время (десятки миллисекунд)»,- Джессика Ривьеро.
Возможные приложения
Благодаря разработанному алгоритму, можно быстро находить путь (цепочку связей) между элементами социальных сетей, не изменяя при этом структуру графа, чьи вершины и рёбра соответствуют элементам социальной сети и связям между ними, соответственно. «Этот прорыв позволит нам решить многие прикладные задачи, так как многие системы и ситуации могут быть промоделированы с помощью графов», — объясняют исследователи. Разработанный алгоритм может быть применен, например, для нахождения оптимальных маршрутов в системах планирования грузоперевозок, или в компьютерных играх, или для того, чтобы определить степень семантической близости двух слов, или чтобы узнать, сколько общих друзей есть у двух пользователей Фейсбука или Твиттера.
Данная исследовательская работа, получившая поддержку от властей автономного сообщества Мадрида (MA2VICMR, S2009/TIC-1542) и Министерства образования и науки Испании (Ministerio de Educación y Ciencia) началось как часть проекта SOPAT (TSI-020110-2009-419) целью которого было создание системы навигации для постояльцев отелей. Докторская диссертация Джессики Ривьеро, посвященная данной теме, называется «Búsqueda Rápida de Caminos en Grafos de Alta Cardinalidad Estáticos y Dinámicos» («Быстрый поиск пути в больших статических и динамических графах»). Руководителем работы был Франциско Хавьер Калле Долорес Куадра (Francisco Javier Calle Dolores Cuadra), один из профессоров лаборатории LABDA. В феврале 2012 года Джессика успешно защитила свою диссертационную работу.
Оригинал статьи: «A search engine for social networks based on the behavior of ants»
Ссылки
- Страница Джессики Ривьеро на сайте UC3M
- Using the ACO algorithm for path searches in social networks
- Búsqueda Rápida de Caminos en Grafos de Alta Cardinalidad Estáticos y Dinámicos
Автор: pancakes
