Астрофизики восстановили структуру космических сетей по случайным блужданиям
Исследователи представили метод восстановления структуры графов по данным случайных блужданий. Работа, опубликованная на arXiv, предлагает конвейер, который использует матрицу совместных посещений вершин и может применяться для анализа пространственных корреляционных сетей в астрофизике и для определения связности в сетевой науке.
В основе подхода лежит модель парных весов ребер и алгоритм подгонки на основе Левенберга-Марквардта с групповыми весами для узлов и самокалибрующимся порогом для ребер. Авторы отмечают, что матрица совместных посещений сохраняет упорядоченную пару до суммирования по строкам, что позволяет учитывать структуру, недоступную аддитивной модели узловых потенциалов.
Метод был протестирован на нескольких наборах данных: подграфе электронной почты, сетях Делоне и Вороного, построенных из каталога COSMOS, а также на двух контрольных графах с 12 вершинами. Использовались как аналитический шум, так и конечные траектории случайных блужданий.
Результаты показали высокую точность восстановления. Для сетей Делоне и Вороного из COSMOS коэффициент корреляции Мэтьюза (MCC) превысил 0.98 при полном размере графа (119 и 223 вершины соответственно). Для эмпирического графа email-Eu-core с 240 вершинами и 417 ребрами также достигнуто высокое качество восстановления.
Сравнение с эталонным методом графического лассо продемонстрировало значительное преимущество: на полном графе Делоне MCC составил 0.540 для лассо против 0.988 для предложенного подхода. При этом каждое восстановленное ребро сопровождается неопределенностью, распространенной методом Фишера.
Авторы подчеркивают, что ошибки восстановления почти полностью сосредоточены на ребрах, которые случайное блуждание вообще не посещало. Таким образом, в режиме конечной траектории ограничением является не оценка, а покрытие графа обходом: практически каждое посещенное ребро восстанавливается.
Разработка может быть полезна для анализа крупных пространственных сетей в астрофизике, где прямое наблюдение всех связей затруднено, а также для задач вывода связности в сложных системах.
