Force-directed node placement algorithms, a popular technique to visualise networks, are known to optimize “cluster separability”: when sets of densely connected nodes get represented as well-separated groups of dots. Using these techniques leads us to conceive networks as sets of clusters connected by bridges. This is also how we tend to think of the “community structure” model embedded in clustering techniques like modularity maximization. Yet this mental model has flaws. We specifically address the notion that clusters (“communities”) necessarily look like groups of dots, through the mediation of a node placement algorithm. Although often true, we provide a reproducible counterexample: topological clusters that look like bridges. First, we present an empirical case that we encountered in a real world situation, while mapping the academic landscape of AI and algorithms. Second, we show how to generate a network of arbitrary size where a cluster looks like a bridge. In conclusion, we open a discussion about layout algorithms as a visual mediation of a network's community structure. We contend that when it comes to the accuracy of retrieving clusters visually, node placement algorithms have an imperfect recall despite an excellent precision.
The purpose of drawing a large graph (a.k.a. making a network map) is generally to
mediate its topological features. One aims to produce visual patterns providing insights about its
community structure 2[
In section 2 we report our observations from a real-world situation where we find such clusters in a co-occurrence network about AI and algorithms in science. In sect3iowne draw on those observation to build a procedure to generate clusters that look like bridges. We conclude by framing this issue as an accuracy problem for the task of retrieving clusters visually, more specifically as a recall issue.
If community detection techniques like modularity maximizatio3n, [
Noack formalized graph drawing as an optimization problem about the “separation of
communities” [
In this implicit mental model, the macro-structure is nested and graph-like: clusters play
the role of nodes, and bridges that of edges. Yet as it turns out, relevant patterns in graphs are
not limited to the cluster/bridge dichotomy. We generally consider bridges as made of nodes
[
The notion of community structure has multiple definitions1[
Description of the case: We generated this network by extracting expressions co-occurring in the abstract or title of academic articles mentioning AI, algorithms, or machine learning. Our motivation was to map what algorithms were doing in science. We present our full methodology and our statistical analysis of the corpus in another pape1r1][.
This network’s 7,562 nodes represent the most frequent expressions in our corpus, such as
“encrypted”, “image denoising”, or “CNNs”. Each of the 85,215 edges represents a co-occurrence
of connected expressions with a sufÏciently high pointwise mutual information (PMI) score [
The network obtained has a blatant community structure, and at first glance, seems to consist of clusters connected by bridges (Figur3e).
Issue at stake: Our annotation task demanded us to explaivnisible clusters, as rendered by the layout algorithm, while we had computetdopological clusters through clique percolation. To our surprise, we faced many mismatches: some computed clusters did not look like groups of dots in the network map, or conversely, some clearly visible clusters were not captured by the clique percolation process.
One may think that when there is a mismatch between computed and visualized clusters, the computation should always take precedence over the visual, because it is more true to the data (then the mismatch would not be an issue). But that perspective fails to account for the purpose of annotation, which is to provide a context for the visible patterns. One cannot annotate a pattern that is not visible, even if it exists in the data; and conversely, onsheould annotate the artifacts of the method, i.e. anti-patterns that are visible but do not exist in the data (precisely to mark them as artifacts).
As soon as a visualization is used, even for exploratory data analysis, accounting for what it makes visible becomes a methodological necessity.
Sub-issue 1: granularity level. To retrieve clusters we used clique percolation as we did not need to annotate the entire network (only dense areas). We picked a clique size =of7 because it was low enough to capture the smallest relevant clusters. In many cases, this approach worked: the cluster retrieved looked like what one expects (Fig4u)r.e
However, this approach had a significant drawback: was too low to break the bigger and denser clusters down to subclusters (Figu5r)e. In the most extreme case, one of the retrieved clusters contained th3e1% of the nodes (the entire semantic field related to health and medicine).
Large computed clusters were an issue because they contained multiple smaller visual clusters. However, this issue was easy to address by subdividing them until we reached the desired granularity. We chose the modularity maximization by the Leiden metho2d1][for the convenience of its resolution setting.
also contained non-compact structures, such as bridges. We could not solve that issue, and had to live with the trouble. For instance, the recalcitrant cluster of Fig5usreeemed to contain a mix of clusters and bridges, which appears more clearly if we isolate it from the rest (Fi6g-ure A). It is not compact, but extremely spiky. Yet from the method, its topology satisfies the same criterion as the well-behaved cluster of Figu4r:eeach node has at least 6 fully interconnected neighbors in the cluster.
The spikiness is partly due to how this cluster is interconnected with the rest of the map, and partly due to its internal structure. We can observe it by applying the same layout to the isolated network (Figur6e-B): although the layout is less spiky and more compact, it remains very elongated. Even when we repeat this process recursively, many clusters keep resisting and refuse to become compact unless we tear them down to confetti (Figu7r)e.
We had to accept that some clusters are dense enough to be captured by community detection (both clique percolation and modularity clustering) yet not dense enough to look like compact shapes on the map. Many of those clusters looked like bridges, stretching between compact clusters. We ultimately decided to annotate the compact clusters and the bridge clusters the same way, the only diference being that compact clusters got attached to a landmark point while the title of bridge clusters followed the contour of the connection (Fi8g)u.re Takeaways from the case. By splitting initial clusters to the desired granularity, we settled on 235 sub-clusters to annotate. Of those, 58 were of the bridge kin2d5(%): at least in this case, bridge-looking clusters are not a marginal phenomenon.
We also observed that those bridges were straightforward to explain. The main bridge in our recalcitrant cluster was aboruetnewable energy storage, and it connected the topics ofrenewable energy and power distribution with those ofsmart grids and lithium-ion batteries, which makes a lot of sense. Other examples includesdcanning for cancer bridgingscanners with cancer research; orlanguage bridgingtext analysis with speech recognition; etc.
Drawing on these observations, we devised a method to generate clusters that look like bridges. An example is shown in Figure1. Criteria satisfied: The method works for any clique size set in advance. It generates an arbitrarily large graph such that clique percolation using sawidill find exactly 3 clusters, one of which will look like a bridge (it get represented as a visually non-compact set of dots spread out between the two other clusters).
Our tests show that modularity clustering by the Louvain and Leiden methods will also find 3 clusters, although it depends on the resolution used (we cannot guarantee the result as those algorithms are not deterministic). However, the result for clique percolation is granted by design of the method.
Method: Generate two cliques of a size significantly greater tha n . Generate a “stretching”
[
In the example of Figure1, we used = 100 ; the cliques had 500 nodes and the stretching stacked 400 cliques.
Why it works: Each clique will be retrieved by clique percolation because its size is greater than . The stretching will be retrieved because it satisfies clique percolation by construction. However, the merge o f− 2 creates a bottleneck that prevents clique percolation from joining the stretching with either clique, because it is smaller than the minimum overlap−o1f nodes required.
The stretching will look like a bridge for the same two reasons we mentioned in our observations. First, it is less compact than a clique by design; in fact, it is just compact enough to satisfy the criterion of clique percolation at the decided le v.elSecond, it gets pulled in two opposite directions by the cliques, whose mutual repulsion is dominating the balance of forces in the layout.
The situation can be reformulated as an accuracy problem for the task of retrieving clusters
visually, which is the purpose of force-directed layout algorithms as formalized by their authors
(for instance [
We presented an empirical case where clusters retrieved from modularity clustering did not always look like the compact groups of dots we usually expect. Building on our observations, we built a method to generate clusters that look like bridges: satisfying the criterion of clique percolation for an arbitrary clique size, yet looking like bridges stretched between compact clusters when visualized by a force-directed layout. We do not provide evidence about the pervasiveness of these visually non-compact clusters, but our generation method shows that the conditions for their emergence are commonplace in the context of large graphs with a community structure.
The existence of bridge-like clusters creates a recall issue for the task of retrieving clusters visually from a force-directed layout, even when the precision is good: unbeknownst to the visualization’s reader, some clusters may remain unseen. Being aware of that possibility is an important insight for the researchers and experts using network maps to explore relational data.