31:T9f9,md`## What connected-closeness does for us **1. It allows a quantitative statement about the placement of nodes in the visualization.** The simplest statement is "76% of connected nodes are ${tex`\Delta_{max}`} or closer" (of course the numbers vary depending on the network). Since ${tex`\Delta_{max}`} is represented on the picture, it provides quantitative information on the relation between the topology (connectedness) and its representation (closeness). Now, for a more relevant index, we have to take into account the fact that in any placement of the nodes, for a given distance, it is not surprising that *some* node pairs are connected. For instance for a distance greater than the whole network, it is unsurprising that all connected nodes are closer. Bigger distances are expected to catch more edges, and smaller distances fewer. This is why the *difference* matters. **Connected-closeness is this difference** between connected nodes caught by a certain distance, and their *expected* number. This difference is highlighted in the pie chart, and the text helps contextualize the figures. **2. Maximal connected-closeness validates the layout.** Different layouts have different goals, and this metric only accounts for one of them. But at least, it tells you a game at which the layout is good (*if* it is), and *how good* it is. This game is to put connected nodes closer. Now, there are different ways to measure it, and using a particular distance like ${tex`\Delta_{max}`} might not be the most straightforward, although it has other benefits. Still, the metric provides a ground for the narrative that the layout has an effect. **3. It allows comparability.** I explore that point below, but for the moment it suffices to mention that you can compare ${tex`C_{max}`} across networks and layouts pretty consistently. It allows identifying when layouts are efficient, or not. **4. It tells something about the underlying structure of networks.** Force-driven placement algorithms are non-deterministic. It means that from one time to another you run them, they do not provide the same result. One might conclude that they are not reliable. Practice tells otherwise, but it is not easy to quantify how similar are two renderings of the same network, by the same layout algorithm, while all node positions are different. As I show below, not only are ${tex`\Delta_{max}`} and ${tex`C_{max}`} pretty consistent for different executions of the same layout, but sometimes even for different executions of the same network generator. `32:T636,function simplePlot(displayed_networks, displayed_layouts, variable, title, varName) { varName = varName || variable; const usePercentage = [ 'Cmax', 'E_percent_of_DeltaMax', 'p_percent_of_DeltaMax', 'P_edge_of_DeltaMax', 'R_edge' ].some(d=>(d==variable)); const data = stats.filter(d=>{ return displayed_layouts.some(l=>(d.layout_id==l)) && displayed_networks.some(n=>(d.network_id==n)) }); const bars = vl.markErrorbar() .data(data) .encode( vl.x().fieldQ(variable+'_lower').title(''), vl.x2().fieldQ(variable+'_upper'), vl.y().fieldN(displayed_layouts.length>1 ? 'layout_name' : 'network_name') ); let xScaleSettings = {}; if (usePercentage) { xScaleSettings.domain = [0, 1]; } let xAxisSettings = {grid: true}; if (usePercentage) { xAxisSettings.format = '%'; } let yScaleSettings = { domain: displayed_layouts.length>1 ? displayed_layouts.map(layout_id=>layout_index[layout_id].name) : displayed_networks.map(network_id=>network_index[network_id].name) }; const points = vl.markPoint({filled: true, color: '#000'}) .data(data) .encode( vl.x().fieldQ(variable+'_mean') .title(varName+' (100 samples)') .axis(xAxisSettings) .scale(xScaleSettings) , vl.y().fieldN(displayed_layouts.length>1 ? 'layout_name' : 'network_name') .title(displayed_layouts.length>1 ? 'Layout' : 'Network') .scale(yScaleSettings) ); return vl.layer(bars, points) .title(title) .width(500) .render(); }33:T426,md`## Force-directed layouts are pointless on cliques Cliques are the polar opposite of sparse networks, as they are as dense as can be: each node is connected to each other node. Regardless of the distance ${tex`\Delta`}, we always expect all nodes closer than it to be connected. So the connected-closeness ${tex`C(\Delta)`} is always null, and no ${tex`\Delta_{max}`} can emerge. *Reminder: although it is technically possible to pick a value for ${tex`\Delta_{max}`}, as it bears no meaning, it is instead declared "not applicable".* This follows intuition: as every node is connected to every node, they are all topologically equivalent, and placing them on a map is completely pointless. It is actually worse than useless: it manifests distinctions (some are in the middle, others on the side) that do not exist, [anti-patterns](https://en.wikipedia.org/wiki/Anti-pattern). This is not due to a layout in particular, but to the *plane* itself. In 2D, there is no way to put more than three nodes so that the distances between all of them are the same. `34:T496,md`## Random layouts have a structure Here I mean that a realization of a random layout has a notion of "locality", unless it is too dense (clique) or not enough (no edges). That sounds weird considering that all node are on the same level. But they are only equivalent in the model, not in its realization. Once a random network is "played" into an actual data set, that data set may have a structure. Another way to think of it is to mind that the network of C. Elegans featured at the top of this notebook, which clearly has a structure, has a tiny chance to get generated by a random network model. A very, very tiny chance, but there are also many *other* networks that have a structure and can be generated with a random model. ${tex`C_{max}`} provides an opportunity to capture a structure. The structure is the one provided by the statement features in the legend: *"X% of connected nodes are closer than ${tex`\Delta_{max}`}"*. In other words, the layout has something to work with, some edges that can be shortened; the layout has a topological structure to manifest. Take a look first at the visualization. I compare here Force Atlas 2 with a random layout. `35: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.

