With Tommaso Venturini and Pablo Jensen, we submitted the following paper to publication. In a nutshell, we propose and discuss a framework for interpreting networks visually, in the context of a dot-line diagram and a force-directed node placement algorithm, which is a common practice in the social sciences.
We call Visual Network Analysis (VNA) the practice in which you spatialize a network and interpret it visually. Note that this practice is never isolated, it is usually associated with using metrics to measure the topology of the network and/or qualitative inquiry on the phenomenon represented or modeled as a graph. But in VNA the visualization plays an important role in the exploration of the data, in the spirit of Exploratory Data Analysis (EDA). This practice is not unusual in the social sciences, especially now that we have access to many relational data sets.
In the typical scenario we discuss, a researcher is using Gephi or a similar software and applies a layout algorithm such as Force Atlas 2 or similar to an empirical network of 100 to 100,000 nodes. The expected outcome of the visualization is to obtain basic insights on the structure of the network and formulate hypotheses that could be tested by other means (graph metrics, external knowledge on that phenomenon…).
The central question we investigate and frame is: how to interpret the network visualization? In other terms, what do we see that we can or cannot trust, and what is important that we cannot see?
Interpreting a network visualization requires first to work on the semiotics of the image: color and size of the nodes, edges, labels… We provide a few guidelines based on classics such as Bertin’s Semiology of Graphics for instance. On that matter, network visualization is like the rest of data visualization. Things get complicated when we try to interpret the position of the nodes.
The big question – which we could not fully answer – is about the meaning of node positions. Even though we know how the algorithms producing the placement work, it does not mean that we know how to interpret the outcome. We know a number of things from these algorithms’ design, we can conjecture other things from experience, and we ignore other things.
- It is all about the relative distances between the nodes (which pairs are closer or more distant than others)
- Axes have no meaning (you could rotate, scale, flip the image without impacting its interpretation)
- Nodes that are closer have a tendency to be connected, but not always, not directly, and there is a massive amount of exceptions (basically, all long lines represent pairs of connected nodes that nevertheless end up far away)
- A. Noack has shown that the visual clusters correspond to modularity clustering.
- This strategy is bad at representing the asymmetries of directed networks (because visual distances are mutual while topological distances are not).
- Force-driven layout placement are optimizing something, but we do not know exactly what. It just turns out that these algorithms are very useful in practice, and people appreciate the insights they get from it, but we have no satisfying rationale to explain that.
- The thing that is optimized is probably a distance between the nodes, because it is how we interpret the visualization. But we do not have any mathematical expression of that distance.
- How to explain in everyday words what the visual distances represent.
- What the distance between the nodes in the visualization is an approximation of (in mathematical terms).
If we were able to find a mathematical distance that reasonably correlates with the distances in the visualization, we could use it as a way to evaluate the different algorithms and provide a theoretical ground to VNA. We were not able to find this distance, but in the paper we propose a profile of this hypothetical distance, based on what we already know of force-driven placement algorithms.
The paper also proposes a few experiments. We show for instance that the visual distance does not correlate well with the geodesic distance (length of the shortest path, counted in number of links) or the the mean commuting time (another intuitive notion of distance in a graph). We also provide an empirical account for Noack’s theoretical claim that the visual clusters correspond to modularity clustering.
We do this in a pretty fun way:
- Spatialize the network
- Apply modularity clustering (Louvain algorithm). It finds groups of nodes that are well linked together and poorly linked from group to group (let us call these “modules”.
- Apply a k-means based on nodes positions: it makes groups of nodes that are visually close. Let us call these “visual clusters”. We set the algorithm so that we have the same number of clusters than modularity.
- We look at all the pairs of nodes, and we look at whether the two nodes are in the same module or not, and if they are in the same visual cluster or not. The two measures agree if (1) the two nodes are in different modules and different visual clusters, or (2) if the two nodes are in the same module and visual cluster. Measures disagree if (3) the two nodes are in the same module but different visual clusters or (4) different modules but the same visual cluster.
We show that A. Noack was right, but also that Force Atlas 2 and LinLog perform better than Früctherman Rheingold, for instance.