Paper Info
Title
Mining preserving structures in a graph sequence.
Abstract
In the recent research of data mining, frequent structures in a sequence of graphs have been studied intensively, and one of the main concerns 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⁡{Δ5,|E|2Δ}) for cliques, where the input graph is G=(V,E) with maximum degree Δ. To the best of our knowledge, this is the first approach to the treatment of this notion, namely, preserving structures.
Year
DOI
Venue
2012
10.1016/j.tcs.2015.12.007
Theoretical Computer Science
Keywords
Field
DocType
Data mining,Enumeration,Graph sequence,Polynomial delay,Preserving structure,Structure mining,Trajectory mining
Discrete mathematics,Graph,Structure mining,Combinatorics,Vertex (geometry),Clique,Polynomial,Enumeration,Timestamp,Degree (graph theory),Mathematics
Journal
Volume
ISSN
Citations 
654
0304-3975
5
PageRank 
References 
Authors
0.42
20
2
Name
Order
Citations
PageRank
Takeaki Uno11319107.99
yushi uno222228.80