2e:null 2f:["$","title",null,{"children":"A validity metric for interpreting distances in a network map | Mathieu Jacomy | Observable"}] 34:T16bc,{ // This is a modified version of the routine in the appendix const _draw = function(_g, _settings, _D, indicators){ // SETTINGS let settings = _settings || {}; // Note: all sizes except canvas size are based on a 1000px x 1000px canvas // (this allows resizing the whole thing without losing tuning) // // 👇 Default values settings.size = settings.size || 300; settings.node_size = settings.node_size || 0.5; settings.edge_thickness = 5 let D = _D; // Create canvas const canvas = document.createElement('canvas'); canvas.width = settings.size; canvas.height = settings.size; const ctx = canvas.getContext('2d'); // Clone network, so that we do not modify the original let g = _g.copy() // 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.size, settings.size) ctx.fillStyle="white" ctx.fill() ctx.closePath() // Scale canvas ctx.scale(settings.size/1000, settings.size/1000) // Draw each edge ctx.lineCap="round"; ctx.lineJoin="round"; ctx.fillStyle = 'rgba(0, 0, 0, 0)'; ctx.lineWidth = settings.edge_thickness; g.edges().forEach(function(eid){ const ns = g.getNodeAttributes(g.source(eid)); const nt = g.getNodeAttributes(g.target(eid)); const d = Math.sqrt(Math.pow(ns.x-nt.x, 2)+Math.pow(ns.y-nt.y, 2)) if (d<=D) { ctx.strokeStyle = 'rgba(96, 168, 98, 0.8)'; } else { ctx.strokeStyle = 'rgba(229, 120, 114, 0.8)'; } ctx.beginPath(); ctx.moveTo(ns.x, ns.y); ctx.lineTo(nt.x, nt.y); ctx.stroke(); ctx.closePath(); }); // Draw each node ctx.lineWidth = 0; ctx.shadowColor = 'transparent'; g.nodes().forEach(function(nid){ const n = g.getNodeAttributes(nid); ctx.beginPath(); ctx.arc(n.x, n.y, settings.node_size * n.size, 0, 2 * Math.PI, false); ctx.fillStyle = n.color; ctx.fill(); ctx.closePath(); }); // Draw the distance circle (diameter = D) ctx.strokeStyle = '#000'; ctx.fillStyle = 'rgba(0, 255, 0, 0.1)'; ctx.lineWidth = 5; ctx.beginPath(); ctx.arc( 10 + 0.5*D, 1000 - (10 + 0.5*D), 0.5*D, 0, 2 * Math.PI ); ctx.stroke(); ctx.fill(); ctx.closePath(); // Draw distance circle label const cl_txt = indicators.P+" % of connected nodes are close enough to fit in there"; const cl_x = 10 + D + 10; const cl_y = 1000 - (10 + 0.5*D) + 8; ctx.font = "400 24px sans-serif"; ctx.lineWidth = 12; ctx.fillStyle = '#FFFFFF'; ctx.strokeStyle = '#FFFFFF'; ctx.fillText( cl_txt, cl_x, cl_y ); ctx.strokeText( cl_txt, cl_x, cl_y ); ctx.lineWidth = 0; ctx.fillStyle = '#000'; ctx.fillText( cl_txt, cl_x, cl_y ); // Reset current transformation matrix to the identity matrix ctx.setTransform(1, 0, 0, 1, 0, 0); // Functions function rescaleGraphToGraphicSpace() { const referenceSize = 1000; // General barycenter resize let xbarycenter = 0; let ybarycenter = 0; let wtotal = 0; let dx; let dy; let ratio; g.nodes().forEach(function(nid){ let 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 = referenceSize / (2 * dmax); // Resize g.nodes().forEach(function(nid){ let n = g.getNodeAttributes(nid); n.x = referenceSize / 2 + (n.x - xbarycenter) * ratio; n.y = referenceSize / 2 + (n.y - ybarycenter) * ratio; n.size *= ratio; }) D *= ratio; } function addMissingVisualizationData() { let colorIssues = 0; let coordinateIssues = 0; g.nodes().forEach(function(nid){ let n = g.getNodeAttributes(nid); if (!isNumeric(n.x) || !isNumeric(n.y)) { const 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) { console.warn('Note: '+coordinateIssues+' nodes had coordinate issues. We carelessly fixed them.'); } function isNumeric(n) { return !isNaN(parseFloat(n)) && isFinite(n); } function getRandomCoordinates() { let candidates; let d2 = Infinity; const heuristicRatio = 5 * Math.sqrt(g.order); while (d2 > 1) { candidates = [2 * Math.random() - 1, 2 * Math.random() - 1]; d2 = candidates[0] * candidates[0] + candidates[1] * candidates[1]; } return candidates.map(function(d){return d * heuristicRatio}); } } // Return result return { canvas, ctx }; } return _draw( g, {size: 500}, D, indicators, graph_version ).canvas }35:T6ad,computeIndicators = function(D,g){ const connected_pairs = pairs_of_nodes_list.filter(d=>d.c) const total_of_connected_pairs = connected_pairs.length const connected_pairs_below_D = connected_pairs.filter(d=>d.d<=D) const count_of_connected_pairs_below_D = connected_pairs_below_D.length const disconnected_pairs = pairs_of_nodes_list.filter(d=>!d.c) const disconnected_pairs_below_D = disconnected_pairs.filter(d=>d.d<=D) const count_of_disconnected_pairs_below_D = disconnected_pairs_below_D.length const total_of_pairs_below_D = count_of_connected_pairs_below_D + count_of_disconnected_pairs_below_D const total_of_all_pairs = pairs_of_nodes_list.length // Percentage of connected nodes below D const P = Math.floor(10000*count_of_connected_pairs_below_D/total_of_connected_pairs)/100 // False positive error (of interpreting D as a threshold under which all pairs are connected) const E = Math.floor(10000*(1-count_of_connected_pairs_below_D/total_of_pairs_below_D))/100 // Chances that a pair below D is connected (note: E+C=100%) const C = Math.floor(10000*(count_of_connected_pairs_below_D/total_of_pairs_below_D))/100 // Percentage of all pairs below D const P_all = Math.floor(10000*total_of_pairs_below_D/total_of_all_pairs)/100 // Quality measure, looking at how many connected pairs we grasp above expected const ratio_of_connected_pairs = total_of_connected_pairs / total_of_all_pairs const expected_count_of_connected_pairs_below_D = Math.round(total_of_pairs_below_D*ratio_of_connected_pairs) const Q = count_of_connected_pairs_below_D - expected_count_of_connected_pairs_below_D return { P, E, C, P_all, Q } }36:T88c,md`## Conclusion There is a specific distance *D_Q* that optimizes the metric *Q*. *D_Q* is a distance that captures the most edges compared to expectations, when we look at pairs of nodes defined by being closer. ** The *D_Q* distance is characteristic of the layout.** I propose to call it as such, the "characteristic distance of the layout". It represents the scale at which the layout succeeds the most, and where it is the most interpretable. It characterizes the layout, i.e. the placement of the nodes; not the graph itself and its topology. The same way we defined *D_Q*, we can define *P_Q*: the percentage of connected pairs captured by the characteristic distance *D_Q*. ** *P_Q* is a validity metric of the layout.** It represents how many edges it can capture at its best. If *P_Q* is low, it means that no distance allows to capture a significant amount of connections (that "significant amount" is, in fact, *Q*). If it is high, it means that *at least at the characteristic scale D_Q* the layout means something: it means that *D_Q* captures most edges - and we know what "most" means: *P_Q*. ### Using the validity metric in practice From a design standpoint (algorithm design indeed), a number of things matter: * The characteristic distance *D_Q* has no meaning out of the context of the network layout. Its place is **drawn within the map**, as a scale would be. * The metric itself is not *D_Q* but *P_Q*. That number must be featured close to where *D_Q* is drawn. * The symbols I used here are not very important, but the names in plain English matter. Let's pick them carefully (I'm not sure I am there yet) * As a percentage, *P_Q* is quite easy to understand; but what it represents is far from obvious. The formulation is super important. * We know that it is crucial to avoid the pitfall of interpreting *P_Q* as "percentage of connected pairs under the characteristic distance", because that is very, very false. One way to put it is to also indicate the actual figure. ### Example `37:T1089,drawNetwork = (_g, _settings) => { // SETTINGS let settings = _settings || {}; // Note: all sizes except canvas size are based on a 1000px x 1000px canvas // (this allows resizing the whole thing without losing tuning) // // 👇 Default values settings.size = settings.size || 300; settings.node_size = settings.node_size || 0.5; settings.edge_color = settings.edge_color || 'rgba(150, 150, 150, 0.8)'; // Create canvas const canvas = document.createElement('canvas'); canvas.width = settings.size; canvas.height = settings.size; const ctx = canvas.getContext('2d'); // Clone network, so that we do not modify the original const g = _g.copy(); // Prepare network data addMissingVisualizationData(); rescaleGraphToGraphicSpace(); // Paint a white background ctx.fillStyle="white"; ctx.beginPath(); ctx.rect(0, 0, settings.size, settings.size); ctx.fill(); ctx.closePath(); // Scale canvas ctx.scale(settings.size/1000, settings.size/1000); // Draw each edge ctx.lineCap="round"; ctx.lineJoin="round"; ctx.strokeStyle = settings.edge_color; ctx.fillStyle = 'rgba(0, 0, 0, 0)'; ctx.lineWidth = settings.edge_thickness; g.edges().forEach(function(eid){ const ns = g.getNodeAttributes(g.source(eid)); const nt = g.getNodeAttributes(g.target(eid)); ctx.beginPath(); ctx.moveTo(ns.x, ns.y); ctx.lineTo(nt.x, nt.y); ctx.stroke(); ctx.closePath(); }); // Draw each node ctx.lineWidth = 0; ctx.shadowColor = 'transparent'; g.nodes().forEach(function(nid){ const n = g.getNodeAttributes(nid); ctx.beginPath(); ctx.arc(n.x, n.y, settings.node_size * n.size, 0, 2 * Math.PI, false); ctx.fillStyle = n.color; ctx.fill(); ctx.closePath(); }); // Reset current transformation matrix to the identity matrix ctx.setTransform(1, 0, 0, 1, 0, 0); // Functions function rescaleGraphToGraphicSpace() { const referenceSize = 1000; // General barycenter resize let xbarycenter = 0; let ybarycenter = 0; let wtotal = 0; let dx; let dy; let ratio; g.nodes().forEach(function(nid){ let 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 = referenceSize / (2 * dmax); // Resize g.nodes().forEach(function(nid){ let n = g.getNodeAttributes(nid); n.x = referenceSize / 2 + (n.x - xbarycenter) * ratio; n.y = referenceSize / 2 + (n.y - ybarycenter) * ratio; n.size *= ratio; }) } function addMissingVisualizationData() { let colorIssues = 0; let coordinateIssues = 0; g.nodes().forEach(function(nid){ let n = g.getNodeAttributes(nid); if (!isNumeric(n.x) || !isNumeric(n.y)) { const 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) { console.warn('Note: '+coordinateIssues+' nodes had coordinate issues. We carelessly fixed them.'); } function isNumeric(n) { return !isNaN(parseFloat(n)) && isFinite(n); } function getRandomCoordinates() { let candidates; let d2 = Infinity; const heuristicRatio = 5 * Math.sqrt(g.order); while (d2 > 1) { candidates = [2 * Math.random() - 1, 2 * Math.random() - 1]; d2 = candidates[0] * candidates[0] + candidates[1] * candidates[1]; } return candidates.map(function(d){return d * heuristicRatio}); } } // Return result return { canvas, ctx }; }38:[{"id":"9dc5154f16a784b7c605a9699f43aa41566a9c86bc16e5cf779bc06149c818e1e5cd7e1a0954e2e85ebe9fcdc48a5b9f211daf2be3d9148653f9567c0d96ece5","href":"https://static.observableusercontent.com/files/9dc5154f16a784b7c605a9699f43aa41566a9c86bc16e5cf779bc06149c818e1e5cd7e1a0954e2e85ebe9fcdc48a5b9f211daf2be3d9148653f9567c0d96ece5","name":"Rio+20.gexf","type":"application/xml","lastModified":1583918018307.441,"size":549283}] 32:{"id":"a27aabb1a0d2bf02","slug":"a-validity-metric-for-interpreting-distances-in-a-network-m","title":"A validity metric for interpreting distances in a network map","thumbnail":"e9f18fa177076d3ce8c7d2674d6e6c9efe78623046b1768c00c5d7b2fe94a03e","access_level":"public","create_time":"$D2020-03-11T08:16:05.292Z","update_time":"$D2020-05-11T17:59:51.148Z","view_time":null,"first_public_time":"$D2020-03-11T19:52:30.824Z","has_unpublished_edits":null,"fork":false,"stars":14,"starred":false,"owner":{"type":"team","id":"314a0a5985c09d6c","login":"jacomyma","name":"Mathieu Jacomy","avatar_url":"https://avatars-next.observableusercontent.com/4496a2bc190392af306e4fcc2cc12dec9fe2acc458657e9bb35aecbeb5322d71","tier":"starter_2024"},"version":844,"publish_version":844,"role":null,"authored":false,"authors":[{"type":"individual","id":"5877bce6260ce3ea","login":"jacomyma","name":"Mathieu Jacomy","avatar_url":"https://avatars-next.observableusercontent.com/4496a2bc190392af306e4fcc2cc12dec9fe2acc458657e9bb35aecbeb5322d71","tier":null}],"members":[{"type":"individual","id":"5877bce6260ce3ea","login":"jacomyma","name":"Mathieu Jacomy","avatar_url":"https://avatars-next.observableusercontent.com/4496a2bc190392af306e4fcc2cc12dec9fe2acc458657e9bb35aecbeb5322d71","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":5,"collection":{"id":"e33184b07af44a70","slug":"quest-for-connected-closeness","title":"Quest for connected-closeness","owner":{"id":"314a0a5985c09d6c","login":"jacomyma","name":"Mathieu Jacomy"}},"type":"notebook","body":{"title":"A validity metric for interpreting distances in a network map","cells":[{"id":823,"value":"md`# A validity metric for interpreting distances in a network map`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":819,"value":"md`***This notebook is part of a [series](https://observablehq.com/collection/@jacomyma/quest-for-connected-closeness) that retraces my quest for a metric capable of evaluating network maps. You may want to check or the final result, [connected-closeness](https://observablehq.com/@jacomyma/highlights-on-connected-closeness).***`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":0,"value":"md`\nWe have seen [in another notebook](https://observablehq.com/@jacomyma/distance-between-nodes-when-using-a-force-directed-layout) that in the network map we were visualizing, the best rigorous interpretation we can come up with is the following:\n* If two nodes are *super close*, they might be connected\n* If they are not, they are *almost certainly* disconnected\n\nWhat do \"super close\" and \"almost certainly\" mean? Our goal is now to propose a practical, quantitative metric for those notions. I aim at a template such as:\n\n***P* % of connected nodes are closer than *D*.**\n* *P* is a high percentage, such as 95%\n* *D* is a threshold distance\n\nThis formulation is problematic from the point of view of someone who interprets the map, but I will address that issue later on. For the moment I focus on finding *P* and *D*. Of course, they depend of each other: the longer *D*, the higher *P*. Let's take a look in practice.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":21,"value":"md`## Plotting the distances in the network map\nThis is a network map using [Force Atlas 2](https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0098679), a force-directed placement algorithm.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":62,"value":"{\n return drawNetwork(\n g,\n { // Settings\n size: 500\n },\n graph_version\n ).canvas\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":102,"value":"{\n const form = html``;\n form.layoutAndRenderButton.onclick = () => {\n applyLayout(g);\n }; \n \n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":147,"value":"md`Like previously, let's visualize the distribution of all pairs of nodes, and then connected pairs specifically.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":150,"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":403,"value":"vl.markBar()\n .data(pairs_of_nodes_list)\n .encode(\n vl.x()\n .fieldQ('d')\n .bin({maxbins: 30})\n .title('Distance in the map'),\n vl.y().count().title('Count of nodes pairs')\n )\n .title('Distribution of all node pairs')\n .width(600)\n .height(120)\n .render()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":312,"value":"vl.markBar()\n .data(pairs_of_nodes_list.filter(d=>d.c))\n .encode(\n vl.x()\n .fieldQ('d')\n .bin({maxbins: 30})\n .title('Distance in the map'),\n vl.y().count().title('Count of connected nodes pairs')\n )\n .title('Distribution of pairs of CONNECTED nodes')\n .width(600)\n .height(120)\n .render()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":420,"value":"{\n const form = html``;\n form.layoutAndRenderButton.onclick = () => {\n applyLayout(g);\n }; \n \n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":417,"value":"md`Of course this distribution depends on the result of the layout; click on the button to check. But as you can see, it does not change much:\n* The connected pairs seem to be massively contained in below 400 length units\n* But of course, that range also catches a massive part of the non-connected edges\n\nTake a try at finding a good threshold distance *D* by using the slider down below (after the map).\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":514,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":430,"value":"html`\nD\n${viewof D.bind(html``)}\n${viewof D.bind(html``)}\n
\nThreshold distance for the validity metric\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":482,"value":"{\n indicators;\n return md`\n* ** *P* = ${indicators.P} %** (Percentage of connected nodes below D)\n* ** *E* = ${indicators.E} %** (Error in false positives)\n* ** *P_all* = ${indicators.P_all} %** (Percentage of pairs below D)\n* ** *Q* = ${indicators.Q}** (Connected pairs below D above expected)\n`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":448,"value":"indicators = computeIndicators(D,g)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":623,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":478,"value":"md`\n** *E* represents the proportion of disconnected pairs among pairs of nodes closer than *D*.** It represents how wrong it is to believe that *\"close=connected\"*, to believe that *D* represents the limit under which *P* percent of nodes are connected. We want E as low as possible.\n\nNote: *P* does NOT represent how many pairs below *D* are connected. It represents how many *of the connected pairs* are under *D*. That is very different (check [this notebook](https://observablehq.com/@jacomyma/distance-between-nodes-when-using-a-force-directed-layout) for a practical illustration).\n\n** *P_all* represents how many of the pairs of nodes are present below *D* overall.** It matters insofar as having 99% of connected nodes below *D* is not impressive if we also have 99% of all pairs. We want *P_all* as low as possible.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":615,"value":"md`## Plotting indicators\nWhat happens if we plot the indicators for all possible distances *D*?\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":618,"value":"indicators_data = {\n const distances = d3.scaleLinear()\n .domain(d3.extent(pairs_of_nodes_list, d=>d.d))\n .nice()\n .ticks(50)\n \n let data = distances.map(D=>{\n const i = computeIndicators(D, g)\n return {\n D,\n E: i.E,\n P: i.P,\n P_all: i.P_all,\n Q: i.Q\n }\n })\n \n // Normalize Q to 100 max (for scale coherence)\n const Qmax = d3.max(data, d=>d.Q)\n data.forEach(d=>{\n d.Q = 100 * d.Q / Qmax\n })\n \n return data\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":639,"value":"{\n indicators_data;\n \n const P = vl.markLine({interpolate: 'monotone', stroke: 'black'})\n .encode(\n vl.x().fieldQ('D'),\n vl.y().fieldQ('P').title('P (BLACK)'),\n );\n \n const E = vl.markLine({interpolate: 'monotone', stroke: 'red'})\n .encode(\n vl.x().fieldQ('D'),\n vl.y().fieldQ('E').title('E (RED)'),\n );\n \n const P_all = vl.markLine({interpolate: 'monotone', stroke: 'blue'})\n .encode(\n vl.x().fieldQ('D'),\n vl.y().fieldQ('P_all').title('P_all (BLUE)'),\n );\n \n const Q = vl.markLine({interpolate: 'monotone', stroke: 'green'})\n .encode(\n vl.x().fieldQ('D'),\n vl.y().fieldQ('Q').title('Q (GREEN)'),\n );\n\n return vl.layer(P, E, P_all, Q)\n .data(indicators_data)\n //.resolve({scale: {y: 'independent'}}) // resolve to independent y channel scales\n .title('Indicators over D')\n .width(800)\n .height(300)\n .render();\n}\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":688,"value":"{\n const form = html``;\n form.layoutAndRenderButton.onclick = () => {\n applyLayout(g);\n }; \n \n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":661,"value":"md`\n* *P* is in black. It represents how many connected pairs are closer than *D*. We want it high.\n* *E* is in red. It represents how wrong it is to consider that all pairs closer than *D* are connected. We want it as low as possible.\n* *P_all* is in blue. It represents how many pairs are closer than *D* (connected or not). We want it low, because when it is high, *P* does not mean much.\n* *Q* is in green. It represents how many connected pairs are closer than *D*, compared to expectations. *(Note: it is normalized to match the scale of the other indicators)*\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":566,"value":"md`### A few observations\n* **The error *E* is always super high.** In other words, **no useful value of *D* can be interpreted as \"close nodes are connected\", even approximately**. It is therefore critical to fight against this interpretation.\n* But at least we can ignore *E* and stop trying to optimize it; it is hopeless.\n* *P* rises much quicker than *P_all*. It is not surprising, since we know that most connected pairs are super close, while disconnected pairs are distributed more evenly. Still, it shows that we have a chance to have *P* high and *P_all* low at the same time.\n* ** *Q* rises and falls.** It is expected, since *Q* should be zero at both ends, by definition (i.e. captured connected pairs minus expected connected pairs).\n* ** *Q* captures well the moment *P* is high and *P_all* is low.** Does this generalize to other networks? Other layouts? For the moment, let's go with it.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":691,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":711,"value":"DQ = {\n // This brute force method is not optimized. I know. But it is clear, at least.\n let Qmax = 0;\n let DQ = 0;\n indicators_data.forEach(d=>{\n if (d.Q > Qmax) {\n Qmax = d.Q;\n DQ = d.D;\n }\n })\n return DQ\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":752,"value":"DQ_indicators = computeIndicators(DQ, g)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":762,"value":"{\n const form = html``;\n form.layoutAndRenderButton.onclick = () => {\n applyLayout(g);\n }; \n \n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":720,"value":"{\n return drawNetwork(\n g,\n { // Settings\n size: 500\n },\n graph_version\n ).canvas\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":732,"value":"{\n const size = 500;\n \n // Create canvas\n const canvas = document.createElement('canvas');\n canvas.width = 500;\n canvas.height = 50;\n const ctx = canvas.getContext('2d');\n\n // Paint a white background\n ctx.beginPath()\n ctx.rect(0, 0, canvas.width, canvas.height)\n ctx.fillStyle=\"white\"\n ctx.fill()\n ctx.closePath()\n\n // Scale canvas\n ctx.scale(size/1000, size/1000)\n\n // Draw the scale\n ctx.lineCap=\"round\";\n ctx.lineJoin=\"round\";\n ctx.fillStyle = 'rgba(0, 0, 0, 0)';\n ctx.lineWidth = 5;\n\n const offset = 10;\n ctx.beginPath();\n ctx.moveTo(offset, offset)\n ctx.lineTo(offset, canvas.height - offset)\n ctx.moveTo(offset, canvas.height/2);\n ctx.lineTo(offset+DQ, canvas.height/2);\n ctx.moveTo(offset+DQ, offset)\n ctx.lineTo(offset+DQ, canvas.height - offset)\n ctx.stroke();\n ctx.closePath();\n\n // Reset current transformation matrix to the identity matrix\n ctx.setTransform(1, 0, 0, 1, 0, 0);\n \n return canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":748,"value":"html`

\n Characteristic distance of the layout (D_Q)\n

${Math.floor(DQ_indicators.P)} % of edges are D_Q or shorter
But note that two nodes closer than D_Q only have ${Math.floor(DQ_indicators.C)} % chances of being connected
At length D_Q or shorter, lie the most edges compared to expectations, in this layout.

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":805,"value":"md`

*Note: Have you remarked that the characteristic distance is very stable despite re-running the layout? What do you think?*`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":25,"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":27,"value":"Graph = require('graphology@0.17.1/dist/graphology.umd.min.js')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":839,"value":"GraphologyLibrary = require('graphology-library@0.3.0/dist/graphology-library.min.js')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"gexf = GraphologyLibrary.gexf","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"layout = GraphologyLibrary.layout","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"fa2 = GraphologyLibrary.layoutForceAtlas2","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"md`### Require d3`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":37,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":39,"value":"md`### Load the network into Graphology`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":41,"value":"networkGEXF = FileAttachment(\"Rio+20.gexf\").text()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":43,"value":"g = {\n let g = gexf.parse(Graph, networkGEXF);\n applyLayout(g);\n return g\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":97,"value":"md`*We use a variable for the graph version to track graph changes across cells:*`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":94,"value":"mutable graph_version = 0; // We use the graph version to track graph changes across cells","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":49,"value":"md`### Apply force-driven layout`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":51,"value":"applyLayout = function(g) {\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}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":64,"value":"md`### Network rendering routine`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":66,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":156,"value":"md`### Load Vega Lite for plotting`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":159,"value":"import {vl} from '@vega/vega-lite-api'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":441,"value":"md`### Load Observable inputs`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":444,"value":"import {View} from \"@mbostock/synchronized-views\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":571,"value":"md`Bind some views`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":574,"value":"viewof D = new View(50) // 50 is the default value","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W38","stdlib":"1","titling":"auto"}} 33:"$32:body"