Computational nanotechnology Выпуск №2 — 2020

Алгоритмы выявления аномалий типа «черная дыра» в ориентированном графе при помощи топологического подхода
(Стр. 49-57)

Иванов Денис Евгеньевич Семенов Александр Сергеевич

DOI: 10.33693/2313-223X-2020-7-2-49-57

Иванов Денис Евгеньевич магистр
Московский Государственный Университет имени М.В. Ломоносова Семенов Александр Сергеевич кандидат технических наук; начальник отдела, доцент; ведущий научный сотрудник
Московский Государственный Университет имени М.В. Ломоносова; Научно-исследовательский центр электронной вычислительной техники (АО «НИЦЭВТ»); Высшая школа экономики

Оплатить 390 руб. (Картой) Оплатить 390 руб. (Через QR-код)

Нажимая на кнопку купить вы соглашаетесь с условиями договора оферты

Аннотация:

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

Образец цитирования:

Иванов Д.Е., Семенов А.С., (2020), АЛГОРИТМЫ ВЫЯВЛЕНИЯ АНОМАЛИЙ ТИПА «ЧЕРНАЯ ДЫРА» В ОРИЕНТИРОВАННОМ ГРАФЕ ПРИ ПОМОЩИ ТОПОЛОГИЧЕСКОГО ПОДХОДА. Computational nanotechnology, 2 => 49-57.

Список литературы:

Bader D.A., Madduri K. Design and implementation of the hpcs graph analysis benchmark on symmetric multiprocessors. International Conference on High Performance Computing. Springer, 2005. Рp. 465-476.
Chakrabarti D., Zhan Y., Faloutsos C. R-mat: A recursive model for graph mining. Proceedings of the 2004 SIAM International Conference on Data Mining. SIAM, 2004. Рp. 442-446.
Erdoos P., Reyni A. On random graphs. Publicationes Mathematicae. 1959. No. 6. Pp. 290-297.
Fortunato S. Community detection in graphs. Physics Reports. 2010. No. 486 (3-5). Pp. 75-174.
Hong L., Zheng Y., Yung D. et al. Detecting urban black holes based on human mobility data. Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2015. P. 35.
Li Z., Xiong H. Mining blackhole and volcano patterns for fraud detection. In: Encyclopedia of Social Network Analysis and Mining. 2014. Pp. 904-915.
Li Z., Xiong H., Liu Y. Mining blackhole and volcano patterns in directed graphs: A general approach. Data Mining and Knowledge Discovery. 2012. No. 25 (3). Pp. 577-602.
Li Z., Xiong H., Liu Y., Zhou A. Detecting blackhole and volcano patterns in directed networks. 2010 IEEE International Conference on Data Mining. 2010. Pp. 294-303.
Semenov A., Mazeev A., Doropheev D. et al. Survey of common design approaches in aml software development. GraphHPC 2017 Conference (GraphHPC). CEUR Workshop Proceedings. 2017. Vol. 1981. Pp. 1-9.
Sharir M. A strong-connectivity algorithm and its applications in data flow analysis. Computers & Mathematics with Applications. 1981. No. 7 (1). Pp. 67-72.
Watts D.J. Networks, dynamics, and the small-world phenomenon. American Journal of sociology. 1999. No. 105 (2). Pp. 493-527.

Ключевые слова:

ориентированный граф, поиска подграфов в графе, подграф «черная дыра».