Detecting Blackholes and Volcanoes in Directed Networks

Zhongmou Li, Hui Xiong, Yanchi Liu

Introduction

In large-scale directed networks, such as financial transaction systems, detecting collaborative fraud is a significant challenge. Financial "trading rings" often involve groups of accounts that trade exclusively among themselves to manipulate stock prices. While these transactions might appear normal in isolation, they form distinct structural anomalies at the network level. This research introduces two novel graph patterns—blackholes and volcanoes—to identify such coordinated behavior.

A blackhole is defined as a group of nodes where all external connections are incoming; money or information flows in but does not flow out. Conversely, a volcano is its mathematical dual: a group where all external connections are outgoing. Detecting these structures is a combinatorial challenge; as the number of nodes increases, the search space for potential groups grows exponentially, making brute-force search impossible for real-world datasets.

Visual representation of blackholes within a directed network.

Methodology

To address the computational complexity, the researchers developed the iBlackhole-DC algorithm, which utilizes sophisticated pruning and divide-and-conquer strategies.

Duality and Node Closure

The researchers first established the Duality Theorem, proving that finding a blackhole in a graph is identical to finding a volcano in the same graph with all its edges reversed. This allows algorithmic efforts to focus solely on blackholes. Additionally, the algorithm leverages the concept of Node Closure: the set of all nodes reachable from a specific node $v$ is, by definition, a blackhole. This mathematical shortcut allows the algorithm to identify certain patterns instantly without exhaustive searching.

The iBlackhole Algorithm

The core iBlackhole algorithm employs "pattern-size-independent" pruning rules. For example, when searching for a blackhole of size $n$, any node with an out-degree greater than $n-1$ can be immediately discarded. This triggers a cascading delete—if a node is pruned, its predecessors might no longer be able to form a blackhole and are pruned in a chain reaction.

The iBlackhole algorithm pseudocode for finding n-node blackhole patterns.

Divide and Conquer (iBlackhole-DC)

The "DC" version of the algorithm introduces a divide-and-conquer strategy. After initial pruning, the remaining graph often shatters into many small, disconnected components. By treating these fragments as independent problems, the algorithm drastically reduces the search space, turning a global exponential problem into several much smaller local ones.

Experimental Results

The authors evaluated their algorithms on four diverse real-world datasets: Wiki (hyperlinks), Amazon (product co-purchases), Roget (word associations), and a custom Stock network (lagged price correlations).

  • Massive Speedups: In tests on the Wiki and Amazon datasets, the iBlackhole-DC algorithm was several orders of magnitude faster than the standard iBlackhole algorithm.
  • Scalability: While brute-force methods failed as soon as the group size ($n$) reached 4 or 5, iBlackhole-DC could identify patterns of size 10 and beyond in seconds.
  • Real-World Utility: In the Stock dataset, the algorithm identified a blackhole involving Owens Corning and Westmoreland Coal Company. It revealed that the coal company's price movements lagged behind the building material producer—a structural relationship reflecting the industry's shift toward recycling coal byproducts into building materials.

Conclusion and Future Work

This study provides a robust framework for identifying coordinated structures in directed graphs. While the current model focuses on a simplified version where edge weights are ignored and the out-degree must be exactly zero, future research will explore "temporal blackholes" in dynamic networks and incorporate edge weight thresholds to capture more nuanced fraud patterns.

Summary updated

Abstract

In this paper, we formulate a novel problem for finding blackhole and volcano patterns in a large directed graph. Specifically, a blackhole pattern is a group which is made of a set of nodes in a way such that there are only inlinks to this group from the rest nodes in the graph. In contrast, a volcano pattern is a group which only has outlinks to the rest nodes in the graph. Both patterns can be observed in real world. For instance, in a trading network, a blackhole pattern may represent a group of traders who are manipulating the market. In the paper, we first prove that the blackhole mining problem is a dual problem of finding volcanoes. Therefore, we focus on finding the blackhole patterns. Along this line, we design two pruning schemes to guide the blackhole finding process. In the first pruning scheme, we strategically prune the search space based on a set of pattern-size-independent pruning rules and develop an iBlackhole algorithm. The second pruning scheme follows a divide-and-conquer strategy to further exploit the pruning results from the first pruning scheme. Indeed, a target directed graphs can be divided into several disconnected subgraphs by the first pruning scheme, and thus the blackhole finding can be conducted in each disconnected subgraph rather than in a large graph. Based on these two pruning schemes, we also develop an iBlackhole-DC algorithm. Finally, experimental results on real-world data show that the iBlackhole-DC algorithm can be several orders of magnitude faster than the iBlackhole algorithm, which has a huge computational advantage over a brute-force method.
BibTeX
@misc{li2010detecting,
  author = {Zhongmou Li and Hui Xiong and Yanchi Liu},
  title = {{Detecting Blackholes and Volcanoes in Directed Networks}},
  year = {2010},
  eprint = {1005.2179},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1005.2179},
}
Figure