• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

Алгоритмы выявления аномалий типа «черная дыра» в ориентированном графе при помощи топологического подхода

Computational nanotechnology. 2020. № 2. С. 49-57.
Семенов А. С., Иванов Д. Е.

В данной работе рассмотрена задача поиска подграфа типа «черная дыра» в ориентированном графе без весов. Постановка задачи рассматривается в той формулировке, которая дана в работе коллектива авторов из университета Нью-Джерси в 2010 г. Данная работа вносит вклад в область выявления в графе подграфов определенного вида, результаты работы могут применяться для выявления аномалий в финансовой области и природных катаклизмов, анализе городских ситуаций. Цель работы – предложить новый алгоритм для поиска «черных дыр», учитывающий структуру данного паттерна и использующий ее для более эффективного перебора возможных вариантов, рассмотреть уже существующие решения на графах гораздо большего размера по сравнению с рассмотренными предыдущими исследователями. В работе рассмотрен предложенный ранее алгоритм и его модификация iBlackholeDC на основе принципа Divide and Conquer, выделены его недостатки. Предложено использовать конденсацию графа для сокращения размера задачи. В ходе работы доказаны теоремы о строении «черных дыр» на графах. Предложен подход к перебору множеств-кандидатов, основанный на доказанных теоремах. Введены правила для сокращения такого перебора. Для сокращения перебора используется топологическая сортировка графа, а также введенное нами понятие «особая вершина». Дано определение особой вершины, доказаны ее свойства. Предложен новый алгоритм TopSortBH, задействующий конденсацию, новый подход к перебору кандидатов и сокращение перебора на основе топологии. Для TopSortBH разработана модификация FastSkip, позволяющая эффективно пропускать большие группы неподходящих кандидатов. Все рассмотренные алгоритмы реализованы, проведено экспериментальное сравнение на системе Polus. Показана эффективность конденсации в качестве предобработки графа для данной задачи. Продемонстрировано преимущество алгоритма TopSortBH и его модификации FastSkip на графах RMAT, SSCA2, Uniform Random с числом вершин до 2^18 по сравнению с алгоритмом iBlackholeDC.