Hidden structures in hairballs, and how to see them

15 minutes read

At the moment, I am writing my PhD dissertation. As this part of my draft can be useful to those who work with network maps, I reproduce it here right away. I propose an example-based exploration of the Gestalt approach to the semiotics of network maps, and I explain why and how we can see structures in hairball networks. My argument is essentially visual. For an overview of Gestalt theory, see Wagemans et al., 2012. On Gestalt and network visualization, see Bennett et al., 2007; Kobourov et al., 2015.

When it comes to network visualization, the most important Gestalt principle is perceptual grouping. “Historically, the visual phenomenon most closely associated with perceptual organization is grouping: the fact that observers perceive some elements of the visual field as ‘going together’ more strongly than others.” (Wagemans et al., 2012). Multiple factors influence what we perceive as groups, but two of them stand out in our situation: proximity, and closure. In short, you may perceive a set of dots more or less as a textured shape (figure 1), provided that they are distributed homogeneously, that the contour draws a recognizable shape, and that these shapes are well separated. Technically, your perception works the other way around: you associate the dots because they are close, and this interplay of proximity and distance makes you see a contour, then you associate it to a known shape. This process is not perfect, however. The shapes we see have some degree of ambiguity, and different people may perceive different groups.

The topological structure is mainly mediated by the node placement, to the point that some authors propose to not display the edges at all (Noack, 2007). Here I will simplify the problem by considering that nodes are represented by dots of the same size and color. Size and color are known visual variables (in the sense of Bertin, 1967) but also influence the perception of groups (Wagemans et al., 2012) and should be accounted for in a complete perceptive model of network maps. Here, however, I only touch on this subject. My main concern is our perception of node groups, that we intuitively interpret as topological clusters. Gestalt theory provides tools to discuss this intuition.

As a starting point, let me emphasize the importance of gaps in our perception of groups. Gaps are places where the continuum of proximities breaks. We see groups when (i.e. because) there are gaps between them. We need gaps to separate clusters visually (figure 2). If the gaps are too small or inexistent, we do not perceive different groups. Different persons will agree more easily on the groups with big gaps than small gaps. Big gaps make visual groups less ambiguous and easier to see. This is, Gestalt says, how our cognitive system works.

Unfortunately, computations do not follow the same principles as human vision. Although a force-directed node placement algorithm makes, in some sense, groups, it does not care about the same gaps. Intuitively, the eye looks at the gaps border-to-border, while the algorithm cares about the distance between middle points, between statistical averages (figure 3). When there are large gaps, the eye and the algorithm agree. But when the gaps are small or inexistent, it is possible that the algorithm “sees” a gap where the human eye does not.

As an experimental illustration of this phenomenon using networks, I will use a planted partition model, also called stochastic block model. Here I build a network with two groups of nodes, and create links between the nodes by following a statistical rule. For two nodes in the same group, I will create a link with a probability P_in. For nodes in different groups, I will use a probability P_out. As long as P_in is bigger than P_out, each group is promised to be a cluster in a topological sense (e.g. modularity). I choose P_in and P_out so that Pin is smaller, and the sum equals 100%. When P_in is large, the clusters are well-defined. When P_in is 50%, the community structure has entirely disappeared and we just have a random network (indeed P_in = P_out = 50%).

I generate a series of networks with a decreasing probability P_in (figure 4). As expected, the most separated groups topologically (P_in high) are the most separated visually. As P_in gets closer to 50%, the two groups start to merge. At 70%, the general contour starts to look like a circle, but there is still a gap. At 60%, there is no more gap. Yet there is still a topological structure. Indeed, the layout correctly positions the nodes in the right group; but the groups are stuck to each other. We still see the groups because we have colors, but from just the node positions, we would not perceive a cluster. Gestalt theory says why: we need gaps and contours to perceive groups.

You may think that at a P_in of 60%, the two groups are too entangled to be considered distinct. There is some sense to this point, yet it does not change that there is some topological structure, and more importantly, that the force-directed layout is able to display it. Even though we do not see it. It displays it in the sense that nodes of the same group get placed next to each other. The layout algorithm is so consistently successful at retrieving these groups (figure 5) that we cannot deny their existence. But we do not see it because there is no gap. Here I only give a visual argument, but we could quantify it.

You may also think that we actually see the two groups, even without the colors. Take your chance at making the distinction between a planted partition of P_in=60% and a random network in figure 6, using solely the node placement. I doubt you see any gaps, and without them, the groups do not appear. But it does not mean that there is no locality principle: close nodes may still be, on average, more connected.

Hidden structures in hairballs

Many authors have blamed network visualization, and notably force-directed networks, for producing hairballs (e.g. Correa and Ma, 2011; Van Den Elzen and Van Wijk, 2014). Hairballs are typically networks such as those of figures 5 and 6, with a “significant node occlusion and link crossings that can almost completely fill the inter-node space” (Edge et al., 2018). Nocaj et al. (2015) and Edge et al. (2018) propose a sparsification approach based on reduction to subgraphs to tackle this specific problem, and Dianati (2016) a pruning approach. I do not deny the practical problem of hairballs (one does not see the structure), and I certainly think that sparsification methods have applications. Yet the hairball is most often a straw man.

