-
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.
-
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.
-
The first seven chapters of Graph Theory and Complex Networks
-
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?
-
-
Ive never heard of Social DRM. I’ll have to look into that further.
-
-
-
-
-
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).
These ones are excellent, thank you.
Edit: you have an awesome blog. Here in case anyone else is curious - http://www.kmjn.org/notes/.
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!