`36: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)} } ]37:T11cb,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 (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 (square)', 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); }); } } ]38: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; }39:T368e,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; settings.small_legend = settings.small_legend || false; let DeltaMax = data.DeltaMax; let Cmax = data.Cmax; let CmaxThreshold = 10; // 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 >= CmaxThreshold) { 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 && Cmax >= CmaxThreshold)) { 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 && Cmax >= CmaxThreshold) { 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 >= CmaxThreshold) { // Draw the scale drawScaleV(ctx, 20, settings.size/2, DeltaMax_scaled); drawText(ctx, 'Δmax', 25, settings.size/2 + 4, "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) +(settings.small_legend ? `% edges ≤ Δmax` : `% of connected nodes are Δmax or closer` ), settings.size/2, settings.size + 10, "center" ); // Draw pie chart const chartAreaXOffset = settings.size/2 - 300 + (settings.small_legend ? 160 : 0) 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)) +(settings.small_legend ? `% edges ≤ Δmax due to chance` : `% 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) +(settings.small_legend ? `% edges ≤ Δmax due to layout` : `% 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)) +(settings.small_legend ? `% edges > Δmax` : `% of connected nodes are more distant than Δmax` ), chartAreaXOffset + 80, settings.size + 80, "start" ); drawText( ctx, settings.small_legend ? `(2 nodes ≤ Δmax) ⇒ ${Math.round(data.P_edge_of_DeltaMax)}% chance connected` : `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"); } // 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 = settings.small_legend ? "300 12px sans-serif" : "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 NETWORK: ${network.name}.
${network.description} LAYOUT: ${layout.name}.
${layout.description}

${canvas}

`; function generate(drawSettings) { g = network.generator(); layout.layout(g); data = computeData(g, layout); drawSettings = drawSettings || {} drawSettings.size = drawSettings.size || 640; drawSettings.node_size = drawSettings.node_size || 2; drawSettings.edge_thickness = drawSettings.edge_thickness || 0.8; if (drawSettings.edge_color_Dm === undefined) { drawSettings.edge_color_Dm = true } canvas = draw( g, drawSettings, data ).canvas } }3c:T625,preview_x3 = function(displayed_networks, displayed_layouts, drawSettings){ const blocks = []; displayed_networks.forEach(network_id=>{ displayed_layouts.forEach(layout_id=>{ blocks.push({network_id, layout_id}); }) }) const blocks_html = blocks.map(block=>{ const content = drawBlock(block.network_id, block.layout_id, drawSettings); return html`

${content}

` }) return html`

${blocks_html}

`; function drawBlock(network_id, layout_id, drawSettings) { const network = network_index[network_id]; const layout = layout_index[layout_id]; let g, data, canvas, content; generate(drawSettings); return html`

N ${network.name}

L ${layout.name}

${canvas}

${content}

` }) return html`

${blocks_html}

N ${network.name}

L ${layout.name}

${canvas}

`; function generate(drawSettings) { g = network.generator(); layout.layout(g); data = computeData(g, layout); drawSettings = drawSettings || {} drawSettings.node_size = drawSettings.node_size || 2; drawSettings.edge_thickness = drawSettings.edge_thickness || 0.8; drawSettings.small_legend = true; drawSettings.size = 480; if (drawSettings.edge_color_Dm === undefined) { drawSettings.edge_color_Dm = true } canvas = draw( g, drawSettings, data ).canvas } } }3e:[{"id":"520c4f82b7c01b1e66d028507faeed5010f9367e3d95d5e8a4cfc2660c86a02e281805cae35d8d6daa40d4e2d71149622964b4f6672f13a95bf617e76c4e1b6d","href":"https://static.observableusercontent.com/files/520c4f82b7c01b1e66d028507faeed5010f9367e3d95d5e8a4cfc2660c86a02e281805cae35d8d6daa40d4e2d71149622964b4f6672f13a95bf617e76c4e1b6d","name":"C Elegans.gexf","type":"application/xml","lastModified":1584453120303.649,"size":243687},{"id":"33b192d4e1fd10bdb712164d9c0c0edc93e5645655d67b7d08a95d4fa07d133be28b9796d871d35bfb278aa20e89fe994920cac92ce6d57f17abf08c0f9db5e0","href":"https://static.observableusercontent.com/files/33b192d4e1fd10bdb712164d9c0c0edc93e5645655d67b7d08a95d4fa07d133be28b9796d871d35bfb278aa20e89fe994920cac92ce6d57f17abf08c0f9db5e0","name":"connected-closeness data sample=100.csv","type":"text/csv","lastModified":1584458637520.607,"size":20756}] 2f:{"title":"Highlights on connected-closeness","cells":[{"id":0,"value":"md`# Highlights on connected-closeness\n\n***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.***\n\n**Connected-closeness** is a metric I developed to help people make sense of network maps. It is based on the idea that many network maps use force-directed placement algorithms that try to bring connected nodes closer. But at the same time we know that two nodes that are close in the visualization are not necessarily connected, and there are still connected nodes that are far away (the long edges). Connected-closeness aims at quantifying the success of the layout, in the form of a statement about the visualization.\n\nI propose you a tour into interesting questions that connected-closeness allows to formulate and/or visualize. For a more formal definition, I include the equations at the end of the notebook. Here we will engage with it in practice.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":6,"value":"md`## Basic notions\nConnected-closeness is not directly the useful metric. Indeed, it measures the success of a layout as a function of a distance in the image. The more useful notion is the maximum connected-closeness in the picture, and the distance at which it is reached.\n* ${tex`\\Delta_{max}`} is the *distance of maximal connected-closeness*. It is represented in the network map.\n* ${tex`C_{max} = C(\\Delta_{max})`} is the *maximal connected-closeness*. It represents the proportion of connected nodes that are closer than ${tex`\\Delta_{max}`}, but discounting the proportion that would be closer anyways, if the edges were at random.\n\nThat is not super explicit. An actual network map may better help.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":58,"value":"md`## C. Elegans\nMeet the neural network of a little worm known as [Caenorhabditis Elegans](https://en.wikipedia.org/wiki/Caenorhabditis_elegans) (or just C. Elegans). Its network of neurons is a [classic](https://snap.stanford.edu/data/C-elegans-frontal.html) in network science.\n\nThe network has been processed in [Gephi](https://gephi.org/) using the algorithm [Force Atlas 2](https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0098679), with the LinLog setting activated.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":54,"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"},{"id":68,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":83,"value":"md`## Test networks\n\nBelow I will use data generated in [another notebook](https://observablehq.com/@jacomyma/evaluating-the-connected-closeness-metric-post-design). It consists of networks of 100 nodes generated according to different patterns, such as cliques, stars or random edges. Different layouts have been used, too. For a given network generator and a given layout, 100 executions have been done. Each execution has a newly generated network, with randomized starting positions for the nodes. It's important because it means that the average value of ${tex`\\Delta_{max}`} for random networks, for instance, is not the average of 100 renditions of the same layout, but 100 renditions of 100 different random networks.\n\nThe dataset is attached to this notebook, it contains the average value and the standard deviation for each measured feature.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":88,"value":"html`Download the data set as a CSV`","pinned":false,"hidden":false,"mode":"ojs"},{"id":342,"value":"md`## Plotting the results\n\nI use charts like the example down below. Each mark represents the 100 renditions of a given *(network, layout)* pair.\n* The **mean** is represented as a **dot**\n* The **standard deviation** is represented as an **error bar**\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":346,"value":"{\n const displayed_layouts = ['fa2', 'linlog', 'random-round', 'random-graphology'];\n const displayed_networks = ['star'];\n const variable = 'Cmax';\n const title = 'Max connected-closeness (Cmax) / NETWORK: STAR';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":369,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":514,"value":"md`## Summary\n1. **Force-directed layouts do great in the presence of a community structure**\n* **As the community structure decreases, so does connected-closeness**\n* **Randomized layouts suck at connected-closeness**\n* **Force-directed layouts do great on sparse networks**\n* **Force-directed layouts are pointless on cliques**\n* **The denser the network, the lowest ${tex`C_{max}`} is achieved by a force layout**\n* **Density and community structure are not everything**\n* **Bad layouts give bad results**\n* **Random layouts have a structure**\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":452,"value":"md`## Force-directed layouts do great in the presence of a community structure\n\nThis is totally expected. As Noack wrote, [\"Modularity clustering is force-directed layout\"](https://www.semanticscholar.org/paper/Modularity-clustering-is-force-directed-layout-Noack/70588d5549b4d48b181cf66da74296564878ae10). Connected-closeness confirms it: ${tex`C_{max}`} is consistently high for such networks.\n\nIndeed, the typical network with a community structure is the [stochastic block model (SBM)](https://en.wikipedia.org/wiki/Stochastic_block_model). This model has blocks where two nodes have a high probability to be connected, while from one block to the other, two nodes have a low probability to be connected. Take a look at a SBM with an internal probability of 90% and external of 10%. It is rendered by Force Atlas 2, which I consider here the typical force-directed layout.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":459,"value":"preview('sbm-90', 'fa2');","pinned":false,"hidden":false,"mode":"ojs"},{"id":469,"value":"md`The visualization above is just one case, but we have the data for more samples. Down below is the same network model for three different force-directed layout algorithms.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":462,"value":"{\n const displayed_layouts = ['fa2', 'linlog', 'd3'];\n const displayed_networks = ['sbm-90'];\n const variable = 'Cmax';\n const title = 'Max connected-closeness (Cmax) / NETWORK: SBM Pin=90% Pout=10%';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":474,"value":"md`It is remarkable that the maximal connected-closeness is very stable: the standard deviation is very low. And it is not only ${tex`C_{max}`}, but ${tex`\\Delta_{max}`} as well. Despite each rendition of the stochastic block model being a different network, the distance of maximal connected-closeness is extremely stable.\n\n*Note: while ${tex`C_{max}`} is comparable from one layout to another, ${tex`\\Delta_{max}`} is not.*`","pinned":false,"hidden":false,"mode":"ojs"},{"id":477,"value":"{\n const displayed_layouts = ['fa2', 'linlog', 'd3'];\n const displayed_networks = ['sbm-90'];\n const variable = 'DeltaMax';\n const varName = 'Δmax';\n const title = 'Distance of max connected-closeness (Δmax) / NETWORK: SBM Pin=90% Pout=10%';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title, varName);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":683,"value":"md`## As the community structure decreases, so does connected-closeness\n\n**The stochastic block model allows to quantify the influence of the community structure.** Indeed, as the probability ${tex`P_{in}`} drops closer to 50%, the community structure disappears. ${tex`C_{max}`} consequently drops.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":685,"value":"preview_x3(['sbm-999', 'sbm-99', 'sbm-90', 'sbm-80', 'sbm-70', 'sbm-60'], ['fa2']);","pinned":false,"hidden":false,"mode":"ojs"},{"id":697,"value":"{\n const displayed_layouts = ['fa2'];\n const displayed_networks = ['sbm-999', 'sbm-99', 'sbm-90', 'sbm-80', 'sbm-70', 'sbm-60'];\n const variable = 'Cmax';\n const title = 'Max connected-closeness (Cmax) / LAYOUT: FORCE ATLAS 2';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":729,"value":"md`As the low standard variation shows, we could predict very accurately ${tex`C_{max}`} for the stochastic block model and a given layout algorithm.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":339,"value":"md`## Randomized layouts suck at connected-closeness\n...as expected. Indeed, by definition they do not even try to bring connected nodes closer; they put all nodes randomly close regardless of whether or not they are connected. Naturally, heir connected-closeness ${tex`C_{max}`} is close to zero.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":420,"value":"{\n const displayed_layouts = ['random-round', 'random-graphology'];\n const displayed_networks = ['sbm-90'];\n const variable = 'Cmax';\n const title = 'Max connected-closeness (Cmax) / NETWORK: SBM Pin=90% Pout=10%';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":484,"value":"preview('sbm-90', 'random-round');","pinned":false,"hidden":false,"mode":"ojs"},{"id":487,"value":"md`When ${tex`C_{max}`} is below 10%, ${tex`\\Delta_{max}`} is declared \"not applicable\", despite being technically calculable. This is because the Euclidean distance ${tex`\\Delta_{max}`} only has a meaning insofar as ${tex`C_{max}`} is high enough. Else, it just means that connected nodes are never closer than expected. This is what happens here.\n\nIt is neverthess informative here to visualize what it means: the distance varies a lot from one case to another, as a symptom of the difficulty to find the top of a basically flat curve.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":493,"value":"{\n const displayed_layouts = ['random-round', 'random-graphology'];\n const displayed_networks = ['sbm-90'];\n const variable = 'DeltaMax';\n const varName = 'Δmax';\n const title = 'Distance of max connected-closeness (Δmax) / NETWORK: SBM Pin=90% Pout=10%';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title, varName);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":499,"value":"md`So like force-directed layouts, random layout have a *stable* ${tex`C_{max}`}. But contrary to them, they have *high variance* ${tex`\\Delta_{max}`} and their ${tex`C_{max}`} is *close to zero*.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":94,"value":"md`## Force-directed layouts do great on sparse networks\n\nA network is sparse when it does not have many edges. Force-directed layout algorithms succeed very well at bringing connected nodes closer for this type of network.\n\nBelow is a random network with a low probability of edges (0.1%).\n\nNote that there are a few edges, even though they are not so visible. It is easy for the layout to put connected edges closer, as connected pairs are mostly independent.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":131,"value":"preview('rand-01', 'fa2');","pinned":false,"hidden":false,"mode":"ojs"},{"id":508,"value":"{\n const displayed_layouts = ['fa2', 'linlog', 'd3'];\n const displayed_networks = ['rand-01'];\n const variable = 'Cmax';\n const title = 'Max connected-closeness (Cmax) / NETWORK: RANDOM P=0.1%';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":240,"value":"md`Here is another example of a sparse network: a chain.\n\n${tex`\\Delta_{max}`} is highly informative: the distance is short on the network, and it captures almost 100% of the connected pairs above random chance.\n\nAnother metric mentioned in the legend is relevant here: the probability that two nodes closer than ${tex`\\Delta_{max}`} are connected. Here that probability is close to 100%, which is pretty rare.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":245,"value":"preview('chain', 'fa2');","pinned":false,"hidden":false,"mode":"ojs"},{"id":662,"value":"md`If we look at multiple sparse networks rendered by a force-directed layout, we see that ${tex`C_{max}`} is always high, and sometimes close to 100% (see below).`","pinned":false,"hidden":false,"mode":"ojs"},{"id":665,"value":"{\n const displayed_layouts = ['fa2'];\n const displayed_networks = ['rand-01', 'chain', 'sq-latt', 'star'];\n const variable = 'Cmax';\n const title = 'Max connected-closeness (Cmax) / LAYOUT: FORCE ATLAS 2';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":678,"value":"md`Other force-directed layouts provide the same result. Note that for a given *(network, layout)* pair, the variance of ${tex`C_{max}`} is very low (error bars represent the standard deviation for the 100 samples).`","pinned":false,"hidden":false,"mode":"ojs"},{"id":671,"value":"{\n const displayed_layouts = ['linlog'];\n const displayed_networks = ['rand-01', 'chain', 'sq-latt', 'star'];\n const variable = 'Cmax';\n const title = 'Max connected-closeness (Cmax) / LAYOUT: LIN-LOG (FA2 implementation)';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":675,"value":"{\n const displayed_layouts = ['d3'];\n const displayed_networks = ['rand-01', 'chain', 'sq-latt', 'star'];\n const variable = 'Cmax';\n const title = 'Max connected-closeness (Cmax) / LAYOUT: D3 FORCE SIMULATION';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":250,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":252,"value":"preview('clique', 'fa2');","pinned":false,"hidden":false,"mode":"ojs"},{"id":521,"value":"{\n const displayed_layouts = ['fa2', 'linlog', 'd3', 'random-round', 'random-graphology'];\n const displayed_networks = ['clique'];\n const variable = 'Cmax';\n const title = 'Max connected-closeness (Cmax) / NETWORK: CLIQUE';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":524,"value":"md`## The denser the network, the lowest ${tex`C_{max}`} is achieved by a force-directed layout\n\nWe get the intuition from the case of the clique, but we can also see it with random network. Here I compare three of them: with a probability of edges of 0.1%, 5%, and 50%.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":529,"value":"{\n const displayed_layouts = ['fa2'];\n const displayed_networks = ['rand-01', 'rand-5', 'rand-50'];\n const variable = 'Cmax';\n const title = 'Max connected-closeness (Cmax) / LAYOUT: FORCE ATLAS 2';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":620,"value":"md`*Reminder: ${tex`C_{max}`} is the blue share of the pie chart*`","pinned":false,"hidden":false,"mode":"ojs"},{"id":541,"value":"preview_x3(['rand-01', 'rand-5', 'rand-50'], ['fa2']);","pinned":false,"hidden":false,"mode":"ojs"},{"id":631,"value":"md`This is not specific to Force Atlas 2. Other force-directed layouts have the exact same behavior.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":532,"value":"{\n const displayed_layouts = ['linlog'];\n const displayed_networks = ['rand-01', 'rand-5', 'rand-50'];\n const variable = 'Cmax';\n const title = 'Max connected-closeness (Cmax) / LAYOUT: LIN-LOG (FA2 implementation)';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":538,"value":"{\n const displayed_layouts = ['d3'];\n const displayed_networks = ['rand-01', 'rand-5', 'rand-50'];\n const variable = 'Cmax';\n const title = 'Max connected-closeness (Cmax) / LAYOUT: D3 FORCE SIMULATION';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":634,"value":"md`The network maps provide a good insight on what is at play: the denser the network, the higher the amount of connections due to chance (in grey in the pie chart). The situation climaxes with the clique, where there is no room for a ${tex`C_{max}`} above zero.\n\nWe can plot that too. This quantity is noted ${tex`p_\\%(\\Delta_{max})`} and is two things at the same time: (1) the proportion of node pairs closer than ${tex`\\Delta_{max}`}, and (2) the *expected* proportion of *connected* nodes closer than ${tex`\\Delta_{max}`}. The reason why they are the same is the *\"expected\"* means here *\"if edges were at random\"*; in that situation, the probability of two nodes being connected would be independent of the distance between them.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":642,"value":"{\n const displayed_layouts = ['fa2'];\n const displayed_networks = ['rand-01', 'rand-5', 'rand-50'];\n const variable = 'p_percent_of_DeltaMax';\n const varName = 'p%(Δmax)';\n const title = 'Proportion of node pairs closer than Δmax / LAYOUT: FORCE ATLAS 2';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title, varName);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":645,"value":"{\n const displayed_layouts = ['linlog'];\n const displayed_networks = ['rand-01', 'rand-5', 'rand-50'];\n const variable = 'p_percent_of_DeltaMax';\n const varName = 'p%(Δmax)';\n const title = 'Proportion of node pairs closer than Δmax / LAYOUT: LIN-LOG (FA2 implementation)';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title, varName);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":649,"value":"{\n const displayed_layouts = ['d3'];\n const displayed_networks = ['rand-01', 'rand-5', 'rand-50'];\n const variable = 'p_percent_of_DeltaMax';\n const varName = 'p%(Δmax)';\n const title = 'Proportion of node pairs closer than Δmax / LAYOUT: D3 FORCE SIMULATION';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title, varName);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":733,"value":"md`## Density and community structure are not everything\n\nWe have seen that force-directed layouts do better at ${tex`C_{max}`} when a network (1) is less dense, and/or (2) has a community structure.\n\nBut even those two factors are not deciding everything. A good example of this is to compare a *star* with a *chain* network. Those two have the same density, and none has a real community structure. However, force-directed layouts succeed very differently.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":746,"value":"preview_x2(['chain', 'star'], ['fa2']);","pinned":false,"hidden":false,"mode":"ojs"},{"id":750,"value":"{\n const displayed_layouts = ['fa2'];\n const displayed_networks = ['chain', 'star'];\n const variable = 'Cmax';\n const varName = 'Cmax';\n const title = 'Max connected-closeness (Cmax) / LAYOUT: FORCE ATLAS 2';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title, varName);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":757,"value":"md`What happens? We see a topological constraint at play. Look at the star: it is impossible to put the \"leaves\" (as we call them) closer to the central node without having them even closer together. Or, in other words, if we put more space between them, it will also force many of them to be very far away.\n\nThose not-connected leaves end up super close, so there are many pairs of nodes closer than ${tex`\\Delta_{max}`}. We can verify it by looking at ${tex`p_\\%(\\Delta_{max})`}, the expected proportion of edges closer than ${tex`\\Delta_{max}`}. In a more imaged way, it is the grey slice of the pie chart \"eating\" the space of the blue slice.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":761,"value":"{\n const displayed_layouts = ['fa2'];\n const displayed_networks = ['chain', 'star'];\n const variable = 'p_percent_of_DeltaMax';\n const varName = 'p%(Δmax)';\n const title = 'Proportion of node pairs closer than Δmax / LAYOUT: FORCE ATLAS 2';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title, varName);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":774,"value":"md`## Bad layouts give bad results\n\n\"Good\" and \"bad\" may seem opinionated when it comes to layout algorithms. But it does not have to *always* be. I will consider two layouts bad:\n* A random layout is *really bad*, as it does not try to accomplish anything\n* A good layout but with *bad settings* is also bad, but only *half bad*\n\nIn this case I used settings for Force Atlas 2 that are intentionally problematic: the number of iterations is low, and the *gravity* settings has been abused, constraining the network in a too cramped space, and forcing an erratic behavior.\n\nAs a point of reference I will use the Force Atlas 2 as a \"good\" layout. In these tests it scores better than D3 for instance, but that is another question. At least, it is better, by design, than the other two.\n\nFor a test network I will use one that has higher chances to get a good connected-closeness: SBM with ${tex`P_{in}=90%`}.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":777,"value":"preview_x3(['sbm-90'], ['fa2', 'fa2-bad', 'random-round']);","pinned":false,"hidden":false,"mode":"ojs"},{"id":786,"value":"{\n const displayed_layouts = ['fa2', 'fa2-bad', 'random-round'];\n const displayed_networks = ['sbm-90'];\n const variable = 'Cmax';\n const varName = 'Cmax';\n const title = 'Max connected-closeness Cmax / NETWORK: SBM Pin=90%';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title, varName);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":791,"value":"md`The drop in connected-closeness is very clear.\n\nIn the plot below I featured ${tex`\\Delta_{max}`} just because of its standard deviation. Indeed the value itself is not comparable from layout to layout. But the standard deviation is (relatively to the mean). As expected, \"bad\" layouts cause more randomness in the samples.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":783,"value":"{\n const displayed_layouts = ['fa2', 'fa2-bad', 'random-round'];\n const displayed_networks = ['sbm-90'];\n const variable = 'DeltaMax';\n const varName = 'Δmax';\n const title = 'Distance of max connected-closeness / NETWORK: SBM Pin=90%';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title, varName);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":794,"value":"md`The measurable drop in connected-closeness when the layout is \"bad\" works for all networks and not just those that are expected to score high. The effect is just less dramatic. Two examples below, with the star and the lattice.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":803,"value":"md`### Star`","pinned":false,"hidden":false,"mode":"ojs"},{"id":810,"value":"preview_x3(['star'], ['fa2', 'fa2-bad', 'random-round']);","pinned":false,"hidden":false,"mode":"ojs"},{"id":813,"value":"{\n const displayed_layouts = ['fa2', 'fa2-bad', 'random-round'];\n const displayed_networks = ['star'];\n const variable = 'Cmax';\n const varName = 'Cmax';\n const title = 'Max connected-closeness Cmax / NETWORK: STAR';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title, varName);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":806,"value":"md`### Square lattice`","pinned":false,"hidden":false,"mode":"ojs"},{"id":797,"value":"preview_x3(['sq-latt'], ['fa2', 'fa2-bad', 'random-round']);","pinned":false,"hidden":false,"mode":"ojs"},{"id":799,"value":"{\n const displayed_layouts = ['fa2', 'fa2-bad', 'random-round'];\n const displayed_networks = ['sq-latt'];\n const variable = 'Cmax';\n const varName = 'Cmax';\n const title = 'Max connected-closeness Cmax / NETWORK: SQUARE LATTICE';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title, varName);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":820,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":834,"value":"preview_x2(['rand-5'], ['fa2', 'random-round']);","pinned":false,"hidden":false,"mode":"ojs"},{"id":842,"value":"md`The two placements may not seem very different: a bunch of nodes scattered all over the place, without a center or a community structure, and cluttered edges. Nevertheless the layout accomplished something, as connected-closeness tells us.\n\nWhat the layout accomplishes, i.e. a high ${tex`C_{max}`}, is remarkably consistent: around 56% in our case, as statistics show below. And it works with other layouts too.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":829,"value":"{\n const displayed_layouts = ['fa2', 'linlog', 'd3'];\n const displayed_networks = ['rand-5'];\n const variable = 'Cmax';\n const varName = 'Cmax';\n const title = 'Max connected-closeness Cmax / NETWORK: RANDOM P=5%';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title, varName);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":851,"value":"md`But of course, random *layouts* do not capture the structure of random *networks*. They even fail consistently.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":854,"value":"{\n const displayed_layouts = ['random-round', 'random-graphology'];\n const displayed_networks = ['rand-5'];\n const variable = 'Cmax';\n const varName = 'Cmax';\n const title = 'Max connected-closeness Cmax / NETWORK: RANDOM P=5%';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title, varName);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":850,"value":"md`As expected, the denser a random network, the lower its maximal connected-closeness. But layouts still succeed to capture a structure.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":862,"value":"{\n const displayed_layouts = ['fa2', 'linlog', 'd3'];\n const displayed_networks = ['rand-50'];\n const variable = 'Cmax';\n const varName = 'Cmax';\n const title = 'Max connected-closeness Cmax / NETWORK: RANDOM P=50%';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title, varName);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":865,"value":"{\n const displayed_layouts = ['random-round', 'random-graphology'];\n const displayed_networks = ['rand-50'];\n const variable = 'Cmax';\n const varName = 'Cmax';\n const title = 'Max connected-closeness Cmax / NETWORK: RANDOM P=50%';\n \n return simplePlot(displayed_networks, displayed_layouts, variable, title, varName);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":871,"value":"md`# Formal definition of connected-closeness`","pinned":false,"hidden":false,"mode":"ojs"},{"id":874,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":877,"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"},{"id":11,"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":14,"value":"Graph = require('graphology@0.17.1/dist/graphology.umd.min.js')","pinned":false,"hidden":false,"mode":"ojs"},{"id":898,"value":"GraphologyLibrary = require('graphology-library@0.3.0/dist/graphology-library.min.js')","pinned":false,"hidden":false,"mode":"ojs"},{"id":17,"value":"gexf = GraphologyLibrary.gexf","pinned":false,"hidden":false,"mode":"ojs"},{"id":20,"value":"networkGEXF = FileAttachment(\"C Elegans.gexf\").text()","pinned":false,"hidden":false,"mode":"ojs"},{"id":24,"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"},{"id":27,"value":"data = computeData(g);","pinned":false,"hidden":false,"mode":"ojs"},{"id":29,"value":"md`### Require d3`","pinned":false,"hidden":false,"mode":"ojs"},{"id":32,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":35,"value":"md`### Load Vega Lite for plotting`","pinned":false,"hidden":false,"mode":"ojs"},{"id":38,"value":"import {vl} from '@vega/vega-lite-api'","pinned":false,"hidden":false,"mode":"ojs"},{"id":279,"value":"md`### Load and parse stats`","pinned":false,"hidden":false,"mode":"ojs"},{"id":280,"value":"stats_text = FileAttachment(\"connected-closeness data sample=100.csv\").text()","pinned":false,"hidden":false,"mode":"ojs"},{"id":285,"value":"stats = {\n let stats = d3.csvParse(stats_text, d3.autoType);\n stats.forEach(d=>{\n d.network_name = network_index[d.network_id].name;\n d.layout_name = layout_index[d.layout_id].name;\n ['Cmax', 'DeltaMax', 'E_percent_of_DeltaMax', 'p_percent_of_DeltaMax', 'P_edge_of_DeltaMax', 'R_edge'].forEach(attr=>{\n d[attr+'_lower'] = d[attr+'_mean'] - d[attr+'_sd']/2;\n d[attr+'_upper'] = d[attr+'_mean'] + d[attr+'_sd']/2;\n });\n });\n return stats\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":101,"value":"md`### Network generators`","pinned":false,"hidden":false,"mode":"ojs"},{"id":107,"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":110,"value":"reference_order = 100","pinned":false,"hidden":false,"mode":"ojs"},{"id":104,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":113,"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":116,"value":"md`### Layouts`","pinned":false,"hidden":false,"mode":"ojs"},{"id":123,"value":"graphLayout = require('https://bundle.run/graphology-layout@0.3.2')","pinned":false,"hidden":false,"mode":"ojs"},{"id":125,"value":"fa2 = require('https://bundle.run/graphology-layout-forceatlas2@0.5.2')","pinned":false,"hidden":false,"mode":"ojs"},{"id":119,"value":"$37","pinned":false,"hidden":false,"mode":"ojs"},{"id":121,"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":41,"value":"md`### Routines`","pinned":false,"hidden":false,"mode":"ojs"},{"id":44,"value":"$38","pinned":false,"hidden":false,"mode":"ojs"},{"id":48,"value":"$39","pinned":false,"hidden":false,"mode":"ojs"},{"id":51,"value":"$3a","pinned":false,"hidden":false,"mode":"ojs"},{"id":133,"value":"$3b","pinned":false,"hidden":false,"mode":"ojs"},{"id":544,"value":"$3c","pinned":false,"hidden":false,"mode":"ojs"},{"id":742,"value":"$3d","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W3e","stdlib":"1","titling":"auto"}