Detecting Blackholes and Volcanoes in Directed Networks - Computer Science > LearningReportar como inadecuado

Detecting Blackholes and Volcanoes in Directed Networks - Computer Science > Learning - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: In this paper, we formulate a novel problem for finding blackhole and volcanopatterns in a large directed graph. Specifically, a blackhole pattern is agroup which is made of a set of nodes in a way such that there are only inlinksto this group from the rest nodes in the graph. In contrast, a volcano patternis a group which only has outlinks to the rest nodes in the graph. Bothpatterns can be observed in real world. For instance, in a trading network, ablackhole pattern may represent a group of traders who are manipulating themarket. In the paper, we first prove that the blackhole mining problem is adual problem of finding volcanoes. Therefore, we focus on finding the blackholepatterns. Along this line, we design two pruning schemes to guide the blackholefinding process. In the first pruning scheme, we strategically prune the searchspace based on a set of pattern-size-independent pruning rules and develop aniBlackhole algorithm. The second pruning scheme follows a divide-and-conquerstrategy to further exploit the pruning results from the first pruning scheme.Indeed, a target directed graphs can be divided into several disconnectedsubgraphs by the first pruning scheme, and thus the blackhole finding can beconducted in each disconnected subgraph rather than in a large graph. Based onthese two pruning schemes, we also develop an iBlackhole-DC algorithm. Finally,experimental results on real-world data show that the iBlackhole-DC algorithmcan be several orders of magnitude faster than the iBlackhole algorithm, whichhas a huge computational advantage over a brute-force method.

Autor: Zhongmou Li, Hui Xiong, Yanchi Liu


Documentos relacionados