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 [22]. The expected visual pattern mainly consists of visually separated aggregates of dots, that one interprets as clusters or communities, i.e. densely connected sets of nodes. In practice, one rarely sees a cluster if it does not exist in the topology (although we do not assess that statement here). And one tends to assume that conversely, if a cluster exists in the graph topology, it is necessarily visible in the layout. In this paper, we argue that this assumption can be wrong in common situations. We find that a common topological cluster pattern could often get mediated differently from the compact aggregate of dots one generally expects, for instance as a bridge (Figure 1). In short, some clusters can be dense enough to be consistently picked up by common clustering techniques, yet not dense enough to be displayed as visual aggregates by common layout techniques.
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 section 3 we 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 maximization [3,12,21] have become a staple of visual network analysis, it is notably because the retrieved communities closely match the visual clusters produced by force-driven algorithms. This result was voiced by Noack as "modularity clustering is a force-directed layout" [14].
Noack formalized graph drawing as an optimization problem about the "separation of communities" [14]. In this mental model, graphs are imagined as communities connected by bridges. On a practical level, using force-directed layouts and community detection algorithms to analyze networks reinforces the notion that a network's community structure solely consists of clusters connected by bridges (Figure 2). Indeed, the visualizations produced in popular tools like Cytoscape [19] Gephi [1] or NodeXL [20] often feature separated groups of nodes (seen as clusters) connected by edges or chains of edges (bridges). In this context, it is most reasonable to assume that a node is either part of a cluster, of a bridge, or neither.
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 [10,18], sometimes made of edges [7], but rarely as a mix of both; yet such structures can effectively be an important part of the community structure. Intuitively, very dense clusters may be connected by less dense clusters.
The notion of community structure has multiple definitions [16], meanings [6], computational commitments [5,17] and visual representations [2,22]. In the next section, we report on a real-world case where the community structure has richer patterns than the cluster/bridge dichotomy. It shows that the nuance and complexity of a network's structure can be lost in the translation enacted by the layout, notably when some "communities" get represented as visually non-compact shapes.
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 paper [11]. 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 [4]. Through clique percolation [15] with π = 7 we uncovered 166 clusters corresponding to various topics or semantic fields. We rendered the graph as a network map using the layout algorithm LinLog [13] using the Force Atlas 2 implementation [9]. In order to annotate the network map and use it as a discussion elicitation device with our project partners, we underwent the following task: for each cluster, sample the most representative documents, read them, and produce a short summary of the purpose and agency of AI and algorithms in those publications [11].
The network obtained has a blatant community structure, and at first glance, seems to consist of clusters connected by bridges (Figure 3).
Issue at stake: Our annotation task demanded us to explain visible clusters, as rendered by the layout algorithm, while we had computed topological 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, one should 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.
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 of π = 7 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 (Figure 4).
However, this approach had a significant drawback: π was too low to break the bigger and denser clusters down to subclusters (Figure 5). In the most extreme case, one of the retrieved clusters contained the 31% 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 method [21] for the convenience of its resolution setting. Sub-issue 2: clusters not looking like clusters. Some clusters were not only too big, but 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 Figure 5 seemed to contain a mix of clusters and bridges, which appears more clearly if we isolate it from the rest (Figure 6-A). It is not compact, but extremely spiky. Yet from the method, its topology satisfies the same criterion as the well-behaved cluster of Figure 4: each 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 (Figure 6-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 (Figure 7). 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 difference being that compact clusters got attached to a landmark point while the title of bridge clusters followed the contour of the connection (Figure 8).
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 kind (25%): 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 about renewable energy storage, and it connected the topics of renewable energy and power distribution with those of smart grids and lithium-ion batteries, which makes a lot of sense. Other examples included scanning for cancer bridging scanners with cancer research; or language bridging text 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 Figure 1.
The method works for any clique size π set in advance. It generates an arbitrarily large graph such that clique percolation using said π will 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 than π. Generate a "stretching" [8] by stacking as many cliques of size π as desired, as shown in Figure 9. Merge π β 2 nodes from the first clique with as many of the first stacked clique of the stretching; similarly merge π β 2 nodes of the second clique with the last stacked clique of the stretching. More details in the reference implementation (Python). In the example of Figure 1, 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 of π β 2 creates a bottleneck that prevents clique percolation from joining the stretching with either clique, because it is smaller than the minimum overlap of π β 1 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 level π. Second, 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 [13,9]; see also [22]). The clusters we see but cannot retrieve by computational means are the false positives, responsible for the task's precision, which we assume as generally good (or at least, it is not the focus of this paper). Conversely, the clusters that do not look like a compact group of dots and remain undetected are the false negatives responsible for the recall (Figure 10).
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.