Multiaspect graphs: algebraic representation and algorithms

DOI10.3390/A10010001MaRDI QIDQ1662581zbMATH OpenOpenAlexFDO

Authors Klaus Wehmuth, Éric Fleury, Artur Ziviani

Publication date 20 August 2018

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1504.07893

zbMATH Keywords

complex networkgraph algorithmshigh-order networkmultilayer networktime-varying network

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

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 graph. We also make available Python implementations of all the algorithms presented in this paper.

Review text

Summary: 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.

Recommendations

• On multiaspect graphs
• An algebraic multilevel multigraph algorithm
• Algorithmic aspects of intersection graphs and representation hypergraphs
• Algebraic Graph Algorithms
• An algebraic representation of graphs and applications to graph enumeration
• scientific article; zbMATH DE number 2183075
• scientific article; zbMATH DE number 5937963
• Graph algebras and graph varieties
• A theoretical characterization of the data structure `multigraph'

Cites work

• Collective dynamics of `small-world' networks
• Computing the eccentricity distribution of large graphs
• Depth-First Search and Linear Graph Algorithms
• Digraphs
• Editorial: Special issue on graph algorithms
• Emergence of Scaling in Random Networks
• Graphs and matrices
• scientific article; zbMATH DE number 3446921 (Why is no real title available?)
• scientific article; zbMATH DE number 5937963 (Why is no real title available?)
• Introduction to algorithms.
• On multiaspect graphs

Cited in

(8)

• A hybrid adjacency and time-based data structure for analysis of temporal networks
• Efficiency centrality in time-varying graphs
• Algorithmic networks: central time to trigger expected emergent open-endedness
• scientific article; zbMATH DE number 1498419 (Why is no real title available?)
• On multiaspect graphs
• Cops \& robber on periodic temporal graphs: characterization and improved bounds
• Multi-parameter analysis of finding minors and subgraphs in edge-periodic temporal graphs
• On sequential structures in incompressible multidimensional networks

Describes a project that uses

Uses Software

• Python

This page was built for publication: Multiaspect graphs: algebraic representation and algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1662581)