×

Mining preserving structures in a graph sequence. (English) Zbl 1353.68218

Summary: 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 \{\operatorname{\Delta}^5, |E|^2 \operatorname{\Delta} \})\) 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.

MSC:

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

Software:

GraphScope; gSpan
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agrawal, R.; Imielinski, T.; Swami, A., Mining association rules between sets of items in large databases, (Proc. Int’l Conf. on Management of Data (1993)), 207-216
[2] Arimura, H.; Uno, T.; Shimozono, S., Time and space efficient discovery of maximal geometric graphs, (Proc. Discovery Science. Proc. Discovery Science, LNAI, vol. 5012 (2007)), 42-55
[3] Avis, D.; Fukuda, K., Reverse search for enumeration, Discrete Appl. Math., 65, 21-46 (1996) · Zbl 0854.68070
[4] Berlingerio, M.; Bonchi, F.; Bringmann, B.; Gionis, A., Mining Graph Evolution Rules, Lecture Notes in Computer Science, vol. 5781, 115-130 (2009)
[5] Bui Xuan, B.; Ferreira, A.; Jarry, A., Computing shortest, fastest, and foremost journeys in dynamic networks, Internat. J. Found. Comput. Sci., 14, 267-285 (2003) · Zbl 1075.68545
[6] Borgwardt, K. M.; Kriegel, H. P.; Wackersreuther, P., Pattern mining in frequent dynamic subgraphs, (Proc. 6th IEEE ICDM (2006)), 818-822
[7] Eppstein, D.; Galil, Z.; Italiano, G. F.; Nissenzweig, A., Sparsification—a technique for speeding up dynamic graph algorithms, J. ACM, 44, 669-696 (1997) · Zbl 0891.68072
[8] Ford, L. R.; Fulkerson, D. R., Flows in Networks (1962), Princeton University Press · Zbl 0106.34802
[9] Fukuda, K.; Matsui, T., Finding all the perfect matchings in bipartite graphs, Appl. Math. Lett., 7, 15-18 (1994) · Zbl 0792.68129
[10] Görke, R.; Hartmann, T.; Wagner, D., Dynamic Graph Clustering Using Minimum-Cut Trees, Lecture Notes in Computer Science, vol. 5664, 339-350 (2009), Springer · Zbl 1253.68262
[11] Han, J.; Dong, G.; Yin, Y., Efficient mining of partial periodic patterns in time series database, (Proc. 15th IEEE ICDE (1999)), 106-115
[12] Inokuchi, A.; Washio, T., A fast method to mine frequent subsequences from graph sequence data, (Proc. 8th IEEE ICDM (2008)), 303-312
[13] Inokuchi, A.; Washio, T.; Motoda, H., Complete mining of frequent patterns from graphs: mining graph data, Mach. Learn., 50, 321-354 (2003) · Zbl 1033.68079
[14] Kalnis, P.; Mamoulis, N.; Bakiras, S., On discovering moving clusters in spatio-temporal data, (Proc. 9th SSTD (2005)), 364-381
[15] Łącki, J., Improved deterministic algorithms for decremental transitive closure and strongly connected components, (Proc. 22nd ACM-SIAM SODA (2011)), 1438-1445 · Zbl 1376.05152
[16] Lahiri, M.; Berger-Wolf, T. Y., Mining periodic behavior in dynamic social networks, (Proc. 8th IEEE ICDM (2008)), 373-382
[17] Li, Z.; Ding, B.; Han, J.; Kays, R., Swarm: mining relaxed temporal moving object clusters, (Proc. 36th Int’l Conf. on VLDB (2010)), 723-734
[18] Makino, K.; Uno, T., New Algorithms for Enumerating all Maximal Cliques, Lecture Notes in Computer Science, vol. 3111, 260-272 (2004) · Zbl 1095.68626
[19] Pasquier, N.; Bastide, Y.; Taouil, R.; Lakhal, L., Efficient mining of association rules using closed itemset lattices, Inform. Sci., 24, 25-46 (1999)
[20] Read, R. C.; Tarjan, R. E., Bounds on backtrack algorithms for listing cycles, paths, and spanning trees, Networks, 5, 237-252 (1975) · Zbl 0316.05125
[21] Stix, V., Finding all maximal cliques in dynamic graphs, Comput. Optim. Appl., 27, 173-186 (2004) · Zbl 1045.90053
[22] Sun, J.; Faloutsos, C.; Papadimitriou, S.; Yu, P. S., GraphScope: Parameter-free mining of large time-evolving graphs, (Proc. 13th ACM Int’l Conf. on KDD (2007)), 687-696
[23] Tantipathananandh, C.; Berger-Wolf, T., Constant-factor approximation algorithms for identifying dynamic communities, (Proc. 15th ACM Int’l Conf. on KDD (2009)), 827-836
[24] Tantipathananandh, C.; Berger-Wolf, T.; Kempe, D., A framework for community identification in dynamic social networks, (Proc. 13th ACM Int’l Conf. on KDD (2007)), 717-726
[25] Tomita, E.; Tanaka, A.; Takahashi, H., The worst-case time complexity for generating all maximal cliques and computational experiments, Theoret. Comput. Sci., 363, 28-42 (2006) · Zbl 1153.68398
[26] Uno, Y.; Ota, Y.; Uemichi, A., Web structure mining by isolated cliques, IEICE Trans. Inf. Syst., E90-D, 1998-2006 (2007)
[27] Yan, X.; Han, J., Gspan: graph-based substructure pattern mining, (Proc. 2nd IEEE ICDM (2002)), 721-724
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.