Abstract: В данной работе предлагается новый метод для выделения сообществ в графах. Основные преимущества метода --- отсутствие необходимости задавать искомое число кластеров и возможность теоретического анализа. Разработка алгоритма ведется в рамках распространенной модели генерации случайных графов с кластерной структурой --- stochastic block model. Кластеры описываются в терминах матрицы весов. Алгоритм итеративный: на каждой итерации матрица весов пересчитывается в соответствии с некоторым правилом. При этом правило строится с помощью некоторой тестовой статистики, основанной на частотах ребер внутри и между текущими кластерами. Приводится детальное описание алгоритма с псевдокодом. Обсуждаются некоторые теоретические свойства тестовой статистики, в частности, теорема Вилкса. В конце проводится экспериментальное исследование на модельных и реальных данных, результаты работы сравниваются с классическими алгоритмами выделения сообществ.

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

Abstract: В данной работе рассмотрена задача выделения сообществ — групп вершин в графе, плотно связанных между собой, но не с остальной частью графа. Известно множество подходов для выделения непересекающихся сообществ. Гораздо меньше внимания уделено случаю пересекающихся групп. В работе предложен новый метод решения задачи на взвешенных графах с пересекающимися группами вершин. Метод является обобщением алгоритма BigClam. В конце работы приведены эксперименты. Сравнение с другими методами решения задачи показали, что предложенные в статье алгоритмы работают на уровне современных аналогов, но не лучше их. Особое внимание уделено методам инициализации BigClam, предложено несколько улучшений, которые ускоряет алгоритм и позволяет сойтись к лучшему значению функции.

Abstract: Решается задача различения пациентов с расстройствами аутистического спектра и людей без патологии на основе графов структурных связей головного мозга (коннектомов). Для этого мы предлагаем использовать возможные различия в разбиениях графов на подграфы, характерные для коннектомов групп нормы и патологии. Мы используем четыре метода кластеризации, чтобы получить разбиения коннектомов на подграфы. Мы оцениваем попарные расстояния между полученными разбиениями и строим на их основе ядро для SVM классификатора. Полученные классификаторы мы объединяем в двухуровневую модель с использованием стэкинга. Качество классификации для двухуровневой модели достигает 0.73 в смысле площади под ROC-кривой (ROC AUC).

Abstract: In this work, graph spectra of the normalized graph Laplacians of brain networks (connectomes) are used for solving the task of classifying autism spectrum disorder against typical development. We find the most informative group of eigenvalues by introducing a window and sliding it through all possible positions. We next assume that these values are sampled from a Dirichlet distribution and build a linear model with a single feature that is based on estimation of a Dirichlet parameter. The proposed classifier outperforms the baseline in terms of both mean ROC AUC value (0.74) and stability of ROC AUC values to the variations in the data. Classifiers that implemented a similar approach but used geometric distances instead of statistical methods showed worse performance. This implies that the Dirichlet distribution might be a useful tool for the analysis of normalized Laplacian spectra when solving tasks of classifying brain networks.