31:T85b,md`# Distance between nodes, when using a force-directed layout Force-directed placement algorithms proceed like a physical simulation. * All nodes repulse each other like magnets * Pairs of nodes connected by an edge attract like a spring This family of algorithms always is defined by the principle of a repulsion force counterbalanced by an attraction force. Different members of the family use different equations for those forces, and have different optimizations, but the principle is the same. The goal is clear: once an equilibrium is reached, the connected nodes are closer than disconnected nodes, precisely because the attraction force is only carried by the links. Is it true though? ## Randomness in force-directed layouts This family of algorithms works step after steps to produce an approximation of an optimal placement. Finding the actual optimal placement is impossibly hard, but getting close is manageable. But there is a price to pay: these algorithms are non-deterministic. It means that: * The algorithm starts with nodes in random positions * The algorithm works step by step to improve the placement * The result after *n* steps entirely depends on the starting positions (randomized) * As a consequence, every time you run the algorithm, you have a different result ## Interpreting the distance in a layout The rationale of this family of algorithms is that it puts connected nodes closer. Does this tell us how to interpret the result? Let's take a practical example to illustrate that issue. Down below is a network rendered using [Force Atlas 2](https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0098679), an algorithm of this family. We want to interpret the image. It would be convenient to state that the placement is such that close node are connected while distant nodes are disconnected. But is it true? By looking at the image, you can already guess that it's not exactly true (a clue: look at the length of edges). If it is not true that *close = connected* and *distant = disconnected*, then what can we say *precisely* about the image? How are we supposed to interpret it? `32:T4a4,md`A few measures: * There are ${pairs_of_nodes_list.length} pairs of nodes in total and their average length is ${Math.round(d3.mean(pairs_of_nodes_list.map(d=>d.d)))} units * There are **${pairs_of_nodes_list.filter(d=>d.c).length} pairs of connected** nodes (${Math.round(100*pairs_of_nodes_list.filter(d=>d.c).length/pairs_of_nodes_list.length)}% of the pairs) and their average length is **${Math.round(d3.mean(pairs_of_nodes_list.filter(d=>d.c).map(d=>d.d)))} units** * There are ${pairs_of_nodes_list.filter(d=>!d.c).length} pairs of **disconnected** nodes (${Math.round(100*pairs_of_nodes_list.filter(d=>!d.c).length/pairs_of_nodes_list.length)}% of the pairs) and their average length is **${Math.round(d3.mean(pairs_of_nodes_list.filter(d=>!d.c).map(d=>d.d)))} units** *Note: the distance unit is arbitrary by nature.* Clearly, **the algorithm is effective** in the sense that the connected nodes are much closer on average than the disconnected nodes. *But wait, since the algorithm is non-deterministic, we may just have been lucky? Click on the button down below to re-run the layout and check if it makes a difference. It will update the figure as well as the numbers.* `33:T425,md`## Does close equal connected? If on average, connected nodes are closer, then maybe it's just because thanks to the layout, *close equals connected*. That is quite reasonable to suppose, since that is what the algorithm aims at. Unfortunately it does not seem to be that way, at least because we have long edges: pairs of connected nodes that got split apart. What is happening here? Let's break down the problem in four parts: * Does close imply connected? * Does connected imply close? * Does far imply disconnected? * Does disconnected imply far? To keep things simple, let's break the distances down in five classes, using the longest distance *L* as a landmark: * |-------------------------| Super long (80% of *L* to *L*) * |--------------------| Long (60% to 80% of *L*) * |---------------| Medium (40% to 60% of *L*) * |----------| Short (20% to 40% of *L*) * |-----| Super short (0 to 20% of *L*) How do connected and disconnected pairs distribute in these categories? `34:T98b,html`

Distance	Connected pairs	% of connected pairs	Disconnected pairs	% of disconnected pairs
Super long	${distance_breakdown['Super long'].cCount}	${distance_breakdown['Super long'].cPercent} %	${distance_breakdown['Super long'].dcCount}	${distance_breakdown['Super long'].dcPercent} %
Long	${distance_breakdown['Long'].cCount}	${distance_breakdown['Long'].cPercent} %	${distance_breakdown['Long'].dcCount}	${distance_breakdown['Long'].dcPercent} %
Medium	${distance_breakdown['Medium'].cCount}	${distance_breakdown['Medium'].cPercent} %	${distance_breakdown['Medium'].dcCount}	${distance_breakdown['Medium'].dcPercent} %
Short	${distance_breakdown['Short'].cCount}	${distance_breakdown['Short'].cPercent} %	${distance_breakdown['Short'].dcCount}	${distance_breakdown['Short'].dcPercent} %
Super short	${distance_breakdown['Super short'].cCount}	${distance_breakdown['Super short'].cPercent} %	${distance_breakdown['Super short'].dcCount}	${distance_breakdown['Super short'].dcPercent} %

`35:Tf51,md`## Understanding what happens In a force-directed placement algorithm, each pair of nodes is subject to one or two forces: * Connected pairs get attracted *and* repulsed * Disconnected pairs get just repulsed Disconnected pairs do not get extra repulsion, they just don't get the attraction. In other words, the algorithm does not put much effort into separating disconnected pairs. This strategy has been tried. Early algorithms set a long distance for disconnected pairs and a short distance for connected pairs. Then all pairs get a spring force that either repulses if the distance is too short (contracted spring) or attracts if it is too long (extended spring). The result is just very bad. In practice, it produces super cluttered placements that also sturggle to stabilize. I've tried it myself, and like the others I failed to make it work. **Why is it more efficient to allow disconnected pairs getting close?** That, my friend, is a very relevant question that no one ever asks. I don't know if an answer has been found. It leads further down the rabbit hole, and I am still wondering myself. I suppose that projecting a complex network onto only two dimensions is more of a challenge than it looks like, because it is so heavily constrained. It might have to do with the number of dimensions, but it also has to do with the Euclidian nature of that space. We have no idea, and from my point of view, people have just stopped asking. All I know is that there is a price to pay in order to have most of the connected nodes placed super close: (1) some connected pairs still have to be split apart, and (2) a number of disconnected pairs will have to be close. These two are quite inevitable, and it is quite simple to figure out why. (1) Distances in the placement are relative: you are only close or distant compared to other distances in the layout. For a group of connected nodes, being close just means *closer* together than to the rest of the network. Imagine two cliques A and B connected with a single edge (a clique is a group of nodes where each one is connected to each other one). We expect node pairs within clique A to be super close (and the same for B). But being super close means is relative, it actually means *closer* than the distance between A and B. As a consequence, the link between A and B has to be "sacrificed". In other words, a single connected pair between A and B does not matter much in the face of the many disconnected pairs between A and B. (2) Image that node A is connected to B and B to C, but not A to C. We just have a little A-B-C chain. A has to be super close to B and B to C. As a consequence, A has to be close to C, even though they are disconnected. Closeness is kind of transitive. This is a property of Euclidian space (it's called the [triangular inequality](https://en.wikipedia.org/wiki/Triangle_inequality)). It's important to note that connectedness, in a network, is *not* transitive; there is a natural conflict between the structure of the network and its projection onto a plane (or any Euclidian space, actually). ## Drawing a conclusion In a nutshell, force-directed placement seems to be good at placing *most* connected pairs super close, even though many disconnected pairs also end up super close. Therefore the best rigorous interpretation we can forge is the following: * **If two nodes are super close, they might be connected** * **If they are not, they are almost certainly disconnected** *Note: the figures we have seen hold for this particular network and layout algorithm. They are not necessarily true for very different networks (large, denser...) or algorithms. This notebook is more of an illustration. A broader benchmark is for another time.* **What next?** Now that we have a precisely formulated interpretation for the layout, we can try to quantify it and build a systematic validity measure for these statements. `36:Te1b,renderNetwork = function(){ var settings = {} // Feel free to edit following settings // Canvas size settings.width = image_size settings.height = image_size settings.offset = 20 // Margin // Drawing nodes, labels and edges settings.node_size = 0.3 settings.edge_color = 'rgba(200, 200, 200, 0.8)' // --- (end of settings) // Fix missing coordinates and/or colors addMissingVisualizationData() // Change the coordinates of the network to fit the canvas space rescaleGraphToGraphicSpace() // Paint a white background ctx.beginPath() ctx.rect(0, 0, settings.width, settings.height) ctx.fillStyle="white" ctx.fill() ctx.closePath() // Draw each edge g.edges().forEach(function(eid){ var ns = g.getNodeAttributes(g.source(eid)) var nt = g.getNodeAttributes(g.target(eid)) ctx.beginPath() ctx.lineCap="round" ctx.lineJoin="round" ctx.strokeStyle = settings.edge_color ctx.fillStyle = 'rgba(0, 0, 0, 0)'; ctx.lineWidth = settings.edge_thickness ctx.moveTo(ns.x, ns.y) ctx.lineTo(nt.x, nt.y) ctx.stroke() ctx.closePath() }) // Draw each node g.nodes().forEach(function(nid){ var n = g.getNodeAttributes(nid) ctx.beginPath() ctx.arc(n.x, n.y, settings.node_size * n.size, 0, 2 * Math.PI, false) ctx.lineWidth = 0 ctx.fillStyle = n.color ctx.shadowColor = 'transparent' ctx.fill() }) // --- // Functions function rescaleGraphToGraphicSpace() { // General barycenter resize var xbarycenter = 0 var ybarycenter = 0 var wtotal = 0 var dx var dy var ratio g.nodes().forEach(function(nid){ var n = g.getNodeAttributes(nid) // We use node size as weight (default to 1) n.size = n.size || 1 xbarycenter += n.size * n.x ybarycenter += n.size * n.y wtotal += n.size }) xbarycenter /= wtotal ybarycenter /= wtotal var dmax = 0 // Maximal distance from barycenter g.nodes().forEach(function(nid){ var n = g.getNodeAttributes(nid) var d = Math.sqrt( Math.pow(n.x - xbarycenter, 2) + Math.pow(n.y - ybarycenter, 2) ) dmax = Math.max(dmax, d) }) ratio = ( Math.min(settings.width, settings.height) ) / (2 * dmax) // Initial resize g.nodes().forEach(function(nid){ var n = g.getNodeAttributes(nid) n.x = settings.width / 2 + (n.x - xbarycenter) * ratio n.y = settings.height / 2 + (n.y - ybarycenter) * ratio //n.size *= ratio }) } function addMissingVisualizationData() { var colorIssues = 0 var coordinateIssues = 0 g.nodes().forEach(function(nid){ var n = g.getNodeAttributes(nid) if (!isNumeric(n.x) || !isNumeric(n.y)) { var c = getRandomCoordinates() n.x = c[0] n.y = c[1] coordinateIssues++ } if (!isNumeric(n.size)) { n.size = 1 } if (n.color == undefined) { n.color = '#665' colorIssues++ } }) if (coordinateIssues > 0) { alert('Note: '+coordinateIssues+' nodes had coordinate issues. We carelessly fixed them.') } function isNumeric(n) { return !isNaN(parseFloat(n)) && isFinite(n) } function getRandomCoordinates() { var candidates var d2 = Infinity while (d2 > 1) { candidates = [2 * Math.random() - 1, 2 * Math.random() - 1] d2 = candidates[0] * candidates[0] + candidates[1] * candidates[1] } var heuristicRatio = 5 * Math.sqrt(g.order) return candidates.map(function(d){return d * heuristicRatio}) } } }37:[{"id":"9dc5154f16a784b7c605a9699f43aa41566a9c86bc16e5cf779bc06149c818e1e5cd7e1a0954e2e85ebe9fcdc48a5b9f211daf2be3d9148653f9567c0d96ece5","href":"https://static.observableusercontent.com/files/9dc5154f16a784b7c605a9699f43aa41566a9c86bc16e5cf779bc06149c818e1e5cd7e1a0954e2e85ebe9fcdc48a5b9f211daf2be3d9148653f9567c0d96ece5","name":"Rio+20.gexf","type":"application/xml","lastModified":1583854505828.436,"size":549283}] 2f:{"title":"Distance between nodes, when using a force-directed layout","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":92,"value":"network_visualization = {\n const parent = DOM.element('div');\n return parent;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":535,"value":"{\n const form = html``;\n form.layoutAndRenderButton.onclick = () => {\n applyLayout();\n renderNetwork();\n }; \n \n return form;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":182,"value":"md`## Basic data on distances between nodes\nLet's start by gathering some data about the distances between the nodes.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":472,"value":"pairs_of_nodes_index = {\n graph_version;\n let p = {}\n const nlist = g.nodes()\n for (let i=0; i{\n return d\n })\n // Sort from longest to shortest\n pairs.sort(function(a,b){return b.d-a.d})\n pairs.forEach((d,i)=>{d.rank = i})\n return pairs\n})()","pinned":false,"hidden":false,"mode":"ojs"},{"id":422,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":149,"value":"{\n const form = html``;\n form.layoutAndRenderButton.onclick = () => {\n applyLayout();\n renderNetwork();\n }; \n \n return form;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":573,"value":"html`

Connected nodes are closer on average: TRUE ✔

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":592,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":613,"value":"distance_breakdown = {\n graph_version;\n let db = {};\n const L = d3.max(pairs_of_nodes_list.map(d=>d.d));\n const cTotal = pairs_of_nodes_list.filter(d=>d.c).length\n const dcTotal = pairs_of_nodes_list.filter(d=>!d.c).length\n const ranges = [\n {label:'Super long', min:0.8*L, max:L+1},\n {label:'Long', min:0.6*L, max:0.8*L},\n {label:'Medium', min:0.4*L, max:0.6*L+1},\n {label:'Short', min:0.2*L, max:0.4*L},\n {label:'Super short', min:0, max:0.2*L}\n ]\n ranges.forEach(range=>{\n const cCount = pairs_of_nodes_list\n .filter(d=>d.c)\n .filter(d=>(d.d>=range.min && d.d!d.c)\n .filter(d=>(d.d>=range.min && d.d\n

\n `;\n form.layoutAndRenderButton.onclick = () => {\n applyLayout();\n renderNetwork();\n }; \n \n return form;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":641,"value":"md`Let's start by the elephant in the room: ${distance_breakdown['Super short'].cPercent} % of connected pairs are super close. It's not *all* of them, but it's *most* of them and it's important to notice.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":583,"value":"html`

All connected nodes are very close: FALSE ✘

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":652,"value":"html`

Most connected nodes are very close: TRUE ✔

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":660,"value":"md`Now, let's look at the last line of the table. Although only ${distance_breakdown['Super short'].dcPercent} % of disconnected pairs are super close, it still represents ${distance_breakdown['Super short'].dcCount} pairs, against ${distance_breakdown['Super short'].cCount} pairs of connected nodes. That is ${Math.floor(distance_breakdown['Super short'].dcCount/distance_breakdown['Super short'].cCount)} times more, and it is simply because there are much more disconnected pairs overall.\n\nIf a pair being connected generally implies that its distance is super short, the reverse is completely false: most super close pairs are actually disconnected.\n\n**The layout does not allow us to guess which nodes are connected just by looking at their distance.** In other words, guessing connected nodes from distance has many false positives: super close but disconnected nodes.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":667,"value":"html`

Most very close nodes are connected: FALSE ✘

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":678,"value":"md`If we now look at the long distances, we see that long and super long pairs are always disconnected. And *almost* every pair of medium distance or more is disconnected.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":680,"value":"html`

Nodes that are not close are disconnected: TRUE ✔

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":684,"value":"md`But conversely, since there are close, disconnected pairs, we cannot state that disconnected nodes are distant. We can only state that most disconnected nodes are not super close (not very interesting).`","pinned":false,"hidden":false,"mode":"ojs"},{"id":686,"value":"html`

Disconnected nodes are split apart: FALSE ✘

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":690,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":6,"value":"md`

\n\n--- \n\n# Appendix\n\n*This is stuff we need to load in this notebook to make it work.*\n\n### Require Graphology stuff`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"Graph = require('graphology@0.17.1/dist/graphology.umd.min.js')","pinned":false,"hidden":false,"mode":"ojs"},{"id":718,"value":"GraphologyLibrary = require('graphology-library@0.3.0/dist/graphology-library.min.js')","pinned":false,"hidden":false,"mode":"ojs"},{"id":35,"value":"gexf = GraphologyLibrary.gexf","pinned":false,"hidden":false,"mode":"ojs"},{"id":26,"value":"layout = GraphologyLibrary.layout","pinned":false,"hidden":false,"mode":"ojs"},{"id":18,"value":"fa2 = GraphologyLibrary.layoutForceAtlas2","pinned":false,"hidden":false,"mode":"ojs"},{"id":102,"value":"md`### Require d3`","pinned":false,"hidden":false,"mode":"ojs"},{"id":104,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":256,"value":"md`### Load the network into Graphology`","pinned":false,"hidden":false,"mode":"ojs"},{"id":44,"value":"networkGEXF = FileAttachment(\"Rio+20.gexf\").text()","pinned":false,"hidden":false,"mode":"ojs"},{"id":29,"value":"g = gexf.parse(Graph, networkGEXF);","pinned":false,"hidden":false,"mode":"ojs"},{"id":515,"value":"mutable graph_version = 0; // We use the graph version to track graph changes across cells","pinned":false,"hidden":false,"mode":"ojs"},{"id":273,"value":"md`### Apply force-driven layout`","pinned":false,"hidden":false,"mode":"ojs"},{"id":8,"value":"applyLayout = function() {\n // Settings:\n let iterations = 100;\n\n let settings = {}\n\n settings.linLogMode = false\n settings.outboundAttractionDistribution = false\n settings.adjustSizes = false\n settings.edgeWeightInfluence = 0\n settings.scalingRatio = 10\n settings.strongGravityMode = true\n settings.gravity = 0.05\n settings.slowDown = 1\n settings.barnesHutOptimize = false\n settings.barnesHutTheta = 0.5\n\n // Applying a random layout before starting\n layout.random.assign(g);\n\n // Applying FA2\n fa2.assign(g, {iterations: iterations, settings: settings});\n \n mutable graph_version++ // We use this to track the changes of the graph across the notebook\n}\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":278,"value":"md`### Render network visualization`","pinned":false,"hidden":false,"mode":"ojs"},{"id":128,"value":"image_size = 500","pinned":false,"hidden":false,"mode":"ojs"},{"id":95,"value":"canvas = { \n return d3.select(network_visualization).append(\"canvas\")\n .attr('width', image_size)\n .attr('height', image_size)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":121,"value":"ctx = {\n return canvas.node().getContext('2d');\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":116,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":541,"value":"md`### Initialization`","pinned":false,"hidden":false,"mode":"ojs"},{"id":542,"value":"{\n // Init\n applyLayout();\n renderNetwork();\n}","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W37","stdlib":"1","titling":"auto"}