摘要：La minería de subgrafos conexos frecuentes es un problema interesante con amplias aplicaciones en la vida práctica. La mayor parte de los algoritmos para este tipo de minería detectan los candidatos duplicados utilizando pruebas de forma canónica. Este tipo de pruebas tienen una alta complejidad computacional, lo cual afecta el desempeño de los algoritmos de minería de grafos. En este artículo se proponen nuevas propiedades para reducir el número de pruebas de forma canónica en este tipo de minería. Basado en estas propiedades, se propone un nuevo algoritmo llamado gRed. Los resultados experimentales en colecciones de datos reales muestran el impacto de las nuevas propiedades en la eficiencia de gRed, reduciendo el número de pruebas de forma canónicas con respecto a gSpan. Además, el desempeño de gRed es comparado respecto gSpan y otros algoritmos reportados en el estado del arte.
其他摘要：Frequent connected subgraph (FCS) mining is an interesting problem with wide applications in real life. Most of the FCS mining algorithms have been focused on detecting duplicate candidates using canonical form tests. Canonical form tests have high computational complexity, and therefore, they affect the efficiency of graph miners. In this paper, we introduce novel properties to reduce the number of canonical form tests in FCS mining. Based on these properties, a new algorithm for FCS mining called gRed is presented. The experimentation on real world datasets shows the impact of the proposed properties on the efficiency of gRed reducing the number of canonical form tests regarding gSpan. Besides, the performance of our algorithm is compared against gSpan and other state-of-the-art algorithms.
关键词：Data mining; frequent patterns; graph mining; frequent subgraph;Minería de datos; patrones frecuentes; minería de grafos; subgrafos frecuentes
