Publication
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
DOI
10.14778/3236187.3236197
Volume/pages
11 :11 (2018) , p. 1441-1453
ISI
000452537300011
Full text (Publisher's DOI)
Full text (open access)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
Affiliation
Publications with a UAntwerp address
External links
Web of Science
Record
Identifier
Creation 01.08.2018
Last edited 04.03.2024
To cite this reference