approxBlackhole swMATH ID: 6906 Software Authors: Li, Zhongmou; Xiong, Hui; Liu, Yanchi Description: Mining blackhole and volcano patterns in directed graphs: a general approach Given a directed graph, the problem of blackhole mining is to identify groups of nodes, called blackhole patterns, in a way such that the average in-weight of this group is significantly larger than the average out-weight of the same group. The problem of finding volcano patterns is a dual problem of mining blackhole patterns. Therefore, we focus on discovering the blackhole patterns. Indeed, in this article, we develop a generalized blackhole mining framework. Specifically, we first design two pruning schemes for reducing the computational cost by reducing both the number of candidate patterns and the average computation cost for each candidate pattern. The first pruning scheme is to exploit the concept of combination dominance to reduce the exponential growth search space. Based on this pruning approach, we develop the gBlackhole algorithm. Instead, the second pruning scheme is an approximate approach, named approxBlackhole, which can strike a balance between the efficiency and the completeness of blackhole mining. Finally, experimental results on real-world data show that the performance of approxBlackhole can be several orders of magnitude faster than gBlackhole, and both of them have huge computational advantages over the brute-force approach. Also, we show that the blackhole mining algorithm can be used to capture some suspicious financial fraud patterns. Homepage: http://web.njit.edu/~yl473/DMKD12.pdf Keywords: blackhole pattern; volcano pattern; financial fraud detection; graph mining; network structure analysis Related Software: OutRank; OddBall; LOF; gSpan; gBlackhole; LEDA Cited in: 1 Publication Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Mining blackhole and volcano patterns in directed graphs: a general approach. Zbl 1260.91217Li, Zhongmou; Xiong, Hui; Liu, Yanchi 2012 Cited by 3 Authors 1 Li, Zhongmou 1 Liu, Yanchi 1 Xiong, Hui Cited in 1 Serial 1 Data Mining and Knowledge Discovery Cited in 2 Fields 1 Combinatorics (05-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) Citations by Year