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

Abstract : 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.
Type de document :
Rapport
[Research Report] RR-2014030, LIRMM. 2014
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01076138
Contributeur : Isabelle Gouat <>
Soumis le : mercredi 22 octobre 2014 - 16:49:17
Dernière modification le : vendredi 16 septembre 2016 - 15:06:16
Document(s) archivé(s) le : vendredi 23 janvier 2015 - 11:12:03

Fichier

report.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-01076138, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

340

Téléchargements de fichiers

542