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.
Document type :
Reports
Liste complète des métadonnées

Cited literature [26 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01076138
Contributor : Isabelle Gouat <>
Submitted on : Wednesday, October 22, 2014 - 4:49:17 PM
Last modification on : Friday, September 16, 2016 - 3:06:16 PM
Document(s) archivé(s) le : Friday, January 23, 2015 - 11:12:03 AM

File

report.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

466

Files downloads

676