31:Te7c,networks = [ { id:'clique', name:'Clique', description:'All nodes are connected.', generator: ()=>{return generateClique(reference_order)} },{ id:'bri-cli-2-1', name:'Two bridged cliques', description:'2 cliques (groups of fully connected nodes) connected by 1 edge.', generator: ()=>{return generateBridgedCliques(reference_order, 2, 1)} },{ id:'sbm-999', name:'Two blocks connected at 99.9%', description:'Network generated by stochastic block model. It has 2 blocks. Two nodes in the same block have a 99.9% probability of being connected. Two nodes in a different block have a 0.1% probability of being connected.', generator: ()=>{return generateSBM(reference_order, 2, .999, .001)} },{ id:'sbm-99', name:'Two blocks connected at 99%', description:'Network generated by stochastic block model. It has 2 blocks. Two nodes in the same block have a 99% probability of being connected. Two nodes in a different block have a 1% probability of being connected.', generator: ()=>{return generateSBM(reference_order, 2, .99, .01)} },{ id:'sbm-90', name:'Two blocks connected at 90%', description:'Network generated by stochastic block model. It has 2 blocks. Two nodes in the same block have a 90% probability of being connected. Two nodes in a different block have a 10% probability of being connected.', generator: ()=>{return generateSBM(reference_order, 2, .9, .1)} },{ id:'sbm-80', name:'Two blocks connected at 80%', description:'Network generated by stochastic block model. It has 2 blocks. Two nodes in the same block have a 80% probability of being connected. Two nodes in a different block have a 20% probability of being connected.', generator: ()=>{return generateSBM(reference_order, 2, .8, .2)} },{ id:'sbm-70', name:'Two blocks connected at 70%', description:'Network generated by stochastic block model. It has 2 blocks. Two nodes in the same block have a 70% probability of being connected. Two nodes in a different block have a 30% probability of being connected.', generator: ()=>{return generateSBM(reference_order, 2, .7, .3)} },{ id:'sbm-60', name:'Two blocks connected at 60%', description:'Network generated by stochastic block model. It has 2 blocks. Two nodes in the same block have a 60% probability of being connected. Two nodes in a different block have a 40% probability of being connected.', generator: ()=>{return generateSBM(reference_order, 2, .6, .4)} },{ id:'rand-50', name:'Random network connected at 50%', description:'Random network: two nodes have a 50% probability of being connected.', generator: ()=>{return generateRandom(reference_order, .5)} },{ id:'rand-5', name:'Random network connected at 5%', description:'Random network: two nodes have a 5% probability of being connected.', generator: ()=>{return generateRandom(reference_order, .05)} },{ id:'rand-01', name:'Random network connected at 0.1%', description:'Random network: two nodes have a 0.1% probability of being connected.', generator: ()=>{return generateRandom(reference_order, .001)} },{ id:'chain', name:'Chain', description:'A chain of nodes.', generator: ()=>{return generateChain(reference_order)} },{ id:'star', name:'Star', description:'Network with a central node, and the other nodes are only connected to that one.', generator: ()=>{return generateStar(reference_order)} },{ id:'sq-latt', name:'Square lattice', description:'This network is a square grid of nodes.', generator: ()=>{return generateSquareLattice(reference_order, 1)} } ]32:T113c,layouts = [ { id:'fa2', name:'Force Atlas 2', description:'The Force Atlas 2 layout with standard settings.', layout: (g)=>{ // Apply a random layout g.nodes().forEach(nid => { g.setNodeAttribute(nid, 'x', 500-1000*Math.random()); g.setNodeAttribute(nid, 'y', 500-1000*Math.random()); }); // Apply Force Atlas 2 fa2.assign(g, {iterations: 1000, settings: { linLogMode: false, outboundAttractionDistribution: false, adjustSizes: false, edgeWeightInfluence: 0, scalingRatio: 10, strongGravityMode: true, gravity: 0.03, slowDown: 1, barnesHutOptimize: false, barnesHutTheta: 0.5 }}); } },{ id:'fa2-bad', name:'Force Atlas 2 BAD', description:'The Force Atlas 2 layout with bad settings: too much gravity, not enough iterations.', layout: (g)=>{ // Apply a random layout g.nodes().forEach(nid => { g.setNodeAttribute(nid, 'x', 500-1000*Math.random()); g.setNodeAttribute(nid, 'y', 500-1000*Math.random()); }); // Apply Force Atlas 2 fa2.assign(g, {iterations: 250, settings: { linLogMode: false, outboundAttractionDistribution: false, adjustSizes: false, edgeWeightInfluence: 0, scalingRatio: 20, strongGravityMode: true, gravity: 1, slowDown: 0.8, barnesHutOptimize: false, barnesHutTheta: 0.5 }}); } },{ id:'linlog', name:'Lin Log', description:'The Force Atlas 2 layout with the "Lin Log" settings activated (follows the principle of the LinLog algorithm).', layout: (g)=>{ // Apply a random layout g.nodes().forEach(nid => { g.setNodeAttribute(nid, 'x', 500-1000*Math.random()); g.setNodeAttribute(nid, 'y', 500-1000*Math.random()); }); // Apply Force Atlas 2 fa2.assign(g, {iterations: 1000, settings: { linLogMode: true, outboundAttractionDistribution: false, adjustSizes: false, edgeWeightInfluence: 0, scalingRatio: 0.5, strongGravityMode: true, gravity: 0.0001, slowDown: 1, barnesHutOptimize: false, barnesHutTheta: 0.5 }}); } },{ id:'random-round', name:'Random (in a disc)', description:'Nodes are placed at random in a disc.', layout: (g)=>{ // Apply a random layout, but contained to a circle const r = 300; g.nodes().forEach(nid => { let x = r-2*r*Math.random(); let y = r-2*r*Math.random(); let d2 = x*x+y*y; while (d2>r*r) { x = r-2*r*Math.random(); y = r-2*r*Math.random(); d2 = x*x+y*y; } g.setNodeAttribute(nid, 'x', x); g.setNodeAttribute(nid, 'y', y); }); } },{ id:'random-graphology', name:'Random (Graphology)', description:'Nodes are placed at random. Uses the Graphology library.', layout: (g)=>{ graphLayout.random.assign(g, {scale: 500}); } },{ id:'circular', name:'Circular layout', description:'Nodes are placed around a circle. Uses the Graphology library.', layout: (g)=>{ graphLayout.circular.assign(g, {scale: 500}); } },{ id:'d3', name:'d3 Force Simulation', description:'The force-directed layout algorithm implemented in d3.js, with default settings.', layout: (g)=>{ // Graphology system to d3 system let node_index = {} let nodes = g.nodes().map((nid,i)=>{ node_index[nid] = i return {index: i, nid:nid} }); let links = g.edges().map(eid=>{return {source: node_index[g.source(eid)], target: node_index[g.target(eid)]}}); let simulation = d3.forceSimulation(nodes) .force("charge", d3.forceManyBody()) .force("link", d3.forceLink(links)) .force("x", d3.forceX()) .force("y", d3.forceY()) .stop(); // See https://github.com/d3/d3-force/blob/master/README.md#simulation_tick for (let i = 0, n = Math.ceil(Math.log(simulation.alphaMin()) / Math.log(1 - simulation.alphaDecay())); i < n; ++i) { simulation.tick(); } // Back to the graphology stuff nodes.forEach(n=>{ g.setNodeAttribute(n.nid, 'x', n.x); g.setNodeAttribute(n.nid, 'y', n.y); }); } } ]33:T4ab,DOM.download(()=>{ let aggregated_data = benchmark_data_flat.map(d=>{ if (d.data.length == 0) { return { network_id: d.network_id, layout_id: d.layout_id } } return { network_id: d.network_id, layout_id: d.layout_id, Q_mean: isNaN(d.data[0].Q) ? undefined : d3.mean(d.data, dd=>0.01*dd.Q), Q_sd: isNaN(d.data[0].Q) ? undefined : d3.deviation(d.data, dd=>0.01*dd.Q), DQ_mean: isNaN(d.data[0].DQ) ? undefined : d3.mean(d.data, dd=>dd.DQ), DQ_sd: isNaN(d.data[0].DQ) ? undefined : d3.deviation(d.data, dd=>dd.DQ), PQ_mean: isNaN(d.data[0].PQ) ? undefined : d3.mean(d.data, dd=>0.01*dd.PQ), PQ_sd: isNaN(d.data[0].PQ) ? undefined : d3.deviation(d.data, dd=>0.01*dd.PQ), P_allQ_mean: isNaN(d.data[0].P_allQ) ? undefined : d3.mean(d.data, dd=>0.01*dd.P_allQ), P_allQ_sd: isNaN(d.data[0].P_allQ) ? undefined : d3.deviation(d.data, dd=>0.01*dd.P_allQ), CQ_mean: isNaN(d.data[0].CQ) ? undefined : d3.mean(d.data, dd=>0.01*dd.CQ), CQ_sd: isNaN(d.data[0].CQ) ? undefined : d3.deviation(d.data, dd=>0.01*dd.CQ), } }); return serialize(aggregated_data) }, "data.csv", "⬇️ DOWNLOAD")34:T7f5,md`

## Modifications since previous notebook When developing this notebook I realized some improvements had to be done. Some of them were already discusses in previous notebooks of [the series](https://observablehq.com/collection/@jacomyma/force-directed-network-layout). ### Hiding *D_Q* when it is meaningless I have [written on that](https://observablehq.com/@jacomyma/evaluating-the-validity-metric-on-a-different-layout) but I now decided to implement it. I used *Q_max=10%* as the threshold. Below the threshold, I consider that there is not enough meaning to the characteristic distance to display it. In that situation, it is not featured onto the network map, even though technically, we can compute it. Why 10%? It corresponds to the average *Q_max* for a random network of 100 nodes with a probability of 50% rendered by a force-directed layout, which is a reasonable landmark. It is also a round number. That value is debatable. If the goal is to eliminate the random layouts, 1% is above the mean and 2% above the mean plus the standard deviation. ### Plateau management Sometimes there is a plateau for *Q_max*. The typical case is when visualizing two bridged cliques with a force-directed layout. Try it, you will see what I mean. There is a wide range of distances that have the same maximal *Q*, or almost the same. That is bad, because intuitively the miniscule differences on the plateau do not mean much, while they matter a lot to deciding the distance *D_Q*. And intuitively, we would like to have the smallest *D_Q* possible (in case of tie or quasi-tie). So I use a simple modification to give an incentive to smaller *D_Q* without changing *Q_max* significantly. I use an error tolerance *ε*, set to a small percentage like 1% (o.o1), and when checking if a distance *D'* is more suitable than the current best case *D*, instead of checking that *Q(D')>Q(D)* I check that: *Q(D') > Q(D) / [ 1 - ε + εD/D' ]*. `35:T1f26,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_DQ = settings.edge_color_DQ || true; 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 || 140; let D = data.DQ; let Q = data.Q; // 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(); // 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); // 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_DQ) { 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_DQ) { if (d<=D*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); // Validity metric information if (Q >= 10) { // Draw the scale const D_scaled = D * ( settings.size/1000); drawScaleH(ctx, 10+D_scaled/2, settings.size+20, D_scaled); drawText(ctx, 'Dǫ', 10+D_scaled/2 - 8, settings.size + 10); drawText(ctx, Math.round(data.PQ)+'% of edges are Dǫ or shorter ('+Math.round(data.PQ-data.Q)+'% expected)', 8, settings.size + 60); drawText(ctx, 'Dǫ is the distance getting the most edges above expectations ('+Math.round(data.Q)+'%)', 8, settings.size + 90); drawText(ctx, 'Nodes closer than Dǫ have '+Math.round(data.CQ)+'% chances to be connected', 8, settings.size + 120); } else { // The scale is not valid, so we do not draw it, but put a message instead. drawText(ctx, 'Note: No Dǫ', 8, settings.size + 30); drawText(ctx, 'There is no characteristic distance for this layout.', 8, settings.size + 60); drawText(ctx, 'No given distance captures significantly more edges than expected.', 8, settings.size + 90); } // 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); D *= 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) { ctx.font = "500 18px 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 drawScaleH(ctx, x, y, D) { const height = 12; ctx.strokeStyle = 'rgba(0, 0, 0, 1)'; ctx.lineCap="round"; ctx.lineJoin="round"; ctx.fillStyle = 'rgba(0, 0, 0, 0)'; ctx.lineWidth = 2; 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(); } // Return result return { canvas, ctx }; }36:Tf5a,computeData = function(g, layout) { // Apply layout layout.layout(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; })(); // Compute indicators over D const indicators_over_D = (()=>{ const distances = d3.scaleLinear() .domain(d3.extent(pairs_of_nodes_list, d=>d.d)) .nice() .ticks(100); let ilist = distances.map(D=>{ const i = computeIndicators(D, g); return { D, E: i.E, P: i.P, P_all: i.P_all, Q: i.Q }; }); return ilist; })(); // Compute DQ const epsilon = 0.05; // error tolerance const DQ = (()=>{ let Qmax = 0; let DQ = 0; indicators_over_D.forEach(d=>{ //if (d.Q > Qmax) { if (d.Q > Qmax / (1 - epsilon + epsilon * DQ/d.D)) { // tweaked to fix plateau issues Qmax = d.Q; DQ = d.D; } }); return DQ; })(); // Compute indicators for DQ const DQ_indicators = computeIndicators(DQ, g); // Internal methods function computeIndicators(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 = total_of_pairs_below_D*ratio_of_connected_pairs const Q = Math.floor(10000*(count_of_connected_pairs_below_D - expected_count_of_connected_pairs_below_D)/total_of_connected_pairs)/100; return { P, E, C, P_all, Q }; } const data = { g, pairs_of_nodes_index, pairs_of_nodes_list, indicators_over_D, DQ, PQ: DQ_indicators.P, EQ: DQ_indicators.E, CQ: DQ_indicators.C, P_allQ: DQ_indicators.P_all, Q: DQ_indicators.Q }; push_benchmark_data(network.id, layout.id, data); return data; }37:T49c,function plot(data) { const AREA = vl.markArea({interpolate: 'monotone', fill: 'rgba(50, 200, 100, 0.06)'}) .data(data.indicators_over_D) .encode( vl.x().fieldQ('D'), vl.y().fieldQ('P'), vl.y2().fieldQ('P_all'), ); const P = vl.markLine({interpolate: 'monotone', stroke: 'black'}) .data(data.indicators_over_D) .encode( vl.x().fieldQ('D'), vl.y().fieldQ('P').title('P (BLACK)'), ); const P_all = vl.markLine({interpolate: 'monotone', stroke: 'blue'}) .data(data.indicators_over_D) .encode( vl.x().fieldQ('D'), vl.y().fieldQ('P_all').title('P_all (BLUE)'), ); const Q = vl.markLine({interpolate: 'monotone', stroke: 'green'}) .data(data.indicators_over_D) .encode( vl.x().fieldQ('D'), vl.y().fieldQ('Q').title('Q (GREEN)'), ); const DQ_rule = vl.markRule({color: '#0A3'}) .data({values:[{D:data.DQ}]}) .encode( vl.x().fieldQ('D') ); return vl.layer(AREA, P, P_all, Q, DQ_rule) .title('Indicators over D') .width(640) .height(180) .render(); }38:[] 2f:{"title":"Evaluating the validity metric on different networks, different layouts","cells":[{"id":1971,"value":"md`# Evaluating the validity metric on different networks, different layouts`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1966,"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"},{"id":0,"value":"md`\n*Note: find the same notebook but with the post-redesign vocabulary and formalism [there](https://observablehq.com/@jacomyma/evaluating-the-connected-closeness-metric-post-design).*\n\nI wrote a lot of text in [the previous notebook of this series](https://observablehq.com/@jacomyma/evaluating-the-validity-metric-on-a-different-layout). It's about a validity metric for interpreting network maps, that I call *D_Q* for lack of a better name - for now.\n\nHere I focus on the systematic visualization and evaluation of that measure, for different networks, different layouts.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1299,"value":"md`## Networks\nPick a nodes number, and generate a series of different networks using generators from [this notebook](https://observablehq.com/@jacomyma/basic-network-generators).\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1320,"value":"html`

${viewof reference_order.bind(html``)} nodes per test network

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1303,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":1392,"value":"network_index = {\n let index = {};\n networks.forEach(n=>{\n index[n.id] = n;\n })\n return index;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1596,"value":"html`\n

List of generators:

\n ${network.name}.\n ${network.id}\n
\n ${network.description}\n

\n

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1349,"value":"md`## Layout algorithms`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1352,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":1396,"value":"layout_index = {\n let index = {};\n layouts.forEach(l=>{\n index[l.id] = l;\n })\n return index;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1621,"value":"html`\n

List of layouts:

\n ${layout.name}.\n ${layout.id}\n
\n ${layout.description}\n

\n

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1360,"value":"md`## Visualize network & layout`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1370,"value":"html`

Visualize ${\n  viewof network_id.bind(html``)\n} using ${\n  viewof layout_id.bind(html``)\n}\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":936,"value":"{\n return draw(\n g,\n {size: 640},\n data\n ).canvas\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1058,"value":"{\n const form = html``;\n form.layoutAndRenderButton.onclick = () => {\n viewof network_id.value = network_id;\n };\n \n return form;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":912,"value":"plot(data);","pinned":false,"hidden":false,"mode":"ojs"},{"id":1487,"value":"md`*Note: D_Q is visualized as the green bar*`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1425,"value":"html`

Visualize ${\n  viewof network_id.bind(html``)\n} using ${\n  viewof layout_id.bind(html``)\n}\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1409,"value":"layout = layout_index[layout_id]","pinned":false,"hidden":false,"mode":"ojs"},{"id":1406,"value":"network = network_index[network_id]","pinned":false,"hidden":false,"mode":"ojs"},{"id":852,"value":"g = network.generator()","pinned":false,"hidden":false,"mode":"ojs"},{"id":869,"value":"data = computeData(g, layout)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1448,"value":"md`## Benchmarking all the cases\nEvery case that has been tried above is stored below. If we get all the combinations, we can get some statistics.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1492,"value":"mutable benchmark_data = {\n return {}\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1499,"value":"push_benchmark_data = function(network_id, layout_id, data) {\n if ( benchmark_data[reference_order] === undefined ) {\n benchmark_data[reference_order] = {};\n }\n if ( benchmark_data[reference_order][network_id] === undefined ) {\n benchmark_data[reference_order][network_id] = {};\n }\n if ( benchmark_data[reference_order][network_id][layout_id] === undefined ) {\n benchmark_data[reference_order][network_id][layout_id] = [];\n }\n const reducedData = {\n DQ:data.DQ,\n PQ:data.PQ,\n P_allQ:data.P_allQ,\n CQ:data.CQ,\n Q:data.Q\n };\n benchmark_data[reference_order][network_id][layout_id].push(reducedData)\n mutable benchmark_data_version++\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1647,"value":"benchmark_data_flat = {\n network;\n let table = [];\n networks.forEach(network=>{\n layouts.forEach(layout=>{\n if (benchmark_data[reference_order] === undefined) {\n table.push({network_id:network.id, layout_id:layout.id, count:0, data:[]});\n return;\n }\n if (benchmark_data[reference_order][network.id] === undefined) {\n table.push({network_id:network.id, layout_id:layout.id, count:0, data:[]});\n return;\n }\n if (benchmark_data[reference_order][network.id][layout.id] === undefined) {\n table.push({network_id:network.id, layout_id:layout.id, count:0, data:[]});\n return;\n }\n table.push({\n network_id:network.id,\n layout_id:layout.id,\n data: benchmark_data[reference_order][network.id][layout.id]\n });\n });\n });\n \n return table;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1665,"value":"md`This is how many data points we have for each combination of a network and a layout:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1537,"value":"{\n benchmark_data_version;\n \n // Chart\n return vl.markCircle()\n .data(benchmark_data_flat.map(d=>{\n return {\n layout: layout_index[d.layout_id].name,\n network: d.network_id,\n count: d.data.length\n }\n }))\n .encode(\n vl.size().fieldQ('count').title('Data points'),\n vl.row().fieldN('network').title('Type of network'),\n vl.column().fieldN('layout').title('Layout'),\n )\n .width(80)\n .height(80)\n .render()\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1668,"value":"md`Fill the gaps automatically by clicking below. It takes some time!`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1675,"value":"{\n const form = html``;\n form.layoutAndRenderButton.onclick = () => {\n fill_next_gap();\n };\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1709,"value":"viewof scan_cases.bind(html``)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1727,"value":"{\n const form = html``;\n form.layoutAndRenderButton.onclick = () => {\n viewof scan_cases.value = false;\n };\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1671,"value":"function fill_next_gap() {\n const minimum_case_count = 10;\n let found_case = false;\n for (let network_id in network_index) {\n for (let layout_id in layout_index) {\n if (\n benchmark_data[reference_order][network_id]\n && benchmark_data[reference_order][network_id][layout_id]\n && benchmark_data[reference_order][network_id][layout_id].length >= minimum_case_count\n ) {\n // This case is good\n } else {\n found_case = [network_id, layout_id];\n break;\n break;\n }\n }\n }\n if (found_case) {\n viewof network_id.value = found_case[0];\n viewof layout_id.value =found_case[1];\n } else {\n viewof scan_cases.value = false;\n }\n if (viewof scan_cases.value) {\n setTimeout(fill_next_gap, 10);\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1741,"value":"md`## Visualizing the data\nThis is how the different statistical indicators distribute over this table. What do you think?`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1783,"value":"md`### *D_Q*, characteristic distance of the layout\n\n*D_Q* tells us how to interpret the network map:\n* There are more edges shorter than *D_Q* than expected (*Q_max* is the percentage of unexpected, *P(D_Q)* is the percentage of expected, *P_all(D_Q)* is the total percentage of shorter edges)\n* *D_Q* is the distance that get the highest amount of unexpected *Q_max*\n\nThe distance is not very comparable from network to network nor from layout to layout, as its real role is to be drawn onto the map. However, it is useful to observe how stable it is from one layout to another. **When it is very stable, it suggests that it captures an intrinsic feature of the *(network, layout)* pair, or even of the *network* itself, despite the non-deterministic nature of force-directed placement.**\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1780,"value":"{\n benchmark_data_version;\n \n // Data\n let data = [];\n benchmark_data_flat.forEach(d=>{\n d.data.forEach(dd=>{\n data.push({\n layout: layout_index[d.layout_id].name,\n network: d.network_id,\n value: dd.DQ\n });\n });\n });\n \n // Chart\n return vl.markPoint()\n .data(data)\n .encode(\n vl.x().fieldQ('value').title('D_Q'),\n vl.opacity().value(0.1),\n vl.row().fieldN('network').title('Type of network'),\n vl.column().fieldN('layout').title('Layout'),\n )\n .width(80)\n .height(30)\n .render()\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1746,"value":"md`### *Q_max*, layout's success at bringing connected nodes together\n\n*Q_max* depends on the distance *D_Q*. *Q_max* counts the percentage of edges shorter than *D_Q*, discounting their expected number. The highest it is, the better is the layout at bringing connected nodes together.\n\n*Q_max = (count_of_edges_below_DQ - expected_count_of_edges_below_DQ)\n
/ total_of_edges*\n\nwith *expected_count_of_edges_below_DQ = total_of_pairs_below_DQ* x *total_of_edges / total_of_all_pairs*\n\nThis equation can be interpreted as percentage of unexpected edges shorter than D_Q, but it is also strictly equivalent to:\n\n*Q_max = P(D_Q) - P_all(D_Q)* (see below)\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1749,"value":"{\n benchmark_data_version;\n \n // Data\n let data = [];\n benchmark_data_flat.forEach(d=>{\n d.data.forEach(dd=>{\n data.push({\n layout: layout_index[d.layout_id].name,\n network: d.network_id,\n value: dd.Q\n });\n });\n });\n \n // Chart\n return vl.markPoint()\n .data(data)\n .encode(\n vl.x().fieldQ('value').title('Q'),\n vl.opacity().value(0.1),\n vl.row().fieldN('network').title('Type of network'),\n vl.column().fieldN('layout').title('Layout'),\n )\n .width(80)\n .height(30)\n .render()\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1796,"value":"md`### *P(D_Q)*, percentage of edges shorter than *D_Q*\n\n*P(D_Q) = count_of_edges_below_DQ / total_of_edges*\n
(expressed as a percentage)\n\nGives a useful information on how to interpret the map, but that must be contextualized by both *Q_max* and *D_Q*.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1799,"value":"{\n benchmark_data_version;\n \n // Data\n let data = [];\n benchmark_data_flat.forEach(d=>{\n d.data.forEach(dd=>{\n data.push({\n layout: layout_index[d.layout_id].name,\n network: d.network_id,\n value: dd.PQ\n });\n });\n });\n \n // Chart\n return vl.markPoint()\n .data(data)\n .encode(\n vl.x().fieldQ('value').title('P(D_Q)'),\n vl.opacity().value(0.1),\n vl.row().fieldN('network').title('Type of network'),\n vl.column().fieldN('layout').title('Layout'),\n )\n .width(80)\n .height(30)\n .render()\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1813,"value":"md`### *P_all(D_Q)*, percentage of pairs shorter than *D_Q*\n\n*P_all(D_Q) = total_of_pairs_below_DQ / total_of_all_pairs*\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1816,"value":"{\n benchmark_data_version;\n \n // Data\n let data = [];\n benchmark_data_flat.forEach(d=>{\n d.data.forEach(dd=>{\n data.push({\n layout: layout_index[d.layout_id].name,\n network: d.network_id,\n value: dd.P_allQ\n });\n });\n });\n \n // Chart\n return vl.markPoint()\n .data(data)\n .encode(\n vl.x().fieldQ('value').title('P_all(D_Q)'),\n vl.opacity().value(0.1),\n vl.row().fieldN('network').title('Type of network'),\n vl.column().fieldN('layout').title('Layout'),\n )\n .width(80)\n .height(30)\n .render()\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1874,"value":"md`### *C(D_Q)*, chances that a pair below DQ is connected\n\n*C(D_Q) = count_of_edges_below_DQ / total_of_pairs_below_DQ*\n\nAn interesting metric to contextualize the map, because when the network is not very dense, even if *Q_max* is high, it does not mean that two nodes closer than *D_Q* have a high chance to be connected.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1884,"value":"{\n benchmark_data_version;\n \n // Data\n let data = [];\n benchmark_data_flat.forEach(d=>{\n d.data.forEach(dd=>{\n data.push({\n layout: layout_index[d.layout_id].name,\n network: d.network_id,\n value: dd.CQ\n });\n });\n });\n \n // Chart\n return vl.markPoint()\n .data(data)\n .encode(\n vl.x().fieldQ('value').title('C(D_Q)'),\n vl.opacity().value(0.1),\n vl.row().fieldN('network').title('Type of network'),\n vl.column().fieldN('layout').title('Layout'),\n )\n .width(80)\n .height(30)\n .render()\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1888,"value":"md`## Download aggregated dataset\n\nI have the use of downloading that data, as a CSV with the mean and standard deviation of each indicator.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1889,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":1453,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":27,"value":"Graph = require('graphology@0.17.1/dist/graphology.umd.min.js')","pinned":false,"hidden":false,"mode":"ojs"},{"id":1976,"value":"GraphologyLibrary = require('graphology-library@0.3.0/dist/graphology-library.min.js')","pinned":false,"hidden":false,"mode":"ojs"},{"id":29,"value":"gexf = GraphologyLibrary.gexf","pinned":false,"hidden":false,"mode":"ojs"},{"id":31,"value":"graphLayout = GraphologyLibrary.layout","pinned":false,"hidden":false,"mode":"ojs"},{"id":33,"value":"fa2 = GraphologyLibrary.layoutForceAtlas2","pinned":false,"hidden":false,"mode":"ojs"},{"id":35,"value":"md`### Require d3`","pinned":false,"hidden":false,"mode":"ojs"},{"id":37,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":842,"value":"md`### Import network generators`","pinned":false,"hidden":false,"mode":"ojs"},{"id":846,"value":"import {\n generateClique,\n generateStar,\n generateChain,\n generateSquareLattice,\n generateTriangularLattice,\n generateBridgedCliques,\n generateBridgedStars,\n generateBridgedLattices,\n generateRandom,\n generateSBM,\n} from \"@jacomyma/basic-network-generators\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":1901,"value":"md`#### Download CSV stuff`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1893,"value":"// From https://observablehq.com/@palewire/saving-csv\nfunction serialize (data) {\n let parser = new json2csv.Parser();\n let csv = parser.parse(data);\n return new Blob([csv], {type: \"text/csv\"}) \n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1895,"value":"json2csv = require(\"json2csv\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":156,"value":"md`### Load Vega Lite for plotting`","pinned":false,"hidden":false,"mode":"ojs"},{"id":159,"value":"import {vl} from '@vega/vega-lite-api'","pinned":false,"hidden":false,"mode":"ojs"},{"id":441,"value":"md`### Load Observable inputs`","pinned":false,"hidden":false,"mode":"ojs"},{"id":444,"value":"import {View} from \"@mbostock/synchronized-views\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":571,"value":"md`Bind some views`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1306,"value":"viewof reference_order = new View(100)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1372,"value":"viewof network_id = new View('sbm-90')\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":1377,"value":"viewof layout_id = new View('fa2')\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":1719,"value":"viewof scan_cases = new View(false)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1046,"value":"md`### Routines`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1107,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":926,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":1129,"value":"$37","pinned":false,"hidden":false,"mode":"ojs"},{"id":1086,"value":"md`Variables we track to retrigger certain routines`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1561,"value":"mutable benchmark_data_version = 0","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W38","stdlib":"1","titling":"auto"}