|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Алгоритмы выявления аномалий типа «черная дыра» в ориентированном графе при помощи топологического подходастатья
Дата последнего поиска статьи во внешних источниках: 24 июля 2024 г.
- Авторы: Иванов Денис, Семенов Александр
- Журнал: Computational nanotechnology
- Том: 7
- Номер: 2
- Год издания: 2020
- Издательство: Общество с ограниченной ответственностью Издательский дом Юр-ВАК
- Местоположение издательства: Москва
- Первая страница: 49
- Последняя страница: 57
- DOI: 10.33693/2313-223x-2020-7-2-49-57
- Аннотация: В данной работе рассмотрена задача поиска подграфа типа «черная дыра» в ориентированном графе без весов. Постановка задачи рассматривается в той формулировке, которая дана в работе коллектива авторов из университета Нью-Джерси в 2010 г. Данная работа вносит вклад в область выявления в графе подграфов определенного вида, результаты работы могут применяться для выявления аномалий в финансовой области и природных катаклизмов, анализе городских ситуаций. Цель работы - предложить новый алгоритм для поиска «черных дыр», учитывающий структуру данного паттерна и использующий ее для более эффективного перебора возможных вариантов, рассмотреть уже существующие решения на графах гораздо большего размера по сравнению с рассмотренными предыдущими исследователями. В работе рассмотрен предложенный ранее алгоритм и его модификация iBlackholeDC на основе принципа Divide and Conquer, выделены его недостатки. Предложено использовать конденсацию графа для сокращения размера задачи. В ходе работы доказаны теоремы о строении «черных дыр» на графах. Предложен подход к перебору множеств-кандидатов, основанный на доказанных теоремах. Введены правила для сокращения такого перебора. Для сокращения перебора используется топологическая сортировка графа, а также введенное нами понятие «особая вершина». Дано определение особой вершины, доказаны ее свойства. Предложен новый алгоритм TopSortBH, задействующий конденсацию, новый подход к перебору кандидатов и сокращение перебора на основе топологии. Для TopSortBH разработана модификация FastSkip, позволяющая эффективно пропускать большие группы неподходящих кандидатов. Все рассмотренные алгоритмы реализованы, проведено экспериментальное сравнение на системе Polus. Показана эффективность конденсации в качестве предобработки графа для данной задачи. Продемонстрировано преимущество алгоритма TopSortBH и его модификации FastSkip на графах RMAT, SSCA2, Uniform Random с числом вершин до 218 по сравнению с алгоритмом iBlackholeDC.
- Добавил в систему: Семенов Александр Сергеевич