Mining preserving structures in a graph sequence
Mining preserving structures in a graph sequence
复制标题
DOI：
10.1016/j.tcs.2015.12.007
复制
发表时间：
2012-06
期刊：
影响因子：
--
通讯作者：
T. Uno;Yushi Uno
中科院分区：
文献类型：
--
作者：
T. Uno;Yushi Uno
在最近的数据挖掘研究中，对图序列中的频繁结构进行了深入的研究，其中一个主要关注点是沿着图序列改变结构以捕获数据的动态属性。相反，我们最近关注图序列在一定时期内满足给定性质的“保留结构”，并研究了这种结构的挖掘。对于起始点，我们提出了两个结构，一个连接的顶点子集和一个存在一定时间的团。我们考虑列举这些结构的问题。并针对这些问题提出了多项式延迟算法。它们的运行时间可能取决于表示的大小，然而，如果每条边在表示中最多有一个时间间隔，则连接顶点子集的运行时间为O (| V|| E| 3)，对于团块的运行时间为O (min (min) {Δ 5,| E| 2 Δ})，其中输入图为G=(V， E)，最大度为Δ。据我们所知，这是处理这个概念的第一种方法，即保留结构。
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.