A Note on the Modeling Power of Different Graph Types

Understand

Graphs can have different properties that lead to several graph types and may allow for a varying representation of diverse information.

• In order to clarify the modeling power of graphs, we introduce a partial order on the most common graph types based on an expressivity relation.
• The expressivity relation quantifies how many properties a graph type can encode compared to another type.
• Additionally, we show that all attributed graph types are equally expressive and have the same modeling power.