Defining Hypergraphs
I want to create a software system where a person can create labeled nodes, and then define labeled edges between the nodes. However, edges also count as nodes, which means you can have edges between edges and edges, edges and nodes, edges-between-edges-and-nodes and edges-between-nodes-and-nodes, and so on.
This type of hypergraph is described well here in this Wikipedia article:
One possible generalization of a hypergraph is to allow edges to point at other edges. There are two variations of this generalization. In one, the edges consist not only of a set of vertices, but may also contain subsets of vertices, subsets of subsets of vertices and so on ad infinitum. In essence, every edge is just an internal node of a tree or directed acyclic graph, and vertices are the leaf nodes. A hypergraph is then just a collection of trees with common, shared nodes (that is, a given internal node or leaf may occur in several different trees). Conversely, every collection of trees can be understood as this generalized hypergraph.https://en.m.wikipedia.org/wiki/Hypergraph I have been wondering about a good way to represent this data in a data structure.
Hypergraph
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
Formally, a directed hypergraph is a pair
( X , E )
{\displaystyle (X,E)}
, where
...
( X , E )
{\displaystyle (X,E)}
, where
...
Solution:Jump to solution
I always understood that back in the day Marko and crew decided that hypergraphs can be modeled by a property graph. You have to stick a vertex in the middle that represents the hyper edge.
This leaves the query language without any first class constructs about navigating a hyper edges but everything is reachable.
Another problem would be performance, the more abstraction away from the implementation on disc, the slower the graph becomes....
4 Replies
TBH, this may be easier to do in RDF than in LPG. 🙂
Triples can define relationships between entities (vertices). And you can use named graphs in RDF to wrap a triple into another entity/id. Then those can be entities themselves that can have other relationships.
From your example diagram above, I could have:
Good article here that talks about this more, but without using named graphs: https://ontologist.substack.com/p/hypergraphs-and-rdf
You can sort of back into LPG from this, but just easier (for me, at least) to think of things in terms of triples (vertex-edge-vertex) and a triple being an entity that can also have it's own relationships.
Hypergraphs and RDF
An Exploration in Pointers
Thanks
I will try that and I am also interested in how one could define algebraic property hypergraphs
https://groups.google.com/g/gremlin-users/c/0Q0jPHO2y0Q/m/iFusjztLAQAJ
https://arxiv.org/abs/1909.04881
https://arxiv.org/abs/1806.08304
https://ncatlab.org/nlab/show/hypergraph
arXiv.org
Algebraic Property Graphs
We present a case study in applied category theory written from the point of view of an applied domain: the formalization of the widely-used property graphs data model in an enterprise setting using elementary constructions from type theory and category theory, including limit and co-limit sketches. Observing that algebraic data types are a comm...
arXiv.org
Hypergraph Categories
Hypergraph categories have been rediscovered at least five times, under various names, including well-supported compact closed categories, dgs-monoidal categories, and dungeon categories. Perhaps the reason they keep being reinvented is two-fold: there are many applications---including to automata, databases, circuits, linear relations, graph re...
Solution
I always understood that back in the day Marko and crew decided that hypergraphs can be modeled by a property graph. You have to stick a vertex in the middle that represents the hyper edge.
This leaves the query language without any first class constructs about navigating a hyper edges but everything is reachable.
Another problem would be performance, the more abstraction away from the implementation on disc, the slower the graph becomes.
cool