Fast and scalable algorithms for mining subgraphs in a single large graph

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F20%3A10245623" target="_blank" >RIV/61989100:27240/20:10245623 - isvavai.cz</a>

Alternative codes found

RIV/61989100:27740/20:10245623

Result on the web

<a href="https://www.sciencedirect.com/science/article/pii/S0952197620300397" target="_blank" >https://www.sciencedirect.com/science/article/pii/S0952197620300397</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.engappai.2020.103539" target="_blank" >10.1016/j.engappai.2020.103539</a>

Result language

angličtina

Original language name

Fast and scalable algorithms for mining subgraphs in a single large graph

Original language description

Mining 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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10200 - Computer and information sciences

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2020

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE

ISSN

0952-1976

e-ISSN

—

Volume of the periodical

90

Issue of the periodical within the volume

90

Country of publishing house

GB - UNITED KINGDOM

Number of pages

12

Pages from-to

—

UT code for WoS article

000528194400032

EID of the result in the Scopus database

—