Mining preserving structures in a graph sequence

详细信息    查看全文

• 作者：Takeaki Uno^a ; ^uno@nii.jp ; Yushi Uno^b ; ^{uno@mi.s.osakafu-u.ac.jp}
• 关键词：Data mining ; Enumeration ; Graph sequence ; Polynomial delay ; Preserving structure ; Structure mining ; Trajectory mining
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：22 November 2016
• 年：2016
• 卷：654
• 期：Complete
• 页码：155-163
• 全文大小：349 K
• 卷排序：654

文摘

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)O(|V||E|3) for connected vertex subsets and O(min⁡{Δ5,|E|2Δ})O(min⁡{Δ5,|E|2Δ}) for cliques, where the input graph is G=(V,E)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.