The hairball rhetoric is easy to track in academic literature, since it precisely employs the term “hairball”. The argument is always to blame the layout for failing at representing the structure. But this statement is never grounded on a model of how we perceive network maps, and relies instead on a series of noteworthy assumptions. It assumes that network maps are, to some extent, self-evident. It assumes that the (community) structure is translated by the layout as visual groups. And finally, it assumes that the absence of visible groups is a failure. These assumptions are, in fact, wrong. The layout does not exactly translate the structure as visual groups, but as a locality principle. The difference is the presence of visual gaps: the layout may place same-cluster nodes together in a way that produces no visual gaps, which makes these groups invisible to the human eye. From an ethnographic perspective, this rhetoric is etic, it assesses the algorithm from the outside, using criteria alien to its own functioning. But it does not allow predicting the behavior of the algorithm, because it misses the way it assembles a visual structure (even though we do not see it). I claim that there are structures in hairballs, and that we may see them if we learn the way the algorithm communicates them. By mobilizing Gestalt theory, I hope to sketch an emic approach to hairballs.

Firstly, not all networks produce hairballs. Here, I assume that the layout algorithm has been properly parametrized (a high “gravity” setting in Force Atlas 2 tends to produce a hairball regardless of the network’s structure, and that is not a true hairball). So, if a network is properly visualized as a hairball, this does tell us something about its structure: it tells that it is pretty dense. You may find the result banal, it nevertheless discriminates between different structures, so it mediates the topology. Secondly, network layouts are bad at manifesting visual gaps, because in some sense, it does not matter to them. But they are good at placing connected nodes next to each other (on average). It is possible that nodes placed together in the pictures, i.e. local areas, have a meaning. It is possible for clusters to be present even in the absence of any gaps. You may think of it as a bunch of clay balls smashed together (figure 7): the local structures are still present, but they touch each other. Now, to be clear, not all hairballs hide such structures. But since we know they may exist, we can check for them. We may for instance reveal them by coloring clusters: if the hairball has a structure, the colors will not be mixed but gathered in coherent localities. Those clusters may be obtained from the data set (categorical node attributes) or from a community detection algorithm, for instance modularity clustering. For instance, Edge et al. (2018) claim that hairballs lack “clear separation and grouping” but in their example (figure 8 on the left), the hairball has a clear community structure, if we look at colors, despite the lack of visual gaps.

In practice, the contour of the hairball may tell about the internal clustering. In figure 9 the classic network C. Elegans (Watts and Strogatz, 1998) is spatialized by the LinLog energy model. As there are no clear gaps, we do not perceive distinct groups in the node placement (9-a) unless we add additional information, such as color (9-b). The relatively homogeneous distribution of nodes is perceived as a weirdly shaped stain (9-c). The shape of this stain mediates the topology, even in the absence of clear groups. Intuitively, some denser groups of nodes may pull the network in different directions, under the action of the algorithm. This stretches the contour in certain directions, and may create bumps and headlands in specific directions. Intuitively, those are partial clusters that create distinct localities despite being interlinked (hence the absence of visual gaps). I do not offer any proof of this statement here, but you can check, in the example below, that the clusters found by modularity maximization (colors in 9-b) match the elongation and protrusions in the contour of the network (9-c).

I propose to call these pseudo-clusters “poles”, as they tend to appear on the sides (figure 10). The lack of visual separation is meaningful: poles are not only linked, but also weakly separated. A number of nodes lie in-between the two poles, creating an ambiguous area with no clear divide. The poles themselves, however, may be sufficiently dense to be considered topological landmarks. From a clustering perspective, one may say that each pole strongly defines a weakly delineated cluster. The existence of the cluster is robust, but its limits are ambiguous. The pole itself, however, acts as a local anchor. In figure 11 the same community detection algorithm (Blondel et al., 2008) was applied to the same network (same as figure 9). I used the Gephi implementation, which is non-deterministic (Lambiotte et al., 2008). You can observe that the poles always end up in different clusters, but that the boundaries between clusters are not stable. The existence of clusters around poles is stable, but their boundaries are not. In other terms, each denser zone on the side is non-ambiguously local, but most nodes in the middle are ambiguously connected to the different poles.

As we argue in What do we see when we look at networks, the ambiguity of this middle space is a feature of the data. The absence of visual gap reflects the absence of a clear boundary in the topology. The community detection algorithms are tasked to find a boundary anyways, and react to the lack of natural gaps in the topology with a high variance in where they put the limit. From an interpretative standpoint, these boundaries do not deserve much trust, since they are poorly reproducible. Therefore, we argue, the layout is a better reduction of the topology. Indeed, it faithfully reflects the inherent ambiguity of clustering. This assumes that we know how to interpret the layout, of course. And it does not undermine the usefulness of clear-cut categories in various situations where ambiguity is a problem. Yet it is essential to realize that clusters do not exist as separated things, but as a continuous and ambiguous landscape of link density.

