Monthly Archives: July 2017

There are various layouts that you can choose from to visualize a network. All of the networks that you have seen so far have been drawn with a force-directed layout. However, one weakness that you may have noticed is that as the number of nodes and edges grows, the appearance of the graph looks more and more like a hairball such that there’s so much clutter that you can’t identify any meaningful patterns.

Academics are actively developing various types of layouts for large networks. One idea is to simply sample a subset of the network, but by doing so, you lose information. Another idea is to use a layout called a hive layout, which positions the nodes from the same class on linear axes and then draws the connections between them. You can read more about it here. By doing so, you’ll be able to find patterns that you wouldn’t if you were using a force layout. Below, I’ve taken a template from the D3.js website and adapted it to the petroleum trade network that we’ve seen in the previous posts:

Nodes of the same color belong to the same modularity class, which was calculated using gephi. You can see that similar nodes are grouped closer together and that the connections are denser between nodes of the same modularity class than they are between modularity classes. You can mouse over the nodes and edges to see which country each nodes represent and which countries each trade link connects. Each edge represents money flowing into a country. So United States -> Saudi Arabia means the US is importing petroleum.

For comparison, below is the same network, but drawn with a force-directed layout, which looks like a giant…hairball…sort of thing.

Here’s the code used to produce the json file:

I had originally intended to create graphics for all the world’s countries, but the resulting visualizations looked so cluttered that I felt like I was tripping on acid, so I reduced the scope of today’s post to those nations that used to belong to the Soviet Union.

From the original intention of the post, I changed the petroleum dataset to draw from an MIT dataset going all the way back to 1962, although in retrospect that was unnecessary. A friend of mine suggested that I create some kind of visualization that varied over time, so I’ve done just that. I used igraph to create a network for each year, calculated the eigenvector centrality of each node for each network, and then calculated the relative importance of the ex-Soviet countries to each other in the international sphere.

You can see from these visualizations that immediately after the breakup, Russia was the dominant player, but as the years have gone by, other countries like Azerbaijan and Kazakhstan have become increasingly important, and for this particular commodity, Russia’s power is declining:

I felt like these templates weren’t designed to handle all the ex-Soviet countries, so for the top visualization I hand picked 4 countries that I believed had the most influence. Here’s all of them together:

Today marks a milestone in my blog in the sense that I’ll be using D3.js for the first time. I’ve been interested in this library for some years now and I’ve finally gotten around to incorporating some simple examples into my blog.

D3.js is a JavaScript library for producing stunning visualizations – you may have seen several of them in Internet media publications and you can see some more examples on the D3.js homepage.

I think you can’t just be good with code to maser D3, you have to be a bit of an artist, because even if you understand the library well, your visualizations will look bad if you aren’t good with color coordination and web design.

It turns out one of the core developers of the library had already done what I had set out to do today – create a D3.js graph using the Les Miserables data set:

You can see here that this visualization differs from the previous ones in that it’s interactive and dynamic – the nodes appear to be suspended in some kind of invisible goop and the edges are elastic. You can click on the nodes and drag them around and watch them snap back into place when you release them.

Since there’s no point in duplicating what has already been done, I’ve decided to adapt this template to the previous post’s data set, the international petroleum trade:

Compared to the Les Miserables visualization, this one appears to have a bit more inertia as the whole graph doesn’t move as much if you try to click and drag one of the nodes.

I didn’t have to do too much work – the hard part was just figuring out how to get the json format correct and consistent with the html file. I exported the modularity class from gephi into R and used that to color the nodes. R was used to create the json file:

Okay, so I guess there wasn’t much to add as far as theory goes. But I do think these visualizations are pretty cool, and add a level of engagement and interaction with the user that you don’t get with still images.

As far as readings go, there wasn’t much to include from the text in today’s post since I just went through a section that covered some basic proof techniques (induction, contradiction, etc.). Tomorrow will be somewhat similar since that section covers general data gathering and manipulation. So today I’ll go over some data I stumbled upon while looking for other texts on graph theory.

The Observatory of Economic Complexity
MIT has some neat data sets here – these contain aggregate trading data for various commodities dating back to 1962. I was interested in looking at crude petroleum movements between countries in the most recent year available, 2014.

Creating a gexf file
Here’s the script I used to generate the gexf file that I imported into gephi. This is pretty much self-contained, and ought to run on your computer as is as long as you have the sqldf package installed. One improvement over previous code is that it fetches the datasets automatically, rather than having me point it out somewhere in my post. I also discovered a useful function called basename() which extracts the file name part of a url string containing a filename.

