Unless you’ve spent the past five years on an isolated island in the middle of the Pacific, you’ll have heard of Facebook and Twitter and LinkedIn and MySpace and Flickr. Social media sites: whether you love them, hate them, or just don’t get them, they’re going to be here for a while. If you’re like many of us, you may have a few accounts on these sites, whether you’re a power user or occasional dabbler. Social media allow us to re-connect with old friends and colleagues, share our thoughts – and photos, advertise, network... and generally waste time. :)

I want to take a look at these from a slightly different angle, that is, graph theory. If you’ve ever heard of the travelling salesman problem, you’ve got a bit of an idea of what this is already. One of the most popular problems in mathematics, the travelling salesman problem (or TSP, to those in the know) looks at how to find the shortest path which visits each of a number of locations, returning in the end to the starting point.

The Google Maps Fastest Roundtrip Solver is a great online application which lets you enter in your own set of locations, and will then calculate the shortest path for you. I asked it to plan a trip for me starting from Maplesoft’s home base in Waterloo, Ontario:

And here’s what the graph of my TSP looks like, done in Maple:

In essence, graph theory is the study of networks and connections between points. Graphs are mathematical structures that you can use to look at these connections, and of course there are many rules that can be applied.

I used Maple to represent a very small Facebook network, consisting of 8 friends, as a graph. This is what it looks like:

Basically, each person is represented as a single point, and the blue connecting lines drawn between points indicate who is friends with whom.

In the context of social media, people in a network are the nodes of a graph, and of course you can study the connections and relationships between those people. To set up the simple graph above, I used just a couple of Maple commands, using the GraphTheory Package:

with(GraphTheory):
FB := Graph({{Ed, John}, {Ed, Clarence}, {Jane, John}, {Jane, Nancy}, {Jane, Paul}, {Jane, Susan}, {John, Nancy}, {John, Paul}, {John, Susan}, {John, Trevor}, {John, Clarence}, {Nancy, Trevor}, {Paul, Trevor}, {Susan, Trevor}}):
DrawGraph(FB);

My graph (called ‘FB’) consists of 8 vertices, corresponding to the people in my example Facebook network, and the 14 connections between them.

Of course real social networks are much more complex than this. For instance, here is an example social network graph:

An average Facebook user has 130 “friends” in his or her network, and the connections contain more information than just the basic “who is friends with whom”. Data such as “who is in a relationship with whom”, “who went to school with whom”, what music and film interests people have, what social causes they are embracing and so on, is also available. In fact, analysis of social networks is attracting a large following in the fields of sociology, anthropology, economics, and communications, to name a few. It will certainly be interesting to follow how this emerging way of understanding the world plays out over the next five to ten years – I’ll have to make sure I keep myself connected and in the loop. :)

One final note: Maplesoft has a presence on Facebook, Twitter, and LinkedIn, if you would like to add us to YOUR graph.