1. 16

Some domains have mental models which can be readily applied to other domains fairly easily - their main theories and implications are highly abstractable and generalizable. For example:

  • In finance: efficient markets, compounding, risk, option theory.
  • In economics: marginal analysis, competitive markets, game theory, information asymmetries.
  • In statistics: a distribution, statistical significance, correlation, sample selection.
  • In biology: natural selection, genetic algorithms, gene expression.

What are the top takeaways from graph theory? The most generalizable? (For example: centrality, optimal paths, complexity).

I’d greatly appreciate any concise resources pointing me in the right direction.


  2. 9

    This might be more trivial than what you’re looking for, but one very general thing is reachability and its definition as the transitive closure of the “step” relation (reach(v) = U{reach(w) u {w} | edge(v,w)}).

    Many things can be viewed as “states and steps” and “can I reach w from v?” is then often something you want to know.

    1. 5

      Like in these slides, the reachability problem shows up in some formal methods work on model-checking transition systems. The abstract and finite state machines have been applied to tons of problem areas. That means reachability itself might benefit tons of areas through them. Just me hypothesizing there based on seeing it turn up in quite a few papers.

      1. 3

        Slightly more meta than that, reachability as the transitive closure of steps is also a useful way to encode things for model checkers (and model finders, in my case). For example, when using using model-finding for procedural level generation, it’s straightforward to constrain structural properties of levels. But if you want to also constrain dynamic properties of levels, like “the player must be able, consistent with the game mechanics, to reach X in the generated level”, you need to encode a little declarative model of reachability. That’s often easiest to do by defining what can happen in one step first, then adding a transitive-closure rule for overall reachability. E.g. the player model in Figure 8.11 of this textbook chapter does that with a little 3-state FSM player.

    2. 5

      For computer science, the most useful conceptual takeaways for me have been graph isomorphism, subgraphs, and various combinations of those concepts. Many problems can be mapped in some form onto asking whether two graphs are isomorphic, whether a graph is isomorphic to a subgraph of another one, whether a graph has subgraphs of a particular type, etc.

      With subgraphs (and related concepts like graph minors), the concept that I’ve found most interesting is the class of properties that are “hereditary” in some way or another (some examples at Wikipedia). For these, properties of the whole graph can be inferred from whether it contains a specific subgraph or minor. For example, a graph is nonplanar iff it contains K3,3 or K5 as a minor. Sometimes that way of thinking about problems lets you boil down a very messy and complex problem into very simple statements about a graph (not necessarily statements that are computationally easy to check, but that’s another question).

      1. 2

        These ones are excellent, thank you.

        Edit: you have an awesome blog. Here in case anyone else is curious - http://www.kmjn.org/notes/.

        1. 4

          you have an awesome blog

          Thanks! Though I don’t blog very often, alas. These days most of my writing goes into my academic publications. But blog posts can be useful in conveying different kinds of information or reaching a different audience, so I should get back to that more. I do have a gigantic set of blog drafts in rough bullet-point form that are pretty useful to me as research notes, but I seem to not get around to polishing them up into actual public posts often enough.

          There’s some interesting stuff on your blog too!

      2. 5

        By analogy to the statistics example, maybe the best answer is

        • graph theory: graphs, directed graphs

        but that’s hardly informative. I think the hard part when applying graph theory is recognizing that there is a graph in your problem in the first place and clearly identifying what the vertices and edges are (and whether they are directed). I guess you might throw “trees” and “directed acyclic graph” in the list? Because recognition imply more immediate simplification.

        I’d be interested in more examples from you, especially if you’ve been collecting these.

        A number of these examples look like extra perspectives on an existing situation though. And I think this one isn’t meant to be used quite in the same way. When graph theory is applicable, it should naturally suggest itself to you as you model the problem (instead of the other way around). I suppose if you miss the fact there is a graph at all, it might. Its closer to “a distribution” and “game theory” in nature.

        1. 5

          A list is a graph. A tree is a graph. A B-Tree is a graph. Relational systems use trees (graphs) for indexing. Non-relational systems too.

          A network is a graph. BGP operates on the internet graph.

          Transportation networks are graphs. The Braess paradox happens on a graph.

          By visualizing a relationship graph you can explain the complexity without words.

          Centrality (there are many BTW), spanning trees, optimal paths are key takeaways you can see applied to many disciplines if you can model your problem as a graph problem.

          I hope it helps.

          1. 1

            So this is actually the exact reason why I want to learn more about graphs, but I’m looking more for what about graphs I should learn. Are there any major topics or mental models I should take away? (For example, if someone asked me about economics, I would suggest they look at: marginal analysis, monopolies, the creation of money, game theory, etc.)

            Edit: alas, my poor reading comprehension. I didn’t see spanning trees. Will take a look - thank you.

            1. 3

              The first seven chapters of Graph Theory and Complex Networks

              1. 1

                Thanks for the reference. More interesting answer than usual on why it’s free:

                “Why for free?

                Sometimes when you write a book, it makes a lot of sense to think big and act commercially. Thinking big in this sense means you expect many people to have access to your book. Acting commercially means that you try to successfully market and sell your book. Sometimes, it’s enough to just think big, knowing that acting commercially will certainly keep everything small. When you write a book containing mathematical symbols, thinking big and acting commercially doesn’t seem the right combination. I merely hope to see the material to be used by many students and instructors everywhere and to receive a lot of constructive feedback that will lead to improvements. Acting commercially has never been one of my strong points anyway.

                However, freely accessible doesn’t mean that everyone has the right to copy and spread the material, which I would find quite offensive. For this reason, when requesting an electronic copy, the book will be watermarked with your e-mail address. The watermark is part of the LaTeX source, so it will take some effort to remove, although I do not have the illusion that removal is impossible.”

                First part sound great. Second makes me raise an eyebrow as to what they mean. No judgment since they wrote and gave away what you said is a great book. Maybe author just wants to track number of and be able to contact the beneficiaries?

                1. 1

                  This is called Social DRM. This is a totally different discussion though, and you could email the author for more details about his stance.

                  1. 1

                    Ive never heard of Social DRM. I’ll have to look into that further.

          2. 4

            A very general theory for understanding computation is Rewrite Systems. A rewrite system can be understood as pattern matching on terms in some first-order language, binding free variables, and literally rewriting the terms into other terms. For example:

            f(x,y) -> h(g(x),g(y))

            Defines a rewrite relation, where x and y are free variables. Now an interesting general question pops up: given an arbitrary rewrite relation, and an arbitrary term, will you eventually reach a term for which no longer any of the patterns match? This is a reachability problem (and undecidable in general).

            Other aspects of rewrite systems are: if you apply on any term two different rules, is it possible to join them back into a common term? This property is confluence and is also a general property of graphs. Joinability and meetability, and in particular partial order relations, are also understood intuitively as properties of graphs.

            1. 4

              You can translate almost any algorithmic problem into a graph modeled approach. Often this allows you to find more efficient algorithms (mostly already written by other people).