Точный алгоритм вычисления долей бенефициарного владения в ориентированных графах на основе марковских цепей и сильно связных компонент

Аннотация

Задача точного вычисления долей бенефициарного владения в крупномасштабных ориентированных графах с циклами является актуальной проблемой анализа корпоративных сетей. Существующие подходы либо не учитывают циклические структуры владения, либо имеют высокую вычислительную сложность, что делает их неприменимыми к реальным данным. В работе предложен новый алгоритм, сводящий задачу к последовательному вычислению персонализированного PageRank внутри сильно связных компонент графа с последующей агрегацией результатов вдоль ациклической конденсации. Доказана корректность алгоритма и его линейная вычислительная сложность O(m) по числу рёбер на этапе предобработки, что позволяет анализировать графы с десятками миллионов вершин и связей. Экспериментальная валидация проведена на реальных данных: глобальной базе ORBIS (40 млн записей), реестре лиц со значительным контролем Великобритании (PSC, 4 млн) и данных ФНС России (2 млн). Результаты подтверждают высокую точность и масштабируемость метода. Дополнительно исследованы структурные характеристики корпоративных графов (распределение размеров сильно связных компонент, длина цепочек владения), влияющие на производительность алгоритма.