2b:null 2c:["$","title",null,{"children":"Network layout: designing a validity metric | Mathieu Jacomy | Observable"}] 31:T7d1,md`## Issues There are issues with the namings I used so far, but there are more serious issues. There are natural issues for the design. Let me state them here for the record. **The metric is complicated.** Just stating what it does requires multiple sentences. Making it clear is in itself a challenge. **The metric contains two statements.** One statement is a distance, the other one is a score that depends on this distance. This leads to multiple problems. I need to refer to one statement in the other. Should I use a symbol? If not, the name must still be short. In which order to expose the two statements? One order favors clarity while the other favors meaning. **Two different messages must be conveyed.** These are not the two parts. The first message is the meaning of the metrics: what the score means given the distance. The second one is where they come from: why that particular distance is important, and not another one. Indeed, the former does not self-evidently come out of the latter. **"Edges" versus "connected nodes."** Most issues boil down to a trade-off between clarity and exactitude; this one too. Two equivalent statements: "layouts aim at bringing connected nodes closer" and "layouts aim at short edges". The former evokes the fact that the layout's success depends on its ability to represent the topology (closeness represents connections). The latter statement is strictly equivalent, shorter, and in the usual language of graphs; but I think it is harder to understand why short edges matter to reading the network map. I know I have to pick my words carefully. **Confusion with a similar notion.** As I exposed [earlier](https://observablehq.com/@jacomyma/distance-between-nodes-when-using-a-force-directed-layout?collection=@jacomyma/force-directed-network-layout), the score does *not* represent the percentage of edges among the nodes closer than the distance. This interpretation is both tempting and very wrong, and I want to actively discourage it. `32:T111f,md`## Designing the language elements Since I want to help people make sense of network maps, I must state what the metric does in the most straightforward way possible. But because it is complicated, I cannot just explain everything, since it would be too long. I will probably use a metaphor. Think of something like the *betweenness centrality*: it is more meaningful to say that it *detects bridges* than that it *counts on how many shortest paths is a given node.* Indeed the former is why we use it in practice, while the latter is how it is done; and why the latter implies the former is not self-evident. The metric has two parts: * A distance that is drawn on the network map. It defines a scale at which the second part makes sense. * A score, dependent of that distance above. Because of this dependency, I think that some formalism would help me. Indeed, I can write my score as a function of that distance, i.e. *S(d)*, to convey efficiently the idea of this dependency. Which variables to use, then? Something that reminds their name, but we do not have names yet. I aim at a name that relates to how the user is intended to use the distance and the score, but it must also be clear. It will not explain the underlying maths, but it is fine. The distance has to be a "Distance of something", "Length of something" or "Scale of something"; I am not satisfied with just "Reference distance" or "Characteristic scale". The distance is where the layout captures many edges, and it makes sense insofar as the layout tries to put connected nodes closer (if not, then this is not the right metric). Hence "Distance where edges are shorter", "Length of togetherness" or something of that kind. This means that the name of the distance refers to the score metric, because the "togetherness" or whatever is this concept, is quantified by the score. Indeed, the distance is where the score is maximal. It would then be useful to have a one-word concept for "bringing connected nodes together", like "togetherness", so that one can name the score "Maximal togetherness" and the distance "Distance of maximal togetherness". What is the best way to state the score then, if this is what I must pick first? It is not just a score, but a percentage. Then the distance-dependent score has (1) a long name such as "Percentage of xxx" and (2) a short, substantive name such as "togetherness", and the final score is "maximal togetherness". The longer name must favor clarity. "Percentage of unexpectedly shorter edges" is the best I could find and, I think, is good enough. How to summarize it in one substantive? "Togetherness" does not mention edges, or connected pairs specifically. "Edge shortness" is more to the point, but I still think it is not self-evident how short edges relate to reading the network map. "Connected nodes togetherness" is too long. Finally I land on "connected-closeness"; a bit monstruous, but I feel like I have to. It evokes connections but not directly edges, it carries the notion of being close. Now we have the notion of **connected-closeness**, with a definition (**percentage of unexpectedly close connected nodes**, following the same vocabulary), the score itself, **maximal connected-closeness**. This also gives us the **distance of maximal connected-closeness**. Now to clarify the relation between those, I add some formalism, as mentioned earlier. An issue with *connected-closeness* is that it abbreviates as "cc" like "clustering coefficient", a similar but different notion. Another constraint is the fact that **maximal connected-closeness** will certainly have the "max" subscript; so I want to avoid another subscript like *C_c*. I could use a superscript like *Cc* but I do not think that this metric will be used in formal contexts along with many other variable names. I just pick *C* and *C_max*. Now, the distance is another story. There is already an important notion of distance in graph theory, the geodesic distance. It is often written *d* and I want to use something else. I think that *D* might be too close, so here I will go full Greek and use *Δ* (Delta). To enforce the distinction, I will use the expression "Euclidean distance" as often as I can, in the hope that the Greek name will conveniently resonate with the Greek letter. This is what this naming process leads me to: `33:T754,html`

Important quantities

${tex`C(\Delta)`} is the connected-closeness for the Euclidean distance ${tex`\Delta`}.
It is defined as the percentage of unexpectedly close connected nodes, where close means closer than ${tex`\Delta`} (see below).

${tex`\Delta_{max}`} is the distance of maximal connected-closeness.

${tex`C_{max} = C(\Delta_{max})`} is the maximal connected-closeness.

Definition of connected-closeness

${tex`C(\Delta)=\displaystyle\frac{E(\Delta) - E_{expected}(\Delta)}{E(\infty)}=\displaystyle\frac{E(\Delta)}{E(\infty)} - \displaystyle\frac{p(\Delta)}{p(\infty)}`}

${tex`E(\Delta)`} is the count of edges shorter than the Euclidean distance ${tex`\Delta`}
${tex`E(\infty)=e`} is the total count of edges (i.e. the graph size ${tex`e`})
${tex`E_{expected}(\Delta) = E(\infty) \times \displaystyle\frac{p(\Delta)}{p(\infty)}`} is the count of expected edges shorter than Euclidean distance ${tex`\Delta`}
${tex`p(\Delta)`} is the count of node pairs closer than the Euclidean distance ${tex`\Delta`}
${tex`p(\infty)=n \times (n-1)`} is the total count of node pairs (${tex`n`} is graph order)

Definition of the maximal connected-closeness

${tex`C_{max}`} is defined as the maximum of ${tex`C(\Delta)`} for any ${tex`\Delta`}

${tex`\Delta_{max}`} is the Euclidean distance where ${tex`C(\Delta)`} is maximal. In case of ties, the smallest ${tex`\Delta`} is retained.

`34:T41e,md`## Graphic design on the network map The final part of the design is about the network map itself. Contrary to the scale indicator on a geographical map, the ${tex`\Delta`} length does not scale: it would not mean twice as much of something if it were twice as long, it means something at its precise length. It is then quite useful to be able to relate it to the size of the visualized network. I have three ideas to enforce that: * Have it in the center of a side, and not just in the corner * Have it vertical as well as horizontal * Also show it as a background grid In addition, because there is a natural relation between different quantities, I think that a small pie chart might help to convey the idea that "expected" edges ${tex`E_{expected}(\Delta_{max})`} and "layout" edges ${tex`C_{max}`} add up to ${tex`E_{\%}(\Delta_{max})`}. It looks like this, using the dataset from [that paper](https://www.semanticscholar.org/paper/Visual-Network-Exploration-for-Data-Journalists-Venturini-Jacomy/897ed65b81e613e1d53f1ae5edc45a6521307aae). `35:T4a3,html`

	Old naming		New naming
D_Q	Characteristic distance	${tex`\Delta_{max}`}	Distance of maximal connected-closeness
Q_max	Layout's success at bringing connected nodes together	${tex`C_{max} = C(\Delta_{max})`}	Maximal connected-closeness
P(D)	Percentage of edges shorter than D	${tex`E_{\%}(\Delta)`}	Proportion of edges shorter than ${tex`\Delta`}
P_all(D)	Percentage of pairs shorter than D	${tex`p_{\%}(\Delta)`}	Proportion of node pairs closer than ${tex`\Delta`}
C(D)	Chances that a pair below D is connected	${tex`P_{edge}(\Delta)`}	Probability that, considering two nodes closer than the Euclidean distance ${tex`\Delta`}, they are connected

`36:T53f,md`## Additional metric The statistical analysis of these metrics shows than in many usual circumstances, ${tex`C_{max}`} captures a feature of the network and the layout, regarless of the initial randomization of non-deterministic algorithms like Force Atlas 2. I want to go further down the rabbit hole. However ${tex`C_{max}`} has a drawback: it depends on a distance ${tex`\Delta_{max}`}. Indeed, the effect of the layout is to make all edges shorter, including edges that are longer than ${tex`\Delta_{max}`}. I decided to not use a global measure, because it does not help much to read the map in practice. My main goal was *not* to evaluate layouts, but to provide a practical help for interpreting network maps. At this point however, such measure might prove useful. I formalize it below. The simple and understandable metric I propose is to look at how much shorter the edges are, compared to expectations. Expectations here are what the length would be if edges were distributed at random in the current layout, which is the same as the average distance between two nodes. I call it the "edge length reduction ratio" ${tex`R_{edge}`}. Example: ${tex`R_{edge} = 0.25`} means that the layout succeded in having edges a fourth shorter than expected (i.e. their length is on average 25% of what it should be if it were at random). `37:Tf20,computeData = function(g) { // Compute list of pairs of nodes const pairs_of_nodes_index = (()=>{ let p = {}; const nlist = g.nodes(); for (let i=0; i{ return d; }); // Sort from longest to shortest pairs.sort(function(a,b){return b.d-a.d}); pairs.forEach((d,i)=>{d.rank = i}); return pairs; })(); // Global indicators const R_edge = d3.mean(pairs_of_nodes_list.filter(d=>d.c), d=>d.d) / d3.mean(pairs_of_nodes_list, d=>d.d); // Compute indicators over D const indicators_over_Delta = (()=>{ const distances = d3.scaleLinear() .domain(d3.extent(pairs_of_nodes_list, d=>d.d)) .nice() .ticks(100); let ilist = distances.map(Delta=>{ const i = computeIndicators(Delta, g); return { Delta, E_percent: i.E_percent, p_percent: i.p_percent, P_edge: i.P_edge, C: i.C }; }); return ilist; })(); // Compute DeltaMax // Find true Cmax const Cmax_true = d3.max(indicators_over_Delta, d=>d.C); // Find DeltaMax using tolerance const epsilon = 0.03; // error tolerance const DeltaMax = d3.min(indicators_over_Delta.filter(d=>(d.C>=(1-epsilon)*Cmax_true)), d=>d.Delta); // Compute indicators for DQ const DeltaMax_indicators = computeIndicators(DeltaMax, g); // Internal methods function computeIndicators(Delta,g) { const connected_pairs = pairs_of_nodes_list.filter(d=>d.c); const total_of_connected_pairs = connected_pairs.length; const connected_pairs_below_Delta = connected_pairs.filter(d=>d.d<=Delta); const count_of_connected_pairs_below_Delta = connected_pairs_below_Delta.length; const disconnected_pairs = pairs_of_nodes_list.filter(d=>!d.c); const disconnected_pairs_below_Delta = disconnected_pairs.filter(d=>d.d<=Delta); const count_of_disconnected_pairs_below_Delta = disconnected_pairs_below_Delta.length; const total_of_pairs_below_Delta = count_of_connected_pairs_below_Delta + count_of_disconnected_pairs_below_Delta; const total_of_all_pairs = pairs_of_nodes_list.length; // Percentage of connected nodes below Delta const E_percent = Math.floor(10000*count_of_connected_pairs_below_Delta/total_of_connected_pairs)/100; // Percentage of all pairs below D const p_percent = Math.floor(10000*total_of_pairs_below_Delta/total_of_all_pairs)/100; // Probability that a pair below Delta is connected const P_edge = Math.floor(10000*(count_of_connected_pairs_below_Delta/total_of_pairs_below_Delta))/100; // C, connected-closeness const ratio_of_connected_pairs = total_of_connected_pairs / total_of_all_pairs const expected_count_of_connected_pairs_below_D = total_of_pairs_below_Delta*ratio_of_connected_pairs const C = Math.floor(10000*(count_of_connected_pairs_below_Delta - expected_count_of_connected_pairs_below_D)/total_of_connected_pairs)/100; return { E_percent, p_percent, P_edge, C }; } const data = { g, pairs_of_nodes_index, pairs_of_nodes_list, indicators_over_Delta, DeltaMax, E_percent_of_DeltaMax: DeltaMax_indicators.E_percent, p_percent_of_DeltaMax: DeltaMax_indicators.p_percent, P_edge_of_DeltaMax: DeltaMax_indicators.P_edge, Cmax: Cmax_true }; return data; }38:T36da,function draw(_g, _settings, data) { // 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.zoom = settings.zoom || 0.9; // slight de-zoom for comfort settings.size = settings.size || 300; settings.node_size = settings.node_size || 5; settings.node_color = settings.node_color || 'rgba(0, 0, 0, 1)'; settings.edge_color_Dm = settings.edge_color_Dm || false; settings.edge_color = settings.edge_color || 'rgba(150, 150, 150, 0.8)'; settings.edge_thickness = settings.edge_thickness || 2; settings.margin_bottom = settings.margin_bottom || 130; let DeltaMax = data.DeltaMax; let Cmax = data.Cmax; // Create canvas const canvas = document.createElement('canvas'); canvas.width = settings.size; canvas.height = settings.size + settings.margin_bottom; const ctx = canvas.getContext('2d'); // Clone network, so that we do not modify the original let g = _g.copy(); // Prepare network data addMissingVisualizationData(); rescaleGraphToGraphicSpace(); let DeltaMax_scaled = DeltaMax * ( settings.size/1000); // Paint a white background ctx.fillStyle="white"; ctx.beginPath(); ctx.rect(0, 0, settings.size, settings.size+settings.margin_bottom); ctx.fill(); ctx.closePath(); // Connected-closeness Grid if (Cmax >= 10) { drawGrid(DeltaMax_scaled); } // Scale canvas ctx.scale(settings.size/1000, settings.size/1000); // Shuffle edges (important for coloring) let edges = g.edges(); shuffle(edges); // Draw each edge ctx.lineCap="round"; ctx.lineJoin="round"; ctx.fillStyle = 'rgba(0, 0, 0, 0)'; ctx.lineWidth = settings.edge_thickness; if (!settings.edge_color_Dm) { ctx.strokeStyle = settings.edge_color; } 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 (settings.edge_color_Dm) { if (d<=DeltaMax*1.01) { 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 = settings.node_color; ctx.fill(); ctx.closePath(); }); // Reset current transformation matrix to the identity matrix ctx.setTransform(1, 0, 0, 1, 0, 0); // Connected-closeness information if (Cmax >= 10) { // Draw the scale drawScaleV(ctx, 20, settings.size/2, DeltaMax_scaled); drawText(ctx, 'Δmax', 25, settings.size/2, "start"); drawScaleH(ctx, settings.size/2, settings.size-20, DeltaMax_scaled); drawText(ctx, 'Δmax', settings.size/2, settings.size -28, "center"); drawText(ctx, Math.round(data.E_percent_of_DeltaMax)+'% of connected nodes are Δmax or closer', settings.size/2, settings.size + 10, "center"); // Draw pie chart const chartAreaXOffset = settings.size/2 - 300 const pieChartR = 27; const pieChartCenterX = chartAreaXOffset + 25; const pieChartCenterY = settings.size + 55; drawPie(pieChartCenterX, pieChartCenterY, pieChartR); drawSquare(chartAreaXOffset + 67, settings.size + 35, 12, '#DDD'); drawText(ctx, Math.round(data.E_percent_of_DeltaMax)-Math.round(data.Cmax)+'% of connected nodes are closer than Δmax and would be if edges were at random', chartAreaXOffset + 80, settings.size + 40, "start"); drawSquare(chartAreaXOffset + 67, settings.size + 55, 12, 'rgb(49, 130, 189)'); drawText(ctx, Math.round(data.Cmax)+'% of connected nodes are closer than Δmax due to the effect of the layout', chartAreaXOffset + 80, settings.size + 60, "start"); drawSquare(chartAreaXOffset + 67, settings.size + 75, 12, '#FFF'); drawText(ctx, (100-Math.round(data.Cmax)-Math.round(data.E_percent_of_DeltaMax)+Math.round(data.Cmax))+'% of connected nodes are more distant than Δmax', chartAreaXOffset + 80, settings.size + 80, "start"); drawText(ctx, 'Two nodes closer than Δmax have a '+Math.round(data.P_edge_of_DeltaMax)+'% probability to be connected', settings.size/2, settings.size + 110, "center"); } else { drawText(ctx, 'Δmax is not applicable.', settings.size/2, settings.size + 10, "center"); // Draw pie chart const chartAreaXOffset = settings.size/2 - 300 const pieChartR = 27; const pieChartCenterX = chartAreaXOffset + 25; const pieChartCenterY = settings.size + 55; drawPie(pieChartCenterX, pieChartCenterY, pieChartR); drawSquare(chartAreaXOffset + 67, settings.size + 35, 12, '#DDD'); drawText(ctx, Math.round(data.E_percent_of_DeltaMax-data.Cmax)+'% of connected nodes are closer than Δmax and would be if edges were at random', chartAreaXOffset + 80, settings.size + 40, "start"); drawSquare(chartAreaXOffset + 67, settings.size + 55, 12, 'rgb(49, 130, 189)'); drawText(ctx, Math.round(data.Cmax)+'% of connected nodes are closer than Δmax due to the effect of the layout', chartAreaXOffset + 80, settings.size + 60, "start"); drawSquare(chartAreaXOffset + 67, settings.size + 75, 12, '#FFF'); drawText(ctx, (100-Math.round(data.Cmax)-Math.round(data.E_percent_of_DeltaMax-data.Cmax))+'% of connected nodes are more distant than Δmax', chartAreaXOffset + 80, settings.size + 80, "start"); } // Internal methods 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); DeltaMax *= ratio; // Resize g.nodes().forEach(function(nid){ let n = g.getNodeAttributes(nid); n.x = referenceSize / 2 + settings.zoom * (n.x - xbarycenter) * ratio; n.y = referenceSize / 2 + settings.zoom * (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}); } } function shuffle(array) { var currentIndex = array.length, temporaryValue, randomIndex; // While there remain elements to shuffle... while (0 !== currentIndex) { // Pick a remaining element... randomIndex = Math.floor(Math.random() * currentIndex); currentIndex -= 1; // And swap it with the current element. temporaryValue = array[currentIndex]; array[currentIndex] = array[randomIndex]; array[randomIndex] = temporaryValue; } return array; } function drawText(ctx, txt, x, y, textAlign) { ctx.textAlign = textAlign || "start"; ctx.font = "500 14px sans-serif"; ctx.lineWidth = 4; ctx.fillStyle = '#FFFFFF'; ctx.strokeStyle = '#FFFFFF'; ctx.fillText( txt, x, y ); ctx.strokeText( txt, x, y ); ctx.lineWidth = 0; ctx.fillStyle = '#000'; ctx.fillText( txt, x, y ); } function drawPie(pieChartCenterX, pieChartCenterY, pieChartR) { drawPieSlice(pieChartCenterX, pieChartCenterY, pieChartR, 0, (data.E_percent_of_DeltaMax-data.Cmax)/100, '#DDD'); drawPieSlice(pieChartCenterX, pieChartCenterY, pieChartR, (data.E_percent_of_DeltaMax-data.Cmax)/100, data.Cmax/100, 'rgb(49, 130, 189)'); drawPieSlice(pieChartCenterX, pieChartCenterY, pieChartR, (data.E_percent_of_DeltaMax)/100, (100-data.E_percent_of_DeltaMax)/100, '#FFF'); drawPieSliceBorder(pieChartCenterX, pieChartCenterY, pieChartR, 0, (data.E_percent_of_DeltaMax-data.Cmax)/100); drawPieSliceBorder(pieChartCenterX, pieChartCenterY, pieChartR, (data.E_percent_of_DeltaMax-data.Cmax)/100, data.Cmax/100); drawPieSliceBorder(pieChartCenterX, pieChartCenterY, pieChartR, (data.E_percent_of_DeltaMax)/100, (100-data.E_percent_of_DeltaMax)/100); ctx.strokeStyle = 'rgba(0, 0, 0, 1)'; ctx.lineCap="round"; ctx.lineJoin="round"; ctx.fillStyle = 'rgba(0, 0, 0, 0)'; ctx.lineWidth = 1.5; ctx.beginPath(); ctx.arc(pieChartCenterX, pieChartCenterY, pieChartR, 0, 2 * Math.PI); ctx.stroke(); } function drawSquare(x, y, size, color) { ctx.strokeStyle = 'rgba(0, 0, 0, 1)'; ctx.lineCap="round"; ctx.lineJoin="round"; ctx.fillStyle = color; ctx.lineWidth = 1.5; ctx.beginPath(); ctx.fillRect(x-size/2, y-size/2, size, size); ctx.rect(x-size/2, y-size/2, size, size); ctx.stroke(); ctx } function drawPieSlice(x, y, r, percentOffset, percent, color) { const startAngle = percentOffset * 2 * Math.PI - Math.PI/2; const endAngle = (percentOffset + percent) * 2 * Math.PI - Math.PI/2; ctx.strokeStyle = 'rgba(0, 0, 0, 1)'; ctx.lineCap="round"; ctx.lineJoin="round"; ctx.fillStyle = color; ctx.lineWidth = 1.5; ctx.beginPath(); ctx.moveTo(x, y); ctx.arc(x, y, r, startAngle, endAngle); ctx.fill(); ctx.closePath(); } function drawPieSliceBorder(x, y, r, percentOffset, percent) { const startAngle = percentOffset * 2 * Math.PI - Math.PI/2; const endAngle = (percentOffset + percent) * 2 * Math.PI - Math.PI/2; ctx.strokeStyle = 'rgba(0, 0, 0, 1)'; ctx.lineCap="round"; ctx.lineJoin="round"; ctx.lineWidth = 1.5; ctx.beginPath(); ctx.moveTo(x, y); ctx.arc(x, y, r, startAngle, endAngle); ctx.stroke(); ctx.closePath(); } function drawScaleH(ctx, x, y, D) { const height = 8; ctx.strokeStyle = 'rgba(0, 0, 0, 1)'; ctx.lineCap="round"; ctx.lineJoin="round"; ctx.fillStyle = 'rgba(0, 0, 0, 0)'; ctx.lineWidth = 1.5; ctx.beginPath(); ctx.moveTo(x-D/2, y-height/2) ctx.lineTo(x-D/2, y+height/2) ctx.moveTo(x-D/2, y); ctx.lineTo(x+D/2, y); ctx.moveTo(x+D/2, y-height/2) ctx.lineTo(x+D/2, y+height/2) ctx.stroke(); ctx.closePath(); } function drawScaleV(ctx, x, y, D) { const width = 8; ctx.strokeStyle = 'rgba(0, 0, 0, 1)'; ctx.lineCap="round"; ctx.lineJoin="round"; ctx.fillStyle = 'rgba(0, 0, 0, 0)'; ctx.lineWidth = 1.5; ctx.beginPath(); ctx.moveTo(x-width/2, y-D/2) ctx.lineTo(x+width/2, y-D/2) ctx.moveTo(x, y-D/2); ctx.lineTo(x, y+D/2); ctx.moveTo(x-width/2, y+D/2) ctx.lineTo(x+width/2, y+D/2) ctx.stroke(); ctx.closePath(); } function drawGrid(D) { ctx.strokeStyle = 'rgba(107, 174, 214, 1)'; ctx.lineCap="round"; ctx.lineJoin="round"; ctx.fillStyle = 'rgba(0, 0, 0, 0)'; ctx.lineWidth = 0.5; for (let d=0.5 * D; dmax*, etc. But these name tell a story to computer scientists, and do a poor job at explaining what the metric does to users. There is a need for design because, now that I have a better grasp on the maths, I can afford naming things for the user.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"md`## Goal\n\n**Helping users understand what they see when they look at a network map using a force-directed placement.**\n\nThis is my only main goal. I will use it as a guideline to take design decisions. Other valid goals are not as important as this one: publishing a paper, measuring the efficiency of a layout algorithm, optimizing the computation of the metric...\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":51,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":141,"value":"md`## Additional elements\nThe elements above cover the basics, but it was the hardest. Now we still need a few additional elements to explain and/or contextualize the metric. These are for instance the indicators that I used to benchmark the metric in the previous notebook of the series. I just extend the naming conventions to those.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":146,"value":"html`\n

Other useful quantities

\n ${tex`E_{\\%}(\\Delta) = \\displaystyle\\frac{E(\\Delta)}{E(\\infty)}`} is the proportion of edges shorter than the Euclidean distance ${tex`\\Delta`} (expressed as a percentage)\n

\n ${tex`p_{\\%}(\\Delta) = \\displaystyle\\frac{p(\\Delta)}{p(\\infty)}`} is the proportion of node pairs closer than the Euclidean distance ${tex`\\Delta`} (expressed as a percentage)\n

\n ${tex`P_{edge}(\\Delta)=\\displaystyle\\frac{E(\\Delta)}{p(\\Delta)}`} is the probability that, considering two nodes closer than the Euclidean distance ${tex`\\Delta`}, they are connected.\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":167,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":254,"value":"{\n return draw(\n g,\n {\n size: 900,\n node_size: 0.8,\n edge_thickness: 0.4\n },\n data\n ).canvas\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":259,"value":"md`### Indicators plot\nFor your information, the plot of indicators over the Euclidean distance ${tex`\\Delta`}.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":257,"value":"plot(data);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":169,"value":"md`## Table of correspondence with the old naming\n\nThis table is to alleviate your and my pain, should we have to go back and forth before the past and future notebooks. I hope I will not change these names again.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":173,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":330,"value":"md`## Implementation\n\nLook at the green curve in the plot (${tex`C(\\Delta)`}): its top is often flat. We can even have a full plateau. The top of the curve is not very stable. We want the top (${tex`C_{max}`}), yes, but it is also better to have the shortest Euclidean distance ${tex`\\Delta_{max}`} possible, as it bears more meaning in practice.\n\nThe strategy I proposed in the previous notebook is complicated to explain and justify. That is a real problem as the goal of this metric is to provide a quantified interpretation of the map. For that reason, I propose a simpler system. Its simplicity supports its clarity.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":339,"value":"html`\n

Implementation of the routine finding ${tex`\\Delta_{max}`}

\n ${tex`\\epsilon`} is a tolerance parameter, valued to 3% by default.\n
${tex`\\epsilon = 0.03`}\n

\n Once ${tex`C_{max}`} is found, ${tex`\\epsilon`} is used as a tolerance to determine ${tex`\\Delta_{max}`}.\n

\n ${tex`\\Delta_{max}`} is the smallest value such as:\n
${tex`C(\\Delta_{max}) >= (1 - \\epsilon)C_{max}`}\n

\n Insofar as ${tex`\\epsilon`} is small, its influence is negligible.\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":362,"value":"md`Note: in practice, for large networks, ${tex`C_{max}`}, ${tex`\\Delta_{max}`} and the other quantities have to be evaluated numerically, as there are too many node pairs for an exhaustive computation. The tolerance ${tex`\\epsilon`} makes even more sense in that situation, and should be adjusted accordingly.\n` ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":369,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":374,"value":"html`\n

Edge length reduction ratio

\n ${tex`R_{edge} = \\displaystyle\\frac{\\Delta_{edge}}{\\Delta_{pairs}}`} is the edge length reduction ratio, expressed as a percentage.\n

${tex`\\Delta_{edge}`} is the average Euclidean length of edges in the layout
${tex`\\Delta_{pairs}`} is the average Euclidean length of node pairs in the layout

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":206,"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":209,"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":454,"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":211,"value":"gexf = GraphologyLibrary.gexf","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":244,"value":"md`### Load network`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":247,"value":"networkGEXF = FileAttachment(\"Décodex 2017 anonymized@1.gexf\").text()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":250,"value":"g = {\n let g = gexf.parse(Graph, networkGEXF);\n // We need to invert y since the convention is different\n g.nodes().forEach(nid=>{\n let n = g.getNodeAttributes(nid);\n n.y = -n.y;\n });\n return g;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":263,"value":"data = computeData(g);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":217,"value":"md`### Require d3`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":219,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":221,"value":"md`### Load Vega Lite for plotting`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":223,"value":"import {vl} from '@vega/vega-lite-api'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":225,"value":"md`### Routines`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":229,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":227,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":232,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W3a","stdlib":"1","titling":"auto"}} 30:"$2f:body"