Topological approach to blackholes anomaly detection in directed networks
( Pp. 49-57)

In this paper we consider the problem of finding a blackhole pattern in directed unweighted graphs. The problem statement is the same as in an original paper by scientists from University of New-Jersey published in 2010. The paper contributes to the special graph pattern matching, the work results can be used for anomaly detection in finances, natural disasters, urban analysis. This paper aims to propose a novel algorithm for blackhole mining, which would take into account inner structure of the “blackhole” pattern and utilize this knowledge for more efficient mining. This paper reviews previously published solutions and tests them on larger graphs containing up to 1 million of nodes. In particular, an iBlackhole algorithm and its Divide and Conquer modification iBlackholeDC are considered, their weak spots are highlighted and reviewed upon. Graph condensation is introduced as an efficient preprocessing for the problem. This paper provides theorems and definitions describing inner structure of the blackhole pattern. Based on the new theorems, a new approach to enumeration of candidates is introduced as well as rules and heuristics aiming for faster filtration of candidates: they utilize topological sorting of a graph and definition of a “special” node, which is also introduced in this paper. Special nodes properties are described. We propose a novel TopSortBH algorithm. It consists of the graph condensation, candidates enumeration and heuristics for candidates filtration. The algorithm is provided with modification called FastSkip, which allows for more aggressive filtering strategy in time-sensitive cases. All mentioned algorithms are implemented and tested on the IBM Power8 based system. Experimental results show efficiency of the condensation as graph preprocessing for the problem. Strong advantage in found blackholes count is demonstrated for TopSortBH in comparison to iBlackholeDC on RMAT, SSCA2 and UR graphs containing up to 1 million nodes.

Ivanov D.E., Semenov A.S., (2020), TOPOLOGICAL APPROACH TO BLACKHOLES ANOMALY DETECTION IN DIRECTED NETWORKS. 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. Rp. 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. Rp. 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.

directed networks, subgraph mining, blackhole pattern.