On multiaspect graphs

DOI10.1016/J.TCS.2016.08.017zbMATH Open1359.68235arXiv1408.0943OpenAlexW2400899518MaRDI QIDQ517022FDOQ517022

Authors: Klaus Wehmuth, Éric Fleury, Artur Ziviani 

Publication date: 16 March 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Different graph generalizations have been recently used in an ad-hoc manner to represent multilayer networks, i.e. systems formed by distinct layers where each layer can be seen as a network. Similar constructions have also been used to represent time-varying networks. We introduce the concept of MultiAspect Graph (MAG) as a graph generalization that we prove to be isomorphic to a directed graph, and also capable of representing all previous generalizations. In our proposal, the set of vertices, layers, time instants, or any other independent features are considered as an aspect of the MAG. For instance, a MAG is able to represent multilayer or time-varying networks, while both concepts can also be combined to represent a multilayer time-varying network and even other higher-order networks. Since the MAG structure admits an arbitrary (finite) number of aspects, it hence introduces a powerful modelling abstraction for networked complex systems. This paper formalizes the concept of MAG and derives theoretical results useful in the analysis of complex networked systems modelled using the proposed MAG abstraction. We also present an overview of the MAG applicability.

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

Recommendations

• Multiaspect graphs: algebraic representation and algorithms
• Deep graphs -- a general framework to represent and analyze heterogeneous complex systems across scales
• Line graphs for a multiplex network
• Multiplexity analysis of networks using multigraph representations
• Multilayer networks: metrics and spectral properties

zbMATH Keywords

complex networksnetwork sciencemultilayer networksgraph generalizationhigher-order networkstime-varying graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• On extremal problems of graphs and generalized graphs
• On generalized graphs
• Multiplicative attribute graph model of real-world networks
• Multiaspect graphs: algebraic representation and algorithms
• On the exploration of time-varying networks
• Title not available (Why is that?)
• Hypergraphs and Ramseyian Theorems

Cited In (9)

• Mapping higher-order network flows in memory and multilayer networks with Infomap
• On the plurality of graphs
• Multiaspect graphs: algebraic representation and algorithms
• Deep graphs -- a general framework to represent and analyze heterogeneous complex systems across scales
• On seed graphs with more than two components
• On sequential structures in incompressible multidimensional networks
• Multi-colored spanning graphs
• Weighted, bipartite, or directed stream graphs for the modeling of temporal networks
• Algorithmic networks: central time to trigger expected emergent open-endedness

Uses Software

• GenLouvain

This page was built for publication: On multiaspect graphs

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