HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

An edge that connects more than two nodes in a graph?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
nodesgraphconnectsthanmoreedgetwothat

Problem

Is there a way to create a single edge on a graph that connects 3 or more nodes? For example, let's say that the probability of Y occurring after X is 0.1, and the probability of Z occurring after Y is 0.001, but the probability of Z occurring after both X and Y occur is 0.95. If the probabilities are assigned to each edge as weights, how can I make this happen?

$$X _\overrightarrow{0.1} Y$$

$$Y _\overrightarrow{0.001} Z$$

$$\overrightarrow{X \underrightarrow{} Y \underrightarrow{0.95}} Z$$

Solution

When edges connect more than two nodes, you don't have a graph, you have a hypergraph. More precisely, since transitions are oriented (you're starting from a digraph) and there are probability on each transition, you have a weighted hyperdigraph. I'm not sure having this term will help you that much: as data structures go, this isn't that much of a classic.

Transitions with multiple origins rather remind me of Petri nets. If your probabilities are rational numbers and there are no loops, you can scale them to integers. Otherwise you would need to reach for probabilistic Petri nets, I think.

Context

StackExchange Computer Science Q#2826, answer score: 9

Revisions (0)

No revisions yet.