Проверка гипотез для случайных графов со структурой сообществ

Графы — достаточно значимые математические объекты. Они возникают естественным образом во многих задачах: анализ социальных сетей, анализ цитирований, анализ белковых взаимодействий, а так же анализ коннектомов головного мозга. Анализ случайных графов является активным направлением для исследований: ведутся работы по задаче детектирования сообществ, в теории пределов, по определению количества сообществ в графе, а так же по определению модели графа. Значительная часть задач может быть сформулирована в смысле тестирования гипотез для одного графа. Однако, задаче проверки гипотез в задачах тестирования для двух и более графов посвящено не так много работ, и такие задачи до сих пор достаточно мало изучены. Мы фокусируемся на задаче тестирования для двух графов, определенных на одном наборе вершин и имеющих структуру низкого ранга, которая так же включает в себя графы со структурой сообществ. Мы хотим ответить на вопрос: имеют ли данные графы одинаковое распределение. В этой работе мы представляем два похода, основанных на бутстреп-методе, которые работают с общей низкорановой структурой графов, а так же асимптотический тест, работающий со стохастической блочной моделью. Теоретическое обоснование последнего теста приведено в работе. Качество процедур тестирования представлено в ряде экспериментов как на синтетически сгенерированных данных, так и на реальных. В экспериментах с ЭЭГ и коннектомами головного мозга мы получили результаты, которые более надежны, чем результаты существующих решений подобных задач. Более того, результаты на данных головного мозга сравнимы с результатами, получаемыми методами машинного обучения.