Show simple item record

dc.contributor.authorNguyen, Lam B. Q.
dc.contributor.authorVo, Bay
dc.contributor.authorLe, Ngoc-Thao
dc.contributor.authorSnášel, Václav
dc.contributor.authorZelinka, Ivan
dc.identifier.citationEngineering Applications of Artificial Intelligence. 2020, vol. 90, art. no. UNSP 103539.cs
dc.description.abstractMining frequent subgraphs is an important issue in graph mining. It is defined as finding all subgraphs whose occurrences in the dataset are greater than or equal to a given frequency threshold. In recent applications, such as social networks, the underlying graphs are very large. Algorithms for mining frequent subgraphs from a single large graph have been developing rapidly lately. Among all such algorithms, GraMi is considered the state-of-the-art. However, GraMi still consumes a lot of time and memory in the mining of a large graph. In this paper, we propose two effective strategies to optimize the GraMi algorithm, which help to increase performance as well as reduce memory consumption during execution. Firstly, GraMi only lists all frequent subgraphs, without computing the support of each mined subgraph. This is disadvantageous in decision support systems, which require information about the support of all subgraphs. Therefore, we optimize GraMi to compute the support values during the mining process. Secondly, we apply the strategy of sorting all edges in graphs by their frequencies, which means that edges with low frequencies will be mined first, and vice versa. This sorting strategy can reduce the number of possibly infrequent subgraph candidates, especially on large subgraphs that are usually derived from those edges with high frequency. Thirdly, we apply a parallel processing technique, in which each frequent edge is executed simultaneously in a separate thread, and improve our parallel strategy by combination with the sorting strategy. Our experiments were performed on three real datasets and the results showed that the performance, as well as memory requirements, are better than those of the original GraMi algorithm.cs
dc.relation.ispartofseriesEngineering Applications of Artificial Intelligencecs
dc.rights© 2020 Elsevier Ltd. All rights reserved.cs
dc.subjectdata miningcs
dc.subjectdecision support systemscs
dc.subjectsorting strategycs
dc.subjectsubgraph miningcs
dc.titleFast and scalable algorithms for mining subgraphs in a single large graphcs
dc.description.sourceWeb of Sciencecs
dc.description.firstpageart. no. UNSP 103539cs

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record