|
Title
|
|
|
|
Efficient and accurate non-exhaustive pattern-based change detection in dynamic networks
| |
|
Author
|
|
|
|
| |
|
Abstract
|
|
|
|
| Pattern-based change detectors (PBCDs) are non-parametric unsupervised change detection methods that are based on observed changes in sets of frequent patterns over time. In this paper we study PBCDs for dynamic networks; that is, graphs that change over time, represented as a stream of snapshots. Accurate PBCDs rely on exhaustively mining sets of patterns on which a change detection step is performed. Exhaustive mining, however, has worst case exponential time complexity, rendering this class of algorithms inefficient in practice. Therefore, in this paper we propose non-exhaustive PBCDs for dynamic networks. The algorithm we propose prunes the search space following a beam-search approach. The results obtained on real-world and synthetic dynamic networks, show that this approach is surprisingly effective in both increasing the efficiency of the mining step as in achieving higher detection accuracy, compared with state-of-the-art approaches. |
| |
|
Language
|
|
|
|
English
| |
|
Source (journal)
|
|
|
|
Lecture notes in computer science. - Berlin, 1973, currens
| |
|
Source (book)
|
|
|
|
Discovery science : 22nd International Conference, DS 2019, Split, Croatia, October 28–30, 2019, Proceedings
| |
|
Source (series)
|
|
|
|
Lecture notes in artificial intelligence (LNAI); 11828
| |
|
Publication
|
|
|
|
Cham
:
Springer
,
2019
| |
|
ISBN
|
|
|
|
978-3-030-33777-3
| |
|
DOI
|
|
|
|
10.1007/978-3-030-33778-0_30
| |
|
Volume/pages
|
|
|
|
p. 396-411
| |
|
Note
|
|
|
|
22nd International Conference, DS 2019, Split, Croatia, October 28–30, 2019
| |
|
Full text (Publisher's DOI)
|
|
|
|
| |
|
Full text (open access)
|
|
|
|
| |
|