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:T11d4,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(); } // We scale the result for convenience (it has no impact except on drawings) const scalingRatio = 3; // Back to the graphology stuff nodes.forEach(n=>{ g.setNodeAttribute(n.nid, 'x', n.x*scalingRatio); g.setNodeAttribute(n.nid, 'y', n.y*scalingRatio); }); } } ]33:T6fa,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, Cmax_mean: isNaN(d.data[0].Cmax) ? undefined : d3.mean(d.data, dd=>0.01*dd.Cmax), Cmax_sd: isNaN(d.data[0].Cmax) ? undefined : d3.deviation(d.data, dd=>0.01*dd.Cmax), DeltaMax_mean: isNaN(d.data[0].DeltaMax) ? undefined : d3.mean(d.data, dd=>dd.DeltaMax), DeltaMax_sd: isNaN(d.data[0].DeltaMax) ? undefined : d3.deviation(d.data, dd=>dd.DeltaMax), E_percent_of_DeltaMax_mean: isNaN(d.data[0].E_percent_of_DeltaMax) ? undefined : d3.mean(d.data, dd=>0.01*dd.E_percent_of_DeltaMax), E_percent_of_DeltaMax_sd: isNaN(d.data[0].E_percent_of_DeltaMax) ? undefined : d3.deviation(d.data, dd=>0.01*dd.E_percent_of_DeltaMax), p_percent_of_DeltaMax_mean: isNaN(d.data[0].p_percent_of_DeltaMax) ? undefined : d3.mean(d.data, dd=>0.01*dd.p_percent_of_DeltaMax), p_percent_of_DeltaMax_sd: isNaN(d.data[0].p_percent_of_DeltaMax) ? undefined : d3.deviation(d.data, dd=>0.01*dd.p_percent_of_DeltaMax), P_edge_of_DeltaMax_mean: isNaN(d.data[0].P_edge_of_DeltaMax) ? undefined : d3.mean(d.data, dd=>0.01*dd.P_edge_of_DeltaMax), P_edge_of_DeltaMax_sd: isNaN(d.data[0].P_edge_of_DeltaMax) ? undefined : d3.deviation(d.data, dd=>0.01*dd.P_edge_of_DeltaMax), R_edge_mean: isNaN(d.data[0].R_edge) ? undefined : d3.mean(d.data, dd=>dd.R_edge), R_edge_sd: isNaN(d.data[0].R_edge) ? undefined : d3.deviation(d.data, dd=>dd.R_edge), } }); console.log('serialized', serialize(aggregated_data)) return serialize(aggregated_data) }, "data.csv", "⬇️ DOWNLOAD")34:T3730,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 || 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 || 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 (Cmax<=10) { ctx.strokeStyle = 'rgba(200, 200, 200, 0.8)'; } else 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; d{ 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, R_edge: R_edge }; push_benchmark_data(network.id, layout.id, data); return data; }36:T509,function plot(data) { const AREA = vl.markArea({interpolate: 'monotone', fill: 'rgba(50, 200, 100, 0.06)'}) .data(data.indicators_over_Delta) .encode( vl.x().fieldQ('Delta'), vl.y().fieldQ('E_percent'), vl.y2().fieldQ('p_percent'), ); const E_percent = vl.markLine({interpolate: 'monotone', stroke: 'black'}) .data(data.indicators_over_Delta) .encode( vl.x().fieldQ('Delta'), vl.y().fieldQ('E_percent').title('E% (BLACK)'), ); const p_percent = vl.markLine({interpolate: 'monotone', stroke: 'blue'}) .data(data.indicators_over_Delta) .encode( vl.x().fieldQ('Delta'), vl.y().fieldQ('p_percent').title('p% (BLUE)'), ); const C = vl.markLine({interpolate: 'monotone', stroke: 'green'}) .data(data.indicators_over_Delta) .encode( vl.x().fieldQ('Delta'), vl.y().fieldQ('C').title('C (GREEN)'), ); const DeltaMax_rule = vl.markRule({color: '#0A3'}) .data({values:[{Delta:data.DeltaMax}]}) .encode( vl.x().fieldQ('Delta') ); return vl.layer(AREA, E_percent, p_percent, C, DeltaMax_rule) .title('Indicators over Delta') .width(1000) .height(200) .render(); }37:[] 2f:{"title":"Evaluating the connected-closeness metric (post-design)","cells":[{"id":2031,"value":"md`# Evaluating the connected-closeness metric (post-design)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2026,"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: this notebook has basically the same content as [this one](https://observablehq.com/@jacomyma/evaluating-the-validity-metric-on-different-networks-diff) but with the names and formalism stabilized afterwards during the [design step](https://observablehq.com/@jacomyma/network-layout-designing-a-validity-metric).*\n\nI focus on the systematic visualization and evaluation of maximal connected-closeness ${tex`C_{max}`}, 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: 1000},\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: ${tex`\\Delta_{max}`} 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 DeltaMax:data.DeltaMax,\n E_percent_of_DeltaMax:data.E_percent_of_DeltaMax,\n p_percent_of_DeltaMax:data.p_percent_of_DeltaMax,\n P_edge_of_DeltaMax:data.P_edge_of_DeltaMax,\n Cmax:data.Cmax,\n R_edge:data.R_edge\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.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1783,"value":"md`### ${tex`\\Delta_{max}`}, distance of maximal connected-closeness\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.DeltaMax\n });\n });\n });\n \n // Chart\n return vl.markPoint()\n .data(data)\n .encode(\n vl.x().fieldQ('value').title('Δmax'),\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`### ${tex`C_{max} = C(\\Delta_{max})`}, maximal connected-closeness\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.Cmax\n });\n });\n });\n \n // Chart\n return vl.markPoint()\n .data(data)\n .encode(\n vl.x().fieldQ('value').title('Cmax'),\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`### ${tex`E_{\\%}(\\Delta_{max})`}, Proportion of edges shorter than ${tex`\\Delta_{max}`}\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.E_percent_of_DeltaMax\n });\n });\n });\n \n // Chart\n return vl.markPoint()\n .data(data)\n .encode(\n vl.x().fieldQ('value').title('E%(Δmax)'),\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`### ${tex`p_{\\%}(\\Delta_{max})`}, Proportion of node pairs closer than ${tex`\\Delta_{max}`}\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_percent_of_DeltaMax\n });\n });\n });\n \n // Chart\n return vl.markPoint()\n .data(data)\n .encode(\n vl.x().fieldQ('value').title('p%(Δmax)'),\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`### ${tex`P_{edge}(\\Delta_{max})`}, probability that, considering two nodes closer than the Euclidean distance ${tex`\\Delta_{max}`}, they are 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.P_edge_of_DeltaMax\n });\n });\n });\n \n // Chart\n return vl.markPoint()\n .data(data)\n .encode(\n vl.x().fieldQ('value').title('Pedge(Δmax)'),\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":1976,"value":"md`### ${tex`R_{edge}`}, edge length reduction ratio\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1979,"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.R_edge\n });\n });\n });\n \n // Chart\n return vl.markPoint()\n .data(data)\n .encode(\n vl.x().fieldQ('value').title('Redge'),\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":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":2036,"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":"function serialize (data) {\n let csv = jsonToCSV(data);\n return new Blob([csv], {type: \"text/csv\"}) \n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1895,"value":"jsonToCSV = function(jsonArray) {\n // Extract keys to form the first row (headers)\n const headers = Object.keys(jsonArray[0]);\n const csvRows = [headers.join(',')]; // Create header row\n\n // Loop over the rows and create a CSV string\n jsonArray.forEach(item => {\n const values = headers.map(header => {\n const escaped = ('' + item[header]).replace(/\"/g, '\\\\\"'); // Escape double quotes\n return `\"${escaped}\"`;\n });\n csvRows.push(values.join(','));\n });\n\n // Join all rows into a single string with new lines\n return csvRows.join('\\n');\n}","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":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":926,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":1129,"value":"$36","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":"$W37","stdlib":"1","titling":"auto"}