MultiAspect Graphs: Algebraic Representation and Algorithms

Artur Ziviani 1 Klaus Wehmuth 1 Eric Fleury 2, 3
3 DANTE - Dynamic Networks : Temporal and Structural Capture Approach
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme, IXXI - Institut Rhône-Alpin des systèmes complexes
Abstract : We present the algebraic representation and basic algorithms for MultiAspect Graphs (MAGs). A MAG is a structure capable of representing multilayer and time-varying networks, as well as higher-order networks, while also having the property of being isomorphic to a directed graph. In particular, we show that, as a consequence of the properties associated with the MAG structure, a MAG can be represented in matrix form. Moreover, we also show that any possible MAG function (algorithm) can be obtained from this matrix-based representation. This is an important theoretical result since it paves the way for adapting well-known graph algorithms for application in MAGs. We present a set of basic MAG algorithms, constructed from well-known graph algorithms, such as degree computing, Breadth First Search (BFS), and Depth First Search (DFS). These algorithms adapted to the MAG context can be used as primitives for building other more sophisticated MAG algorithms. Therefore, such examples can be seen as guidelines on how to properly derive MAG algorithms from basic algorithms on directed graphs. We also make available Python implementations of all the algorithms presented in this paper.
Type de document :
Article dans une revue
Algorithms, MDPI AG, 2016, 10 (1), 〈10.3390/a10010001〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01424662
Contributeur : Eric Fleury <>
Soumis le : lundi 2 janvier 2017 - 16:21:13
Dernière modification le : mercredi 19 septembre 2018 - 10:02:42

Lien texte intégral

Identifiants

Citation

Artur Ziviani, Klaus Wehmuth, Eric Fleury. MultiAspect Graphs: Algebraic Representation and Algorithms. Algorithms, MDPI AG, 2016, 10 (1), 〈10.3390/a10010001〉. 〈hal-01424662〉

Partager

Métriques

Consultations de la notice

388