The periodic subgraph mining problem consists in discovering maximal subgraphs that recur at regular intervals in G. For a periodic subgraph to be maximal, it is intended here that it cannot be enriched by adding edges nor can its temporal span be expanded in any direction. We give algorithms that improve the theoretical complexity of solutions previously available for this problem. In particular, we show an optimal solution based on an implicit description of the output subgraphs that takes time —where is the average number of edges over the entire sequence G—to publish all maximal periodic subgraphs that meet or exceed a minimum occurrence threshold σ.

Efficient algorithms for the periodic subgraphs mining problem

Liptak, Zsuzsanna;
2012-01-01

Abstract

The periodic subgraph mining problem consists in discovering maximal subgraphs that recur at regular intervals in G. For a periodic subgraph to be maximal, it is intended here that it cannot be enriched by adding edges nor can its temporal span be expanded in any direction. We give algorithms that improve the theoretical complexity of solutions previously available for this problem. In particular, we show an optimal solution based on an implicit description of the output subgraphs that takes time —where is the average number of edges over the entire sequence G—to publish all maximal periodic subgraphs that meet or exceed a minimum occurrence threshold σ.
2012
Discovery algorithms, Sequences of networks, Social networks, Periodicity, Interactions
File in questo prodotto:
File Dimensione Formato  
ApostolicoEGyLP_JDA2012.pdf

solo utenti autorizzati

Tipologia: Versione dell'editore
Licenza: Copyright dell'editore
Dimensione 180.26 kB
Formato Adobe PDF
180.26 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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: https://hdl.handle.net/11562/469150
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact