Mining preserving structures in a graph sequence

DOI10.1007/978-3-319-21398-9_1MaRDI QIDQ3196368zbMATH OpenOpenAlexFDO

Authors Takeaki Uno, Yushi Uno

Publication date 29 October 2015

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

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(7)

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

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)