An efficient and scalable approach for mining subgraphs in a single large graph

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27740%2F22%3A10249926" target="_blank" >RIV/61989100:27740/22:10249926 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/61989100:27240/22:10249926

Výsledek na webu

<a href="https://link.springer.com/article/10.1007/s10489-022-03164-5" target="_blank" >https://link.springer.com/article/10.1007/s10489-022-03164-5</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10489-022-03164-5" target="_blank" >10.1007/s10489-022-03164-5</a>

Jazyk výsledku

angličtina

Název v původním jazyce

An efficient and scalable approach for mining subgraphs in a single large graph

Popis výsledku v původním jazyce

In many recent applications, a graph is used to simulate many complex systems, such as social networks, traffic models or bioinformatics, and the underlying graphs for these systems are very large. Algorithms for mining all frequent subgraphs from a single large graph have attracted much attention and been studied in more detail lately. Mining frequent subgraphs is important, and defined as finding all subgraphs whose occurrences in a dataset are greater than or equal to a given frequency threshold. Among frequent subgraph algorithms, GraMi is considered as the state-of-the-art approach. However, GraMi has a huge search space, and therefore still needs a lot of time and memory to process a large graph. In this paper, we propose two effective strategies to balance and reduce the search space of GraMi, which can decrease the number of candidate subgraphs generated, with early pruning of a large portion of the domain for each candidate. Our experiments were performed on four real datasets and the results show that the performance of our balancing GraMi is better than those of the original algorithm GraMi and the optimized version SoGraMi.

Název v anglickém jazyce

An efficient and scalable approach for mining subgraphs in a single large graph

Popis výsledku anglicky

In many recent applications, a graph is used to simulate many complex systems, such as social networks, traffic models or bioinformatics, and the underlying graphs for these systems are very large. Algorithms for mining all frequent subgraphs from a single large graph have attracted much attention and been studied in more detail lately. Mining frequent subgraphs is important, and defined as finding all subgraphs whose occurrences in a dataset are greater than or equal to a given frequency threshold. Among frequent subgraph algorithms, GraMi is considered as the state-of-the-art approach. However, GraMi has a huge search space, and therefore still needs a lot of time and memory to process a large graph. In this paper, we propose two effective strategies to balance and reduce the search space of GraMi, which can decrease the number of candidate subgraphs generated, with early pruning of a large portion of the domain for each candidate. Our experiments were performed on four real datasets and the results show that the performance of our balancing GraMi is better than those of the original algorithm GraMi and the optimized version SoGraMi.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10200 - Computer and information sciences

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2022

Kód důvěrnosti údajů

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

Název periodika

Applied Intelligence

ISSN

0924-669X

e-ISSN

1573-7497

Svazek periodika

52

Číslo periodika v rámci svazku

15

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

15

Strana od-do

nestrankovano

Kód UT WoS článku

000778916300004

EID výsledku v databázi Scopus

—