Now that we are equipped to understand clustering as, more generally, a matter of locality, we can start to find structures in hairballs. Although the lack of visual gaps prevents us from seeing clusters right away, we can rely instead on the subtleties of the contour and the denser zones on the borders. Hairballs may have non-obvious poles. As a test, we can run a modularity clustering a few times to check whether, and where, it is consistent. This approach reveals a community structure in some networks (figures 12 and 13) but not all (figure 14). Important note: in this visual experiment, I used the same settings for the community detection algorithm, and I used consistent colors. However, the number of clusters depends on the settings I used.

Takeaways

• We need visual gaps to see groups (Gestalt law of proximity).
• Force-directed layouts do not care about visual gaps, and may compress a community structure into a hairball. Then we do not see the structure, even though it is there.
• Force-driven layout creates localities, but it does not always make clear-cut clusters.
• Localities may be more true to the data than clear-cut clusters.
• Weakly connected clusters form poles.
• Poles can be detected by looking at elongated contours and denser areas on the sides.

References

Bennett, C., Ryall, J., Spalteholz, L. and Gooch, A. (2007) ‘The aesthetics of graph visualization’, Proceedings of the 2007 Computational Aesthetics in Graphics, Visualization, and Imaging, pp. 57–64. doi: 10.2312/COMPAESTH/COMPAESTH07/057-064.

Bertin, J. (1967) Sémiologie Graphique. Les diagrammes, les réseaux, les cartes, Paris, La Haye, Mouton, Gauthier-Villars. 2e édition : 1973, 3e édition : 1999, EHESS, Paris.

Blondel, V. D., Guillaume, J.-L., Lambiotte, R. and Lefebvre, E. (2008) ‘Fast unfolding of communities in large networks’, Journal of Statistical Mechanics: Theory and Experiment, 2008(10). doi: 10.1088/1742-5468/2008/10/P10008.

Cardon, D., Cointet, J.P., Ooghe, B. and Plique, G. (2019) Unfolding the multi-layered structure of the French mediascape.

Correa, C. D. and Ma, K.-L. (2011) ‘Visualizing Social Networks’, in Social Network Data Analytics. Boston, MA: Springer US, pp. 307–326. doi: 10.1007/978-1-4419-8462-3_11.

Dianati, N. (2016) Unwinding the hairball graph: pruning algorithms for weighted complex networks. Physical Review E, 93(1), p.012304.

Edge, D., Larson, J., Mobius, M. and White, C. (2018) December. Trimming the hairball: Edge cutting strategies for making dense graphs usable. In 2018 IEEE International Conference on Big Data (Big Data) (pp. 3951-3958). IEEE.

Kobourov, S. G., McHedlidze, T. and Vonessen, L. (2015) ‘Gestalt Principles in Graph Drawing’, in International Symposium on Graph Drawing and Network Visualization. Los Angeles: Springer, Cham, p. 13. doi: 10.1007/978-3-319-27261-0_50.

Lambiotte, R., Delvenne, J.C. and Barahona, M. (2008) Laplacian dynamics and multiscale modular structure in networks. arXiv preprint arXiv:0812.1770.

Noack, A. (2007) ‘Energy Models for Graph Clustering’, Journal of Graph Algorithms and Applications JGAA, 11(112), pp. 453–480.

Nocaj, A., Ortmann, M. and Brandes, U. (2015) ‘Untangling the Hairballs of Multi-Centered, Small-World Online Social Media Networks’, Journal of Graph Algorithms and Applications, 19(2), pp. 595–618. doi: 10.7155/jgaa.00370.

Van Den Elzen, S. and Van Wijk, J. J. (2014) ‘Multivariate network exploration and presentation: From detail to overview via selections and aggregations’, IEEE Transactions on Visualization and Computer Graphics, 20(12), pp. 2310–2319. doi: 10.1109/TVCG.2014.2346441.

Venturini, T., Jacomy, M., Bounegru, L. and Gray, J. (2018) ‘Visual Network Exploration for Data Journalists’, in Franklin, S. E. I. and B. (ed.) The Routledge Handbook to Developments in Digital Journalism Studies. Abingdon: Routledge.

Wagemans, J., Elder, J.H., Kubovy, M., Palmer, S.E., Peterson, M.A., Singh, M. and von der Heydt, R. (2012) A century of Gestalt psychology in visual perception: I. Perceptual grouping and figure–ground organization. Psychological bulletin, 138(6), p.1172.

Watts, D. and Strogatz, S. (1998) Collective dynamics of “smallworld” networks. Nature 393: 440–442.

---

---