|
Title
|
|
|
|
2SCENT : an efficient algorithm to enumerate all simple temporal cycles
| |
|
Author
|
|
|
|
| |
|
Abstract
|
|
|
|
| n interaction networks nodes may interact continuously and repeatedly. Not only which nodes interact is important, but also the order in which interactions take place and the patterns they form. These patterns cannot be captured by solely inspecting the static network of who interacted with whom and how frequently, but also the temporal nature of the network needs to be taken into account. In this paper we focus on one such fundamental interaction pattern, namely a temporal cycle. Temporal cycles have many applications and appear naturally in communication networks. In finan- cial networks, on the other hand, the presence of a temporal cycle could be indicative for certain types of fraud, and in biological networks, feedback loops are a prime example of this pattern type. We present 2SCENT, an efficient algo- rithms to find all temporal cycles in a directed interaction network. 2SCENT consist of a non-trivial temporal exten- sion of a seminal algorithm for finding cycles in static graphs, preceded by an efficient candidate root filtering technique which can be based on Bloom filters to reduce the memory footprint. We tested 2SCENT on six real-world data sets, showing that it is up to 300 times faster than the only ex- isting competitor and scales up to networks with millions of nodes and hundreds of millions of interactions. Results of a qualitative experiment indicate that different interaction networks may have vastly different distributions of temporal cycles, and hence temporal cycles are able to characterize an important aspect of the dynamic behavior in the networks. |
| |
|
Language
|
|
|
|
English
| |
|
Source (journal)
|
|
|
|
Proceedings of the VLDB Endowment
| |
|
Publication
|
|
|
|
2018
| |
|
ISSN
|
|
|
|
2150-8097
| |
|
Volume/pages
|
|
|
|
11
:11
(2018)
, p. 1441-1453
| |
|
ISI
|
|
|
|
000452537300011
| |
|
Full text (Publisher's DOI)
|
|
|
|
| |
|
Full text (open access)
|
|
|
|
| |
|