Должность: научный сотрудник

Учёная степень: кандидат физико-математических наук (диссертация)

Email: korshunov@ispras.ru

Научные интересы:

• интеллектуальный анализ данных пользователей социальных сетей (веб-демо)
• кластерный анализ сложных сетей
• теория графов
• модели случайных графов
• модели влияния и распространения информации
• машинное обучение
• базы знаний на основе открытых электронных энциклопедий
• распределённое хранение и обработка данных

Участие в проектах:

• «Scalable graph community detection algorithms based on Apache Spark»
• «Разработка системы поиска и анализа мнений пользователей сети Интернет»
• «Построение социо-демографического профиля пользователей сети Интернет» (закончен)
• «Scalable Social Graph Processing System» (закончен)

Основные публикации: профиль на Google Scholar

ТЕМЫ РАБОТ ДЛЯ СТУДЕНТОВ

«Моделирование распространения информации среди Интернет-ресурсов с помощью сетей диффузии»

«Modeling information dissemination among Internet resources via diffusion networks»

В сети диффузии вершинами могут служить как отдельные пользователи и их сообщения, так и целые ресурсы и их разделы. На вход поступают следующие данные: идентификаторы+названия вершин и каскады распространения. Каждый каскад — это множество пар «вершина,временная метка». Например, может быть каскад распространения какого-либо термина, URL, хештега. Интерес представляют алгоритмы, позволяющие строить рёбра между вершинами подобной сети, принимая на вход информацию о каскадах распространения информации (например: NetInf, NetRate, InfoPath).

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

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

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

Задачи:

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

Литература: «Inferring Networks of Diffusion and Influence», «Feature-Enhanced Probabilistic Models for Diffusion Network Inference», «Back to the Past: Source Identification in Diffusion Networks from Partially Observed Cascades», «BAYESIAN INFERENCE OF DIFFUSION NETWORKS WITH UNKNOWN INFECTION TIMES».

«Поиск подграфов социального графа, включающих заданное множество пользователей»

«Searching for connection subgraphs comprising the query set of users»

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

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

Задачи:

• исследовать современные методы поиска подграфов, включающих заданное множество пользователей
• разработать и реализовать метод поиска подграфов, включающих заданное множество пользователей
• провести экспериментальное исследование реализованного метода и сравнение с базовыми методами

Литература: «Center-Piece Subgraphs: Problem Definition and Fast Solutions», «Connection Subgraphs: A Survey», «Crawling and Detecting Community Structure in Online Social Networks using Local Information», «The Minimum Wiener Connector», «Bump hunting in the dark: Local discrepancy maximization on graphs», «Mining Connection Pathways for Marked Nodes in Large Graphs».

«Определение структуры пересекающихся сообществ графа путём пост-обработки непересекающихся сообществ»

«Overlapping community detection via post-processing disjoint communities»

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

Задачи:

• исследовать современные методы преобразования непересекающихся сообществ в пересекающиеся для заданного графа
• разработать и реализовать метод преобразования непересекающихся сообществ в пересекающиеся
• провести экспериментальное исследование реализованного метода и сравнение с базовыми методами

Литература: «Leveraging disjoint communities for detecting overlapping community structure», «Overlapping community detection in complex networks based on the boundary information of disjoint community», «Adjusting from disjoint to overlapping community detection of complex networks», «Overlapping Community Detection in Social Network Using Disjoint Community Detection», «Finding Overlapping Communities Using Disjoint Community Detection Algorithms».

«Определение пользовательских ролей в онлайн-сообществах»

«Determining user roles in online communities»

Пользовательская роль соответствует определённому шаблону поведения пользователя по отношению к другим пользователям сети. Примерами ролей могут служить «эксперт», «лидер мнений», «распространитель информации», «читатель».

Задачи:

• исследовать современные подходы к автоматическому определению пользовательских ролей на основе анализа связей между пользователями, генерируемого контента и данных о взаимодействиях пользователей друг с другом
• разработать и реализовать метод определения заданного набора ролей для LiveJournal, Twitter, Facebook, vKontakte и новостных сайтов
• провести экспериментальное исследование реализованного метода и сравнение с базовыми методами
• исследовать современные подходы к кластеризации пользователей по поведению с целью автоматического определения неизвестного набора ролей

Литература: «Roles in social networks: methodologies and research issues», «A Conceptual and Operational Definition of ‘Social Role’ in Online Community», «Inferring Social Roles and Statuses in Social Networks».

«Таргетированный сбор данных пользователей социальных сетей»

«Targeted crawling of social network users data»

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

Задачи:

• исследовать современные подходы к таргетированному сбору данных пользователей
• разработать и реализовать метод сбора данных пользователей с заданным набором параметров
• провести экспериментальное исследование реализованного метода и сравнение с базовыми методами

Литература: «Bandit Algorithms for Social Network Queries», «Finding seeds to bootstrap focused crawlers».