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



    Исследователи из Мадридского университета имени Карлоса 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»

    Ссылки

    1. Страница Джессики Ривьеро на сайте UC3M
    2. Using the ACO algorithm for path searches in social networks
    3. Búsqueda Rápida de Caminos en Grafos de Alta Cardinalidad Estáticos y Dinámicos
    4. Муравьиные алгоритмы
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 5

      +2
      Муравьиному алгоритму и его применениям уже оооочень много лет. О чем статья?
        +1
        о его применении для поиска связей в социальных сетях. просто переводили не статью, а попсовую аннотацию на сайте университета.

        собственно, 2 ссылка уже на статью, но она стоит 35 баксов.
        3 ссылка — документы для защиты достаточно подробно, но на испанском.

        по-моему, это отличный пример того, как НЕ стоит оформлять статьи.
          +1
          Ссылку 2 исправил — теперь она ведет на pdf документ.
          +1
          Статья об алгоритме SoSACO, разработанном исследователями из UC3M. Алгоритм SoSACO является модификацией алгоритма ACO. Согласно авторам, их алгоритм более эффективен при работе с большими графами, поэтому одним из логичных приложений данного алгоритма является поиск пути между вершинами графа, описывающего элементы (реально существующих) социальных сетей, что открывает самые разнообразные возможности по применению данного алгоритма. Подробности работы алгоритма даны в статье по ссылке 2. Кстати, спасибо что напомнили, я добавил ссылку на статью Хабра по муравьиным алгоритмам для всех, кто интересуется данной темой.
            +1
            их алгоритм более эффективен при работе с большими графами, поэтому одним из логичных приложений данного алгоритма является поиск пути между вершинами графа, описывающего элементы (реально существующих) социальных сетей

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

            Если есть интересующиеся добровольцы — разберитесь, пожалуйста, как именно он учитывает топологию соцсетей и напишите статью :-) Было бы очень здорово.

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое