Mining blackhole and volcano patterns in directed graphs: A general approach

Zhongmou Li, Hui Xiong, Yanchi Liu

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)577-602
Number of pages26
JournalData Mining and Knowledge Discovery
Volume25
Issue number3
DOIs
StatePublished - Nov 2012

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Computer Networks and Communications

Keywords

  • Blackhole pattern
  • Financial fraud detection
  • Graph mining
  • Network structure analysis
  • Volcano pattern

Fingerprint

Dive into the research topics of 'Mining blackhole and volcano patterns in directed graphs: A general approach'. Together they form a unique fingerprint.

Cite this