Generating the graph

After importing the gexf file, adjusting the graph for eigenvector centrality, and applying some community detection, gephi produced the following result:

Try clicking on the graph – you can zoom in quite a bit to see the countries and edges in detail. I’ve set the graph so that edge width is proportional to the log of the export value, so the higher the trading volume between two countries, the thicker the edge. We can also see that communities are highlighted in the same color – we would intuitively associate these with trading blocs, or groups of countries that work closely together.

In this graph, the node size is proportional to eigenvector centrality. In other words, the larger the node, the more important the country is to the network. To me, this was kind of puzzling. At least in my mind, I would have thought that major exporting nations like Saudi Arabia would have appeared much larger on the graph. However, you can see from the image that countries associated with importing oil dominate the graph.

I thought maybe it had to do with the direction of the edges. What we have here is a directed graph – if you look carefully you can see that the edges are actually arrows that point from the exporting country to the importing country. If we reverse the direction of these arrows – that is, recreate the graph from the perspective of money flowing into exporting countries rather than goods flowing out of those countries, we get the following graph:

This graph is a little more consistent with my intuition – we can see that major exporting nations like Saudi Arabia, Iraq, and Azerbaijan appear much larger, while importing nations appear smaller. However, I have to caution myself that just because the graph is consistent with my belief, doesn’t mean I’m right. I’ll have to see if I can further understand centrality as I continue in the course.

Oftentimes, we would like to think about the connectivity of a network, that is, how robust is a network to the removal of nodes and edges? I can think of several real-world applications where we might ask this question, for example:

• Which roads can we remove from the transportation network such that people can still get to where they want to go?
• Which metro stations would cause the most disruption to the network if they were destroyed?
• What enemy bases should we target first if we want to disrupt their supply chain?
• Where should we add roads, or other links between stations to increase the robustness of the network?
• What would happen to a group of friends if certain people left? Would they still hang out?

…and so on.

This brings us to two measures of network cohesiveness – edge connectivity and vertex connectivity. Simply stated, edge connectivity measures the number of edges we would need to remove from a network in order to divide it into distinct components. For example, think about your daily commute. If we were to remove one of the roads on your commute, you would probably still be able to reach your destination, even though you’d have to find some other way to get to work. However, if we were to remove more and more roads, eventually you would be unable to get there, and at some point, if we remove even more roads, your workplace may become an inaccessible island separate from the rest of the transportation network. We would call your workplace a component, that is, a node unreachable from any other node. Edge connectivity measures the minimum number of edges we would have to remove in order to separate a network into distinct components. The higher the edge connectivity, the more edges we’d have to remove – so we can say that the higher this number, the more cohesive the network is.

Formally,
Suppose is a simple network.

• A disconnecting set of is any subset for which the network has more components than .
• S is a cut-set of if it contains no proper subsets that are disconnecting sets.
• The edge connectivity of a network is the number of edges in the smallest cut-set and is denoted by . If then is k–edge connected.

Formally, a set of nodes in a connected network is called a separating set if their removal (and the removal of incident edges) disconnects the graph. If the smallest such set has size k then the network is called k–connected and its connectivity, denoted , is k. If then a node whose removal disconnects the network is known as a cut-vertex.

Likewise, vertex connectivity measures the number of nodes we’d have to remove (along with their associated edges) in order to separate a network into distinct components. For example, consider the Hong Kong subway system:

If you ever have the chance to ride the subway in Hong Kong, I recommend that you do – in my mind it’s the best subway system in the world. In network theory, we call this type of network a connected graph, that is, every subway station is reachable from every other station. If we were to remove Wong Tai Sin from the map, we’d still be able to reach every station from every other station. Likewise, we’d still be able to do so if we removed the stations on the periphery, like Chai Wan or Wu Kai Sha. However, if we were to remove just a single important station, say Quarry Bay, we would sever the eastern portion of the Island Line from the rest of the network. Thus, Quarry Bay is a cut-vertex of the Hong Kong subway system. Since vertex connectivity measures the minimum number of nodes we’d have to remove to separate a graph, we say that Hong Kong’s subway system has a vertex connectivity of 1. Like edge connectivity, the higher the vertex connectivity, the more robust the network.

Looking at our Les Miserables example, it’s pretty obvious that both the edge and vertex connectivity is one:

If we were to remove the edge between Myriel and Napoleon, we would separate the graph. Likewise, if we were to remove Myriel from the picture, we’d also separate the graph. This is a somewhat boring example, and output from the R console confirms this is true: