Graph theory. Maybe you’ve heard of it before. Or maybe you haven’t. If you already know what it is, you won’t learn anything new here. But if you’re unfamiliar, prepare to be informed!
Like many terms used in mathematics and computer science, “graph theory” might sound obtuse and impenetrable. In fact, most of us deal with applications of graph theory on a daily basis. Do you use social media like Twitter or Facebook? Then you’re using a system built on graph theory!
It helps to define exactly what we’re talking about, here. A graph needs two things: nodes (points) and edges (lines). Some nodes may be connected by edges, and some may not be. Additional information may be attached to each node and edge, as well. What is important is how these nodes and edges help us describe real-world scenarios and problems.
Imagine a point in the center of a page that represents you. Imagine various other points around it that represent your family and friends. Without lines to connect them, these are just contextless points in space. They don’t really mean anything, do they? But if you start drawing lines between, say, the dot that represents you and the dots that represent your friends, you have begun graphing your personal social network. Perhaps some of your friends are also friends with each other. Drawing lines between their points can signify those relationships, as well. If you include friends of friends, the graph can grow even larger.
Six Degrees of Kevin Bacon? That’s graph theory, too.
If you use professional networking site LinkedIn, you might notice that connections are listed in degrees, as well. First-degree connections are, of course, your direct connections. Second-degree connections are first-degree connections of your connections that aren’t connected to you, and so on. LinkedIn tracks this information because it turns out that social networks reveal a lot about us. Based on nothing other than your social graph, Facebook can tell if you’re gay.
Determining how to time traffic lights is also a valid application of graph theory. It really is everywhere. Any problem that can be reduced to points and connections between those points is, essentially, a graph theory problem.
Organizational charts at your work place? Graph theory! Flowcharts that describe how to solve problems? Yup, that is, too. In fact, flowcharts are a particular type of graph called a directed graph. The basic nodes-and-edges type of graph is an undirected graph, meaning no information is available (or necessary) as to the relationships between nodes other than that they are connected. But in a directed graph, the relationship goes only one way, and is signified by the use of arrows, as one would see in a flowchart.
If you use navigation software on your smartphone/tablet or a GPS device, that is yet another application of graph theory. Vast databases hold lists of various intersections of roads and the distances between them, and combined with speed limit and traffic data, a computer can determine the quickest way to get from one point (where you’re starting) to another (your destination).
Just today, I had to apply graph theory to a problem I faced at work. Given six different versions of a program, what’s the best way to determine how those versions relate to one another? Since this is a large program spanning thousands of files, a visual comparison was out of the question. In this case, it was a graph with six points and no idea how they should be connected. To start off with, it’s safe to just connect all of them to each other–this is known as a “complete graph.” Since it’s not the points (versions) themselves but the edges (similarities and differences between them) that matter, I tracked everything in terms of edges. The files in each version were compared using industry-standard diff utilities, and it was determined how similar, on average, each version was to the next. I assigned a value to each edge to represent this average, which could be thought of as a “strength” or “force” (such terms are common when describing edges in a graph), and then for any given version, it quickly became clear which other version was most similar. It turned out that two particular versions dominate: the other four versions had the most similarity to these two. I could have spent weeks or months doing visual, file-by-file comparisons to determine this, and instead, a program was able to compute it in a matter of minutes.
The end result is a new graph showing how these versions all relate to one another, which describes how I will ultimately store the program code for easier management in the future. A coworker had attempted something like this a few years ago, but the project failed because it was being done manually and took too long–the code became outdated before effective comparisons could be completed. With my system, new versions can be compared just by adding them.
Okay, so maybe this was an excuse to gloat about a problem I solved at work. Even so, graph theory is fascinating and full of applications, from the trivial to the impressive. Graph theory is applied to works of fiction, for instance, to identify and describe relationships between characters.
If you didn’t know, now you do! Graph theory is all around us–we’re all nodes walking around, creating and changing edges. We live in a world of points and connections. As we generate and gather more and more data about ourselves and the world around us, quantifying everything from our relationships to our eating, sleeping, and spending habits, we will need newer, better ways to organize and represent that data. There is some irony, then, that much of that representation will come in the humble form of dots and lines. Graphs today, graphs tomorrow, and graphs forever.
