Computational nanotechnology
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Comp. nanotechnol.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Computational nanotechnology, 2020, том 7, выпуск 2, страницы 49–57
DOI: https://doi.org/10.33693/2313-223X-2020-7-2-49-57
(Mi cn299)
 

РАЗРАБОТКА АРХИТЕКТУРЫ КВАНТОВЫХ КОМПЬЮТЕРОВ НА НОВЫХ ПРИНЦИПАХ, СОЗДАНИЕ НОВОГО КВАНТОВОГО ПРОГРАММИРОВАНИЯ

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

Д. Е. Иванов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
Цитирование в формате AMSBIB
\RBibitem{IvaSem20}
\by Д.~Е.~Иванов, А.~С.~Семенов
\paper Алгоритмы выявления аномалий типа <<черная дыра>> в ориентированном графе при помощи топологического подхода
\jour Comp. nanotechnol.
\yr 2020
\vol 7
\issue 2
\pages 49--57
\mathnet{http://mi.mathnet.ru/cn299}
\crossref{https://doi.org/10.33693/2313-223X-2020-7-2-49-57}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/cn299
  • https://www.mathnet.ru/rus/cn/v7/i2/p49
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Computational nanotechnology
    Статистика просмотров:
    Страница аннотации:152
    PDF полного текста:51
    Список литературы:1
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024