|
РАЗРАБОТКА АРХИТЕКТУРЫ КВАНТОВЫХ КОМПЬЮТЕРОВ НА НОВЫХ ПРИНЦИПАХ, СОЗДАНИЕ НОВОГО КВАНТОВОГО ПРОГРАММИРОВАНИЯ
Алгоритмы выявления аномалий типа «черная дыра» в ориентированном графе при помощи топологического подхода
Д. Е. Ивановa, А. С. Семеновbac a Московский Государственный Университет имени М.В. Ломоносова
b Научно-исследовательский центр электронной вычислительной техники, г. Москва
c Государственный университет – Высшая школа экономики
Аннотация:
В данной работе рассмотрена задача поиска подграфа типа «черная дыра» в ориентированном графе без весов. Постановка задачи рассматривается в той формулировке, которая дана в работе коллектива авторов из университета Нью-Джерси в 2010 г. Данная работа вносит вклад в область выявления в графе подграфов определенного вида, результаты работы могут применяться для выявления аномалий в финансовой области и природных катаклизмов, анализе городских ситуаций. Цель работы - предложить новый алгоритм для поиска «черных дыр», учитывающий структуру данного паттерна и использующий ее для более эффективного перебора возможных вариантов, рассмотреть уже существующие решения на графах гораздо большего размера по сравнению с рассмотренными предыдущими исследователями. В работе рассмотрен предложенный ранее алгоритм и его модификация iBlackholeDC на основе принципа Divide and Conquer, выделены его недостатки. Предложено использовать конденсацию графа для сокращения размера задачи. В ходе работы доказаны теоремы о строении «черных дыр» на графах. Предложен подход к перебору множеств-кандидатов, основанный на доказанных теоремах. Введены правила для сокращения такого перебора. Для сокращения перебора используется топологическая сортировка графа, а также введенное нами понятие «особая вершина». Дано определение особой вершины, доказаны ее свойства. Предложен новый алгоритм TopSortBH, задействующий конденсацию, новый подход к перебору кандидатов и сокращение перебора на основе топологии. Для TopSortBH разработана модификация FastSkip, позволяющая эффективно пропускать большие группы неподходящих кандидатов. Все рассмотренные алгоритмы реализованы, проведено экспериментальное сравнение на системе Polus. Показана эффективность конденсации в качестве предобработки графа для данной задачи. Продемонстрировано преимущество алгоритма TopSortBH и его модификации FastSkip на графах RMAT, SSCA2, Uniform Random с числом вершин до 2$^{18}$ по сравнению с алгоритмом iBlackholeDC.
Ключевые слова:
ориентированный граф, поиска подграфов в графе, подграф «черная дыра».
Поступила в редакцию: 07.05.2020
Образец цитирования:
Д. Е. Иванов, А. С. Семенов, “Алгоритмы выявления аномалий типа «черная дыра» в ориентированном графе при помощи топологического подхода”, Comp. nanotechnol., 7:2 (2020), 49–57
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/cn299 https://www.mathnet.ru/rus/cn/v7/i2/p49
|
Статистика просмотров: |
Страница аннотации: | 138 | PDF полного текста: | 51 | Список литературы: | 1 |
|