Subgraph Matching for Single Large Multigraphs Subgraph Matching for Single Large Multigraphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2014

Subgraph Matching for Single Large Multigraphs Subgraph Matching for Single Large Multigraphs

Résumé

Nowadays, many real world data can be represented by a network with a set of nodes interconnected with each other by multiple relations (multiple edges). Such a rich graph, called multigraph, is very appropriate to represent real world scenarios with complex interactions. However, performing sub-multigraph query on enriched graph is still an open issue since, unfortunately, all the existing algorithms for subgraph query matching fail to consider multiple edges between nodes and, nevertheless, they cannot be directly applied to handle multigraphs. Motivated by the lack of approaches for sub-multigraph query and stimulated by the increasing number of datasets that can be modelled as multigraphs, in this paper we propose SUMGRA, a novel algo-rithm to extract all the embeddings of a query sub-multigraph from a single large multigraph. SUMGRA is composed of two main phases: Firstly, it implements a novel indexing schema for multiple edges, which will help to efficiently retrieve the vertices of the multigraph that match the query vertices. Then, it performs an efficient recursive subgraph search to output the entire set of embeddings for the given query. Extensive experiments conducted on both real and synthetic datasets prove the time efficiency as well as the scalability of SUMGRA.
Fichier principal
Vignette du fichier
report.pdf (488.73 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01076138 , version 1 (22-10-2014)

Identifiants

  • HAL Id : lirmm-01076138 , version 1

Citer

Anonyme Anonyme. Subgraph Matching for Single Large Multigraphs Subgraph Matching for Single Large Multigraphs. [Research Report] RR-2014030, LIRMM. 2014. ⟨lirmm-01076138⟩

Collections

LIRMM LARA
330 Consultations
522 Téléchargements

Partager

Gmail Facebook X LinkedIn More