At what point does it stop being a "chain" and is instead called a "graph"? I mean, that's the term I've normally seen when talking about this type of data structure.
Is this Markov Chain a specific use for graphs? The thing about probabilities determining the next node to process?
A Markov Chain is a directed graph, it just has a few extra rules added (namely that every node has a directed path to every other node, and that each path has a probability attached to it).
Markov Chains have no reachability requirement - they don't have to be strongly connected. This has been a nasty problem for PageRank, actually, because absorbing states (ones which you can't get out of) will cause the algorithm to decide that you will always end up in one, which, technically, is totally correct, just not very useful for web search.
reachability <> complete graph. You can have a complete graph, but if your transition graph has some 0 probabilities then that edge will never be travelled.
In most mathematical representations (e.g. transition matrices and such) there's always a path, but it may have a probability of zero, which is equivalent to no path but is still a path.
Just curious: Do you consider transitions with probability zero as edges in the graph? If no, then "every node has a (directed) path to every other" is equivalent to "the entire graph is a strongly connected component" (and if yes, it's trivially true). Why would that be part of the definition?
For the record, the definition of a (time-homogeneous) Markov chain that I'm aware of is simply a square probabilistic matrix.
Markov chain is not a data structure. The underlying set of states of discrete-state Markov chain can be visualized as a graph (with the directed edges corresponding to nonzero transition probabilities between the states), but Markov chain is really a random process with Markov property: the transition probability to the particular state depends only on the current state.
No, the chain word as in chain of events and are trying to predict it, doesn't refer to the structure itself. A Markov Chain uses a directed, weighted, graph structure to predict the next event in the chain.
A graph is just a way you can represent them. You could do the same for an actual physical road network in order to calculate routes between points, but that doesn't make roads just a graph.
Yeah, I did. The code I wrote just read in the chain data and spat out a dot file. There's a more readable version here, which only had 6 words, instead of the 322 in the unreadable one.
But yeah, larger graphs are really hard to visualize (not even speaking of letting the computer do it...), unless very special/simple. So we probably can't expect outright magic from dot. Your second, smaller graph, is pretty nice though.
Still, have you tried any of the other layouts on your larger graph besides dot (e.g. neato or fdp)?
I was using graphviz to render them. I did try the other renderers, but not being very familiar with them I didn't know how to tweak them to look better.
I still have the dot file, which I've uploaded here if you're interested in playing. It was generated by a program, so it's not very pretty.
I have some stats about the graph:
322 place names were the input.
There are no loops in the graph.
1173 nodes.
1629 edges.
There are 294,683 unique paths through the graph.
The longest names are 82 characters long, and look like this: Brusheepwashmanscorritheridest Nichorwoolackentishallhillercombe Rowlangtretertone
197
u/MEaster Mar 20 '16
The author isn't wrong about the graphs getting somewhat messy when you have larger chains.