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.

Figure 1. A homogeneous distribution of dots can be perceived as a group with a given shape. These shapes may be ambiguous, and get perceived differently by different persons.

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.

Figure 2. A same set of three groups of dots may be perceived as one group if they are close enough.

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.

Figure 3. A visual intuition of the disagreement between the algorithm and the eye. Human vision looks at borders, while the algorithm cares about barycentres.

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 Pin. For nodes in different groups, I will use a probability Pout. As long as Pin is bigger than Pout, each group is promised to be a cluster in a topological sense (e.g. modularity). I choose Pin and Pout so that Pin is smaller, and the sum equals 100%. When Pin is large, the clusters are well-defined. When Pin is 50%, the community structure has entirely disappeared and we just have a random network (indeed Pin = Pout = 50%).

I generate a series of networks with a decreasing probability Pin (figure 4). As expected, the most separated groups topologically (Pin high) are the most separated visually. As Pin 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.

Figure 4. Planted partition networks: nodes in the same group have Pin chances to be connected, nodes in different groups, Pout. Each group has a distinct color. The most separated groups topologically are also the most separated visually. But when Pin is low, the node placement does not display a gap. Layout: Force Atlas 2, default settings.

You may think that at a Pin 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.

Figure 5. Planted partition networks with Pin= 60%. Layout: Force Atlas 2, default settings.

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 Pin=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.

Figure 6. Six of these networks are planted partitions with Pin = 60%, and six are random networks with a connection probability of 50%. Layout: Force Atlas 2, default settings.
Answer: the random networks are, in reading order, 3 to 5 and 7 to 9.

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.

Figure 7. A metaphor for hairball networks: there may be clusters, but they are smashed together like plastic clay balls.
Figure 8. From left to right, the pruning of hairballs, using the layout Force Atlas 2, as illustrated in Edge et al. (2018, figure 2). “How skeletal community structure emerges from an initial ‘hairball’ graph.”

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).

Figure 9. The neural network of C. Elegans (Watts and Strogatz, 1998) spatialized by the LinLog energy model. (a) No color: no clear gaps allow to separate groups visually: it can be considered a hairball. (b) Nodes colored by modularity clustering (modularity = 0.346). Three homogeneous areas appear, showing a locality principle. (c) Poles and elongation highlighted. Intuitively, the modularity clusters correspond to the ends of the shape that pull it apart.

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.

Figure 10. Poles are weakly separated clusters that one can detect by looking at denser areas on the sides of a network spatialized by a force-driven algorithm.
Figure 11. Six renditions of the same community detection algorithm. The poles consistently end up in different clusters, but the boundaries are not stable. Note: one rendition found 4 clusters, contrary to the others. Network: C. Elegans spatialized by LinLog.

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.

Figure 12. The hairball network from Venturini et al. (2018), spatialized by Force Atlas 2, with different renditions of a community detection algorithm. The same clusters appear consistently but their boundaries are not consistent.
Figure 13. The hairball network from Cardon et al. (2019), spatialized with the LinLog energy model, with different renditions of a community detection algorithm. The same clusters appear consistently but their boundaries are not consistent.
Figure 14. A random network (500 nodes, 5% chances of connection) spatialized by Force Atlas 2, with different renditions of a community detection algorithm. Found clusters do not map specific areas, and do not characterize the same nodes consistently.

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.


2 thoughts on “Hidden structures in hairballs, and how to see them”

  1. Thank you very much for this interesting article! I’m planning to do a network for my PhD thesis and I was wondering what I’m gonna do with those hairballs and how to separate them. Aside from the theoretical part I would be interested in which program you are using for your analysis?

    Best wishes,
    Kate

    1. Hi, for my analysis I mostly use Gephi, and for custom things I also use scripts on Graph Recipes. https://medialab.github.io/graph-recipes/#!/upload
      If you want to remove some edges to minimize the hairball effect, you can try sparsification methods, for instance clique percolation or Simmelian backbone. Then you will probably need another tool than Gephi.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.