8
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Are you searching for hyperedges? $\endgroup$
    – user2025
    Commented Jul 19, 2012 at 22:00
  • $\begingroup$ 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? $\endgroup$
    – Nick Anderegg
    Commented Jul 19, 2012 at 22:07

2 Answers 2

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Nick Anderegg
    Commented Jul 19, 2012 at 22:14
  • $\begingroup$ @NickAnderegg That sounds like a completely different beast! Isn't this a plain old Markov chain? $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Jul 19, 2012 at 22:16
  • $\begingroup$ 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. $\endgroup$
    – Nick Anderegg
    Commented Jul 19, 2012 at 22:22
  • 1
    $\begingroup$ @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. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Jul 19, 2012 at 22:26
  • $\begingroup$ 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. $\endgroup$
    – Nick Anderegg
    Commented Jul 19, 2012 at 22:36
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Nick Anderegg
    Commented Jul 20, 2012 at 2:01
  • 1
    $\begingroup$ 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. $\endgroup$
    – alto
    Commented Jul 20, 2012 at 2:27
  • 1
    $\begingroup$ You could also take the nonparametric Bayesian approach with something like the sequence memoizer. $\endgroup$
    – alto
    Commented Jul 20, 2012 at 2:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.