Network data streams are unbounded sequences of complex data produced at high rate which represent complex systems that evolve continuously over time. In this scenario, a problem worthy of being studied is the analysis of the changes, which may concern a complex system as a whole or small parts of it. In this paper, these are distinguished into macroscopic changes and microscopic changes: macroscopic changes have impact on a substantial part of the network, whereas microscopic changes concern variations occurring in specific portions of the network. The algorithm we propose, called KARMA, combines the frequent pattern mining framework with an automatic time-window detection approach. In this way, it is able to detect changes on the frequent subnetworks mined from different time-windows: network changes are then represented as variations of structural regularities frequently observed over the stream. KARMA takes an holistic perspective, in which the two kinds of change are related each other. This is the main novelty with respect to the recent studies, which do not simultaneously extract microscopic and macroscopic changes. Experiments on several real-world network data streams show the effectiveness and efficiency of our approach in comparison with competing algorithms and the usefulness of the changes detected.

Mining microscopic and macroscopic changes in network data streams

Loglisci, Corrado
;
Ceci, Michelangelo;Impedovo, Angelo;Malerba, Donato
2018

Abstract

Network data streams are unbounded sequences of complex data produced at high rate which represent complex systems that evolve continuously over time. In this scenario, a problem worthy of being studied is the analysis of the changes, which may concern a complex system as a whole or small parts of it. In this paper, these are distinguished into macroscopic changes and microscopic changes: macroscopic changes have impact on a substantial part of the network, whereas microscopic changes concern variations occurring in specific portions of the network. The algorithm we propose, called KARMA, combines the frequent pattern mining framework with an automatic time-window detection approach. In this way, it is able to detect changes on the frequent subnetworks mined from different time-windows: network changes are then represented as variations of structural regularities frequently observed over the stream. KARMA takes an holistic perspective, in which the two kinds of change are related each other. This is the main novelty with respect to the recent studies, which do not simultaneously extract microscopic and macroscopic changes. Experiments on several real-world network data streams show the effectiveness and efficiency of our approach in comparison with competing algorithms and the usefulness of the changes detected.
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0950705118303459-main.pdf

non disponibili

Tipologia: Documento in Versione Editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 4.08 MB
Formato Adobe PDF
4.08 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
preprint_KBS.pdf

accesso aperto

Descrizione: Documento in Pre-print
Tipologia: Documento in Pre-print
Licenza: Creative commons
Dimensione 1.56 MB
Formato Adobe PDF
1.56 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11586/225812
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 6
social impact