Mining preserving structures in a graph sequence

DOI10.1007/978-3-319-21398-9_1zbMATH Open1465.68218arXiv1206.6202OpenAlexW2767824101MaRDI QIDQ3196368FDOQ3196368

Authors: Takeaki Uno, Yushi Uno 

Publication date: 29 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: In the recent research of data mining, frequent structures in a sequence of graphs have been studied intensively, and one of the main concern is changing structures along a sequence of graphs that can capture dynamic properties of data. On the contrary, we newly focus on "preserving structures" in a graph sequence that satisfy a given property for a certain period, and mining such structures is studied. As for an onset, we bring up two structures, a connected vertex subset and a clique that exist for a certain period. We consider the problem of enumerating these structures. and present polynomial delay algorithms for the problems. Their running time may depend on the size of the representation, however, if each edge has at most one time interval in the representation, the running time is O(|V||E|^3) for connected vertex subsets and O(min{Delta^5, |E|^2Delta}) for cliques, where the input graph is G = (V,E) with maximum degree Delta. To the best of our knowledge, this is the first approach to the treatment of this notion, namely, preserving structures.

Full work available at URL: https://arxiv.org/abs/1206.6202

Recommendations

• Mining preserving structures in a graph sequence
• Efficient algorithms for the periodic subgraphs mining problem
• Mining evolving patterns of connection subgraphs over evolving graphs
• Speedup for a periodic subgraph miner
• Mining constrained cross-graph cliques in dynamic networks

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Cited In (7)

• Walk-preserving transformation of overlapped sequence graphs into blunt sequence graphs with GetBlunted
• Mining constrained cross-graph cliques in dynamic networks
• Mining preserving structures in a graph sequence
• Speedup for a periodic subgraph miner
• Mining evolving patterns of connection subgraphs over evolving graphs
• Efficient algorithms for the periodic subgraphs mining problem
• Learning block-preserving graph patterns and its application to data mining

This page was built for publication: Mining preserving structures in a graph sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3196368)