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

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$$

• Are you searching for hyperedges? – user2025 Jul 19 '12 at 22:00
• Ah, yes, this kind of explains what I'm looking for, I just can't figure out how that would be implemented. If node X points to Y and Y points to Z, I guess I would have to have some sort of supernode that could hold both X and Y while pointing to Z? Wouldn't that make traversals rather difficult? – Nick Anderegg Jul 19 '12 at 22:07

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.

• What if X and Y are ordered first? This is not what I'm working on now, but the idea stemmed from a context-aware spelling/grammar checker. Word $Y$ coming after word $X$ might have a very low occurrence, but if word $Y$ came after phrase $Z$ that consisted of the words $A->B->C$, then it might have a much higher occurrence. – Nick Anderegg Jul 19 '12 at 22:14
• @NickAnderegg That sounds like a completely different beast! Isn't this a plain old Markov chain? – Gilles 'SO- stop being evil' Jul 19 '12 at 22:16
• Hmm, I don't think that quite covers it, because the phrase would need to come in series. $\{A->B->C\} -> Y$ might occur 95% of the time, but $\{B->C\} -> Y$ might only have an occurrence of 2% if word $A$ is missing. See, my problem here is that I'm a incoming-sophomore CS major with 5th semester standing, a decade of programming experience, and a breakthrough idea that solves a very real problem/research topic if I can solve this one single prerequisite problem. – Nick Anderegg Jul 19 '12 at 22:22
• @NickAnderegg I'm afraid this is beyond me, I know nothing about NLP. I suggest you phrase your question differently, giving more information about your application domain and asking for a data structure recommendation in more general terms. – Gilles 'SO- stop being evil' Jul 19 '12 at 22:26
• I think I'll do that. Funny thing is, this actually has to do very little with NLP. I've tested my theory out on a small scale using just graphs, and it works. The only thing that's going to break it is certain compound-complex sentence structures, 4 prepositions, and idioms. Otherwise, this is research gold. I just don't know enough data structures. – Nick Anderegg Jul 19 '12 at 22:36

Based on your above comments with @Gilles, what you describe is just a higher order markov model. For example an $n$th order markov model, is a model which assumes

$$P(x_t | x_{t-1}, x_{t-2}, \ldots x_1) = P(x_t | x_{t-1}, x_{t-2}, \ldots x_{t-n}).$$

If $n$ is not fixed you have a variable order markv model.

• Hmm... this seems to be what I need... I think. I'm going to learn everything I possibly can about this topic available on the Internet, and I'll get back to you in a week. – Nick Anderegg Jul 20 '12 at 2:01
• Some other search terms to get you started are n-gram and suffix tree. Be warned there are some problems with these models, most notably the number of your parameters in your model exploding as you increase $n$. Depending on your application you may also want to look into hidden markov models or conditional random fields. They are two popular models for discrete sequences which allow you to sidestep this problem somewhat. – alto Jul 20 '12 at 2:27
• You could also take the nonparametric Bayesian approach with something like the sequence memoizer. – alto Jul 20 '12 at 2:30