23 July 2014

A Survey of Graph Theory and Applications in Neo4J

A while ago I had the idea to do a graph theory talk at our local Neo4J Meetup, the Baltimore Washington Graph Database Meetup, especially since Neo4J and graph databases are based on graph theory.  So I finally sat down and spent quite a bit of time putting a talk together. I decided to go with the idea of an overview of graph theory with a primary focus on the theoretical aspects and with some applications like network theory and some specific examples of applications to Neo4J.  My talk is titled: "A Survey of Graph Theory and Applications in Neo4J" and I presented it on June 24, see below for video, slides, and references. This post is my thoughts on it and things leading up to its creation.

Some of my blog posts are created from a desire to make math more accessible and more relevant especially those areas of math that seem to be neglected by the traditional educational system.  One huge gaping hole in my math education both in our American institutional learning facilities and in my college computer science curriculum was that I was never exposed to graph theory.   Once you start studying graph theory you realize that many of these concepts could be taught in middle and elementary schools.  As I was preparing my presentation, I saw this: "Math for seven-year-olds: graph coloring, chromatic numbers, and Eulerian paths and circuits", reaffirming what I already knew.  Sadly many of these concepts were new to me as an adult, and I’d guess the same was probably true of much of my audience.

Graph theory has been a topic that I have included in my blog, I have written two posts about it one is a general math post: "Triangles, Triangular Numbers, and the Adjacency Matrix" and the other post: "The Object Graph" attempts to put it in part in a programming context .  One post or series of posts that I have wanted to do is an introduction/overview of graph theory.  I was thinking that my talk could be turned into those posts.  However, I am not sure if and when I will get a chance to do that, so I figured until then I will make the talk itself that post and that post is this post.

I found myself torn about publishing the video of my presentation, on one hand I feel that it could be much better but on the other, as a friend pointed out, people might find it informative and enjoy watching it.  That being said, I reserve the right to replace it with a better version if I ever do one.

Writing a post about the talk provides me with an opportunity make a few corrections, add some more source material and mention a couple of things that I would have liked to include but that got cut in the interest of time.

I’ll start by adding some additional source material.  I followed the introductory remarks with a brief historical overview.  For that, especially 20th century contributors I made use these power point slides of John Crowcroft’s "Principles of Communications" course.  I also referenced Graph Theory, 1736-1936 by Norman L. Biggs, E. Keith Lloyd, and Robin J. Wilson.  I mentioned the Watts and Strogatz Model (pdf of original nature paper).  I also included Fan Chung who is married to Ronald Graham and is known for her work in graph theory especially spectral graph theory.   I mentioned snarks not to be confused with Lewis Carroll‘s snarks from which he coined the name.  When I was talking about the topology part I mentioned Eulers Gem.  Since the World Cup was going on during the talk I have to include these topology links "The Topology and Combinatorics of Soccer Balls(pdf)" and some more "soccer ball math".

Due to time constraints I cut a few topics,  two of them were the ideas of graph isomorphisms and graph automorphisms, also ideas like: Graph families defined by their automorphisms and the automorphism group.  Another area that I didn’t really get into, except the linear algebra parts was the area of algebraic graph theory.

I did want to offer up a couple of corrections: I called a truncated icosahedron a dodecahedron, how embarrassing. I called the Travelling Salesman Problem, the Travelling Salesman Program, doh! When I said a bipartite graph has no connections between edges, it should have been vertices.  And finally I misstated Kirchoff’s Theorem, it should be n-1 non-zero Eigenvalues, obviously you only use the non-zero ones!  There are probably more and if I decide to replace these videos in the future, I will just replace this paragraph as well.

On a lighter note, when I was creating my "Graphs are Everywhere" images and sharing with my friend Wes, I created this one for fun:

Finally I’d like to thank our meetup sponsor neotechnology refreshments. The part where we thanked them at the meetup didn’t get recorded.