31:T11ad,computeConnectedCloseness = function(g, settings){ // Default settings settings = settings || {} settings.epsilon = settings.epsilon || 0.03; // 3% settings.grid_size = settings.grid_size || 10; // This is an optimization thing, it's not the graphical grid const pairs_of_nodes_sampled = sample_pairs_of_nodes(); const connected_pairs = g.edges().map(eid => { const n1 = g.getNodeAttributes(g.source(eid)); const n2 = g.getNodeAttributes(g.target(eid)); const d = Math.sqrt(Math.pow(n1.x-n2.x, 2)+Math.pow(n1.y-n2.y, 2)); return d; }) // Grid search for C_max let range = [0, Math.max(d3.max(pairs_of_nodes_sampled), d3.max(connected_pairs))]; let C_max = 0; let distances_index = {}; let Delta, old_C_max, C, i, target_index, indicators_over_Delta; do { for(i=0; i<=settings.grid_size; i++){ Delta = range[0] + (range[1]-range[0]) * i / settings.grid_size; if (distances_index[Delta] === undefined) { distances_index[Delta] = computeIndicators(Delta, g, pairs_of_nodes_sampled, connected_pairs); } } old_C_max = C_max; C_max = 0; indicators_over_Delta = Object.values(distances_index); indicators_over_Delta.forEach((indicators, i) => { C = indicators.C; if (C > C_max) { C_max = C; target_index = i; } }); range = [ indicators_over_Delta[Math.max(0, target_index-1)].Delta, indicators_over_Delta[Math.min(indicators_over_Delta.length-1, target_index+1)].Delta ] } while ( (C_max-old_C_max)/C_max >= settings.epsilon/10 ) const Delta_max = find_Delta_max(indicators_over_Delta, settings.epsilon); const indicators_of_Delta_max = computeIndicators(Delta_max, g, pairs_of_nodes_sampled, connected_pairs); // Resistance to misinterpretation if (indicators_of_Delta_max.C < 0.1) { return { undefined, E_percent_of_Delta_max: undefined, p_percent_of_Delta_max: undefined, P_edge_of_Delta_max: undefined, C_max: indicators_of_Delta_max.C } } else { return { Delta_max, E_percent_of_Delta_max: indicators_of_Delta_max.E_percent, p_percent_of_Delta_max: indicators_of_Delta_max.p_percent, P_edge_of_Delta_max: indicators_of_Delta_max.P_edge, C_max: indicators_of_Delta_max.C } } // Internal methods // Compute indicators given a distance Delta function computeIndicators(Delta, g, pairs_of_nodes_sampled, connected_pairs) { const connected_pairs_below_Delta = connected_pairs.filter(d => d<=Delta); const pairs_below_Delta = pairs_of_nodes_sampled.filter(d => d<=Delta); // Count of edges shorter than Delta // note: actual count const E = connected_pairs_below_Delta.length; // Proportion of edges shorter than Delta // note: actual count const E_percent = E / connected_pairs.length; // Count of node pairs closer than Delta // note: sampling-dependent const p = pairs_below_Delta.length; // Proportion of node pairs closer than Delta // note: sampling-dependent, but it cancels out const p_percent = p / pairs_of_nodes_sampled.length; // Connected closeness const C = E_percent - p_percent; // Probability that, considering two nodes closer than Delta, they are connected // note: p is sampling-dependent, so we have to normalize it here. const possible_edges_per_pair = g.undirected ? 1 : 2; const P_edge = E / (possible_edges_per_pair * p * (g.order * (g.order-1)) / pairs_of_nodes_sampled.length); return { Delta, E_percent, p_percent, P_edge, // Note: P_edge is complentary information, not strictly necessary C }; } function sample_pairs_of_nodes(){ if (g.order<2) return []; let samples = []; let node1, node2, n1, n2, d, c; const samples_count = g.size; // We want as many samples as edges if (samples_count<1) return []; for (let i=0; i d.C); const Delta_max = d3.min( indicators_over_Delta.filter(d => ( d.C >= (1-epsilon) * C_max ) ), d => d.Delta ); return Delta_max; } }32:T36ba,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 Delta_max = data.Delta_max; let C_max = data.C_max; let C_max_threshold = 0.1; // 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 Delta_max_scaled = Delta_max * (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 (C_max >= C_max_threshold) { drawGrid(Delta_max_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 && C_max >= C_max_threshold)) { 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 && C_max >= C_max_threshold) { if (d <= Delta_max * 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 (C_max >= C_max_threshold) { // Draw the scale drawScaleV(ctx, 20, settings.size/2, Delta_max_scaled); drawText(ctx, 'Δmax', 25, settings.size/2 + 4, "start"); drawScaleH(ctx, settings.size/2, settings.size-20, Delta_max_scaled); drawText(ctx, 'Δmax', settings.size/2, settings.size -28, "center"); drawText( ctx, Math.round(100*data.E_percent_of_Delta_max) +(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(100*data.E_percent_of_Delta_max) - Math.round(100*data.C_max)) +(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(100*data.C_max) +(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(100*data.C_max)-Math.round(100*data.E_percent_of_Delta_max)+Math.round(100*data.C_max)) +(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(100*data.P_edge_of_Delta_max)}% chance connected` : `Two nodes closer than Δmax have a ${Math.round(100*data.P_edge_of_Delta_max)}% 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); Delta_max *= 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_Delta_max-data.C_max), '#DDD'); drawPieSlice(pieChartCenterX, pieChartCenterY, pieChartR, (data.E_percent_of_Delta_max-data.C_max), data.C_max, 'rgb(49, 130, 189)'); drawPieSlice(pieChartCenterX, pieChartCenterY, pieChartR, (data.E_percent_of_Delta_max), (1-data.E_percent_of_Delta_max), '#FFF'); drawPieSliceBorder(pieChartCenterX, pieChartCenterY, pieChartR, 0, (data.E_percent_of_Delta_max-data.C_max)); drawPieSliceBorder(pieChartCenterX, pieChartCenterY, pieChartR, (data.E_percent_of_Delta_max-data.C_max), data.C_max); drawPieSliceBorder(pieChartCenterX, pieChartCenterY, pieChartR, (data.E_percent_of_Delta_max), (1-data.E_percent_of_Delta_max)); 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{\n let n = g.getNodeAttributes(nid);\n n.y = -n.y;\n });\n return g;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":22,"value":"md`The naïve algorithm goes as follows:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":64,"value":"md`#### 1. Compute all the distances between pairs of nodes\nAlso store the information that the pair of nodes is connected or not.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":68,"value":"pairs_of_nodes_index = (()=>{\n let p = {};\n const nlist = g.nodes();\n for (let i=0; i{\n let pairs = d3.values(pairs_of_nodes_index).map(d=>{\n return d;\n });\n // Sort from longest to shortest (a trick used only for visualization)\n pairs.sort(function(a,b){return b.d-a.d});\n pairs.forEach((d,i)=>{d.rank = i});\n return pairs;\n })();","pinned":false,"hidden":false,"mode":"ojs"},{"id":79,"value":"md`#### 2. Sample the distances\nThe distances relevant to the algorithm do not exceed the maximal distance of all pairs of nodes. Build a data set of distances ranging from zero to the maximal distance, with a high enough precision.\n\nHere I choose to have at least 100 data points. I use the *scale* feature of D3 which picks round values and generally gives more data points.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":80,"value":"distances = d3.scaleLinear()\n .domain(d3.extent(pairs_of_nodes_list, d=>d.d))\n .nice()\n .ticks(100);","pinned":false,"hidden":false,"mode":"ojs"},{"id":88,"value":"md`#### 3. Compute indicators for each distance\nThese indicators are based on counting the pairs of nodes, looking at whether or not they are closer than the distance, and whether or not they are connected.\n\nNote: I use the formalism of the equation, where the Euclidean distance between nodes is noted ${tex`\\Delta`} (Delta).\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":91,"value":"computeIndicators = function(Delta, g, pairs_of_nodes_list) {\n const connected_pairs = pairs_of_nodes_list.filter(d => d.c);\n const connected_pairs_below_Delta = connected_pairs.filter(d => d.d<=Delta);\n const pairs_below_Delta = pairs_of_nodes_list.filter(d => d.d<=Delta);\n\n // Count of edges shorter than Delta\n const E = connected_pairs_below_Delta.length;\n\n // Proportion of edges shorter than Delta\n const E_percent = E / connected_pairs.length;\n\n // Count of node pairs closer than Delta\n const p = pairs_below_Delta.length;\n\n // Proportion of node pairs closer than Delta\n const p_percent = p / pairs_of_nodes_list.length;\n\n // Connected closeness\n const C = E_percent - p_percent;\n\n // Probability that, considering two nodes closer than Delta, they are connected\n const P_edge = E / p;\n\n return {\n Delta,\n E_percent,\n p_percent,\n P_edge, // Note: P_edge is complentary information, not strictly necessary\n C\n };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":97,"value":"indicators_over_Delta = distances.map(Delta => computeIndicators(Delta, g, pairs_of_nodes_list))","pinned":false,"hidden":false,"mode":"ojs"},{"id":104,"value":"md`At this point we can plot each of the four indicators we have computed for all the distances:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":107,"value":"vl.markLine({interpolate: 'monotone', stroke: 'black'})\n .data(indicators_over_Delta)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('E_percent').title('E_% (Δ)').axis({format: '%'}),\n )\n .title('E_% (Δ) Proportion of edges shorter than Δ')\n .width(640)\n .height(120)\n .render();","pinned":false,"hidden":false,"mode":"ojs"},{"id":125,"value":"vl.markLine({interpolate: 'monotone', stroke: 'black'})\n .data(indicators_over_Delta)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('p_percent').title('p_% (Δ)').axis({format: '%'}),\n )\n .title('p_% (Δ) Proportion of node pairs shorter than Δ')\n .width(640)\n .height(120)\n .render();","pinned":false,"hidden":false,"mode":"ojs"},{"id":130,"value":"vl.markLine({interpolate: 'monotone', stroke: 'black'})\n .data(indicators_over_Delta)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('C').title('C(Δ)').axis({format: '%'}),\n )\n .title('C(Δ) Connected-closeness of Δ')\n .width(640)\n .height(120)\n .render();","pinned":false,"hidden":false,"mode":"ojs"},{"id":137,"value":"md`${tex`E_{\\%}(\\Delta)`} rises quickly, since the attraction force of the layout tries to shorten the edges, while ${tex`p_{\\%}(\\Delta)`} rises more progressively, as the repulsion force of the layout tries to spread the nodes. Connected-closeness ${tex`C(\\Delta)`} is the difference between the two, and accordingly culminates somewhere between zero and the maximal distance. It has to, as both ends are null, unless it is totally flat (it happens for cliques).\n\nThe goal of the algorithm is to find the maximum ${tex`C_{max} = C(\\Delta_{max})`}.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":147,"value":"md`### 4. Pick the max of ${tex`C(\\Delta)`} to define ${tex`\\Delta_{max}`} and its indicators\n\nThe simplest way to do it would be to just pick the max value inside our sampling; but there is an issue. Indeed in some cases (not this one) the curve of ${tex`C(\\Delta)`} has a plateau on top. It is flat, and quite different values of ${tex`\\Delta`} are almost as good candidates for the title of ${tex`\\Delta_{max}`}. However, it is always better to have the smallest ${tex`\\Delta_{max}`} possible, especially considering that the resulting ${tex`C_{max}`} would be basically the same.\n\nIn order to deal with the plateau issue, we allow a small approximation captured by the variable ${tex`\\epsilon`}, equal to a small percentage. In practice, we pick for ${tex`\\Delta_{max}`} the *smallest* ${tex`\\Delta`} for which ${tex`C`} is *almost* maximal:\n\n${tex`\\Delta_{max} \\text{ is the smallest value verifying } C(\\Delta_{max}) \\geq (1-\\epsilon) \\times C_{max}`}\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":167,"value":"epsilon = 0.03; // 3%","pinned":false,"hidden":false,"mode":"ojs"},{"id":170,"value":"find_Delta_max = function(indicators_over_Delta, epsilon) {\n const C_max = d3.max(indicators_over_Delta, d => d.C);\n const Delta_max = d3.min(\n indicators_over_Delta.filter(d => (\n d.C >= (1-epsilon) * C_max\n )\n ),\n d => d.Delta\n );\n return Delta_max;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":174,"value":"Delta_max = find_Delta_max(indicators_over_Delta, epsilon);","pinned":false,"hidden":false,"mode":"ojs"},{"id":185,"value":"indicators_of_Delta_max = computeIndicators(Delta_max, g, pairs_of_nodes_list);","pinned":false,"hidden":false,"mode":"ojs"},{"id":192,"value":"md`## A more efficient implementation\n\nA remark first. This implementation will make approximations, but the naïve implementation is not exact either. Not only because of that ${tex`\\epsilon`} trick, but also because we sampled the distances.\n\nTwo obvious points can be improved:\n* Use a sampling of edges and node pairs instead of using all of them.\n* Find ${tex`C_{max}`} more efficiently than testing every distance\n\nThe main bottleneck lies in the first point, as it causes the scalability issues.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":197,"value":"md`### Sampling node pairs\n\nThe actual thing we want to know is twofold:\n* How many pairs are closer than a certain distance ${tex`\\Delta`} (that varies)\n* How many *connected* pairs (edges) are closer than ${tex`\\Delta`}\n\nWe might be fine with just an estimation, as long as it allows finding these information with sufficient accuracy. Let's experiment with that.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":212,"value":"html`\nSp\n${viewof Sp.bind(html``)}\n${viewof Sp.bind(html``)}\n%\n
\nPercentage of sampled node pairs\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":235,"value":"function sample_pairs_of_nodes(g, Sp){\n if (g.order<2) return [];\n let samples = [];\n let node1, node2, n1, n2, d, c;\n const total_of_pairs = g.order * (g.order-1);\n const samples_count = total_of_pairs * Sp / 100;\n if (samples_count<1) return [];\n for (let i=0; i computeIndicators(Delta, g, pairs_of_nodes_sampled))","pinned":false,"hidden":false,"mode":"ojs"},{"id":253,"value":"{\n const baseline = vl.markLine({interpolate: 'monotone', stroke: 'grey'})\n .data(indicators_over_Delta)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('E_percent').title('E_% (Δ)').axis({format: '%'}),\n )\n \n const sampled = vl.markLine({interpolate: 'monotone', stroke: 'black'})\n .data(indicators_over_Delta_sampled)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('E_percent').title('E_% (Δ)').axis({format: '%'}),\n )\n \n return vl.layer(baseline, sampled)\n .title('E_% (Δ) Proportion of edges shorter than Δ')\n .width(640)\n .height(120)\n .render();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":268,"value":"{\n const baseline = vl.markLine({interpolate: 'monotone', stroke: 'grey'})\n .data(indicators_over_Delta)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('p_percent').title('p_% (Δ)').axis({format: '%'}),\n )\n \n const sampled = vl.markLine({interpolate: 'monotone', stroke: 'black'})\n .data(indicators_over_Delta_sampled)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('p_percent').title('p_% (Δ)').axis({format: '%'}),\n )\n \n return vl.layer(baseline, sampled)\n .title('p_% (Δ) Proportion of node pairs shorter than Δ')\n .width(640)\n .height(120)\n .render();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":267,"value":"{\n const baseline = vl.markLine({interpolate: 'monotone', stroke: 'grey'})\n .data(indicators_over_Delta)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('C').title('C(Δ)').axis({format: '%'}),\n )\n \n const sampled = vl.markLine({interpolate: 'monotone', stroke: 'black'})\n .data(indicators_over_Delta_sampled)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('C').title('C(Δ)').axis({format: '%'}),\n )\n \n return vl.layer(baseline, sampled)\n .title('C(Δ) Connected-closeness for Δ')\n .width(640)\n .height(120)\n .render();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":326,"value":"Delta_max_sampled = find_Delta_max(indicators_over_Delta_sampled, epsilon);","pinned":false,"hidden":false,"mode":"ojs"},{"id":329,"value":"indicators_of_Delta_max_sampled = computeIndicators(Delta_max_sampled, g, pairs_of_nodes_sampled);","pinned":false,"hidden":false,"mode":"ojs"},{"id":275,"value":"md`As one can see, the results are already satisfying for a 10% sampling, and acceptable for as low as a few percents. Let us compute the average error for ${tex`C(\\Delta)`}, and something even more important, the error of ${tex`C_{max}`} and ${tex`\\Delta_{max}`}.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":280,"value":"average_error_C = d3.mean(\n indicators_over_Delta_sampled.map((indicators_sampled, i)=>{\n const indicators = indicators_over_Delta[i];\n const error = Math.abs(indicators.C - indicators_sampled.C)/indicators.C;\n return error;\n })\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":324,"value":"Delta_max_error = Math.abs(Delta_max - Delta_max_sampled)/Delta_max;","pinned":false,"hidden":false,"mode":"ojs"},{"id":338,"value":"C_max_error = Math.abs(indicators_of_Delta_max.C - indicators_of_Delta_max_sampled.C)/indicators_of_Delta_max.C;","pinned":false,"hidden":false,"mode":"ojs"},{"id":343,"value":"md`The error of ${tex`C_{max}`} and ${tex`\\Delta_{max}`} is lower than the average error. Indeed the whole curve is not so important, its profile and maximum are the important thing for our calculations.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":294,"value":"md`But we can do even better. Indeed one can assume that the list of edges is known, and many large networks are sparse. In such situation we can compute the indicators using the sampling AND the list of edges. The underlying idea is that the count of edges scales more gracefully than the count of nodes *squared* .`","pinned":false,"hidden":false,"mode":"ojs"},{"id":301,"value":"connected_pairs = g.edges().map(eid => {\n const n1 = g.getNodeAttributes(g.source(eid));\n const n2 = g.getNodeAttributes(g.target(eid));\n const d = Math.sqrt(Math.pow(n1.x-n2.x, 2)+Math.pow(n1.y-n2.y, 2));\n return {d};\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":298,"value":"computeIndicators_2 = function(Delta, g, pairs_of_nodes_list, connected_pairs) {\n const connected_pairs_below_Delta = connected_pairs.filter(d => d.d<=Delta);\n const pairs_below_Delta = pairs_of_nodes_list.filter(d => d.d<=Delta);\n\n // Count of edges shorter than Delta\n const E = connected_pairs_below_Delta.length;\n\n // Proportion of edges shorter than Delta\n const E_percent = E / connected_pairs.length;\n\n // Count of node pairs closer than Delta\n const p = pairs_below_Delta.length;\n\n // Proportion of node pairs closer than Delta\n const p_percent = p / pairs_of_nodes_list.length;\n\n // Connected closeness\n const C = E_percent - p_percent;\n\n // Probability that, considering two nodes closer than Delta, they are connected\n const P_edge = E / p;\n\n return {\n Delta,\n E_percent,\n p_percent,\n P_edge, // Note: P_edge is complentary information, not strictly necessary\n C\n };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":306,"value":"indicators_over_Delta_sampled_2 = distances.map(Delta => computeIndicators_2(Delta, g, pairs_of_nodes_sampled, connected_pairs));","pinned":false,"hidden":false,"mode":"ojs"},{"id":371,"value":"html`\nSp\n${viewof Sp.bind(html``)}\n${viewof Sp.bind(html``)}\n%\n
\nPercentage of sampled node pairs\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":363,"value":"{\n const baseline = vl.markLine({interpolate: 'monotone', stroke: 'grey'})\n .data(indicators_over_Delta)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('E_percent').title('E_% (Δ)').axis({format: '%'}),\n )\n \n const sampled = vl.markLine({interpolate: 'monotone', stroke: 'black'})\n .data(indicators_over_Delta_sampled_2)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('E_percent').title('E_% (Δ)').axis({format: '%'}),\n )\n \n return vl.layer(baseline, sampled)\n .title('E_% (Δ) Proportion of edges shorter than Δ')\n .width(640)\n .height(120)\n .render();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":366,"value":"{\n const baseline = vl.markLine({interpolate: 'monotone', stroke: 'grey'})\n .data(indicators_over_Delta)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('p_percent').title('p_% (Δ)').axis({format: '%'}),\n )\n \n const sampled = vl.markLine({interpolate: 'monotone', stroke: 'black'})\n .data(indicators_over_Delta_sampled_2)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('p_percent').title('p_% (Δ)').axis({format: '%'}),\n )\n \n return vl.layer(baseline, sampled)\n .title('p_% (Δ) Proportion of node pairs shorter than Δ')\n .width(640)\n .height(120)\n .render();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":311,"value":"{\n const baseline = vl.markLine({interpolate: 'monotone', stroke: 'grey'})\n .data(indicators_over_Delta)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('C').title('C(Δ)').axis({format: '%'}),\n )\n \n const sampled = vl.markLine({interpolate: 'monotone', stroke: 'black'})\n .data(indicators_over_Delta_sampled_2)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('C').title('C(Δ)').axis({format: '%'}),\n )\n \n return vl.layer(baseline, sampled)\n .title('C(Δ) Connected-closeness for Δ')\n .width(640)\n .height(120)\n .render();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":348,"value":"Delta_max_sampled_2 = find_Delta_max(indicators_over_Delta_sampled_2, epsilon);","pinned":false,"hidden":false,"mode":"ojs"},{"id":350,"value":"indicators_of_Delta_max_sampled_2 = computeIndicators_2(Delta_max_sampled_2, g, pairs_of_nodes_sampled, connected_pairs);","pinned":false,"hidden":false,"mode":"ojs"},{"id":314,"value":"average_error_C_2 = d3.mean(\n indicators_over_Delta_sampled_2.map((indicators_sampled, i)=>{\n const indicators = indicators_over_Delta[i];\n const error = Math.abs(indicators.C - indicators_sampled.C)/indicators.C;\n return error;\n })\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":356,"value":"Delta_max_error_2 = Math.abs(Delta_max - Delta_max_sampled_2)/Delta_max;","pinned":false,"hidden":false,"mode":"ojs"},{"id":359,"value":"C_max_error_2 = Math.abs(indicators_of_Delta_max.C - indicators_of_Delta_max_sampled_2.C)/indicators_of_Delta_max.C;","pinned":false,"hidden":false,"mode":"ojs"},{"id":317,"value":"md`The result is much better, especially for the low sampling percentages. It remains usable even below 1%.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":374,"value":"md`Small samples are good, amazing. **But what percentage should we use?** It is possible that we do a calculation based on an assumption on the distribution of edge lengths, but this is out of my skills and I don't like it for another reason: networks can be very different, and I suspect that edge length distributions can be, too.\n\nI will keep things simple. Since our calculations scale with the number of edges, picking that very number for our sample size is coherent. **As many pairs as edges.** It will not create any additional scalability issue.\n\n*Note: in our test case, this means a sampling percentage of ${Math.round((g.size/(g.order*(g.order-1)))*1000)/10}%*.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":385,"value":"md`## Finding the max of the ${tex`C(\\Delta)`} curve`","pinned":false,"hidden":false,"mode":"ojs"},{"id":389,"value":"md`Even on weird edge cases like random layouts applied on random networks, the curves remain relatively smooth. You can check this out in [this notebook](https://observablehq.com/@jacomyma/evaluating-the-connected-closeness-metric-post-design?collection=@jacomyma/quest-for-connected-closeness). This assumption is very useful for finding a maximum efficiently.\n\nI propose a simple variation on a \"grid search\". We split the range of distances in a number of equal parts, and we pick the part that is the most promising. Here, where ${tex`C(\\Delta)`} is the highest. Then we iterate until the precision is satisfying: we split the promising part again, and so on.\n\nLet us visualize what happens for three iterations.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":396,"value":"grid_size = 7;","pinned":false,"hidden":false,"mode":"ojs"},{"id":402,"value":"distance_max_sampled = d3.max(pairs_of_nodes_sampled, d => d.d)","pinned":false,"hidden":false,"mode":"ojs"},{"id":400,"value":"distances_iteration_1 = {\n let dataset = [];\n for(let i=0; i<=grid_size; i++){\n dataset.push(i*distance_max_sampled/grid_size)\n }\n return dataset;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":410,"value":"indicators_over_Delta_iteration_1 = distances_iteration_1.map(Delta => computeIndicators_2(Delta, g, pairs_of_nodes_sampled, connected_pairs));","pinned":false,"hidden":false,"mode":"ojs"},{"id":413,"value":"{\n const baseline = vl.markLine({interpolate: 'monotone', stroke: 'grey'})\n .data(indicators_over_Delta)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('C'),\n )\n \n const sampled = vl.markLine({stroke: 'black'})\n .data(indicators_over_Delta_iteration_1)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('C'),\n )\n \n const sampledDots = vl.markPoint({stroke: 'black', fill:'black'})\n .data(indicators_over_Delta_iteration_1)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('C').title('C(Δ)').axis({format: '%'}),\n )\n \n return vl.layer(baseline, sampled, sampledDots)\n .title('C(Δ) Connected-closeness for Δ')\n .width(640)\n .height(120)\n .render();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":431,"value":"md`For the next iteration, we pick the highest index, and then we pick the range from one index before to one index after (unless the good index is the first or the last).`","pinned":false,"hidden":false,"mode":"ojs"},{"id":422,"value":"highest_index_at_iteration_1 = {\n let max_C = -1;\n let max_i;\n indicators_over_Delta_iteration_1.forEach((indicators, i)=>{\n if (indicators.C > max_C) {\n max_C = indicators.C;\n max_i = i;\n }\n });\n return max_i;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":426,"value":"target_range_at_iteration_1 = [\n indicators_over_Delta_iteration_1[Math.max(0, highest_index_at_iteration_1-1)].Delta,\n indicators_over_Delta_iteration_1[Math.min(highest_index_at_iteration_1+1, indicators_over_Delta_iteration_1.length-1)].Delta\n]","pinned":false,"hidden":false,"mode":"ojs"},{"id":442,"value":"distances_iteration_2 = {\n let dataset = distances_iteration_1.slice(0);\n for(let i=1; i computeIndicators_2(Delta, g, pairs_of_nodes_sampled, connected_pairs));","pinned":false,"hidden":false,"mode":"ojs"},{"id":445,"value":"{\n const baseline = vl.markLine({interpolate: 'monotone', stroke: 'grey'})\n .data(indicators_over_Delta)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('C'),\n )\n \n const sampled = vl.markLine({stroke: 'black'})\n .data(indicators_over_Delta_iteration_2)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('C'),\n )\n \n const sampledDots = vl.markPoint({stroke: 'black', fill:'black'})\n .data(indicators_over_Delta_iteration_2)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('C').title('C(Δ)').axis({format: '%'}),\n )\n \n return vl.layer(baseline, sampled, sampledDots)\n .title('C(Δ) Connected-closeness for Δ')\n .width(640)\n .height(120)\n .render();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":453,"value":"highest_index_at_iteration_2 = {\n let max_C = -1;\n let max_i;\n indicators_over_Delta_iteration_2.forEach((indicators, i)=>{\n if (indicators.C > max_C) {\n max_C = indicators.C;\n max_i = i;\n }\n });\n return max_i;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":458,"value":"target_range_at_iteration_2 = [\n indicators_over_Delta_iteration_2[Math.max(0, highest_index_at_iteration_2-1)].Delta,\n indicators_over_Delta_iteration_2[Math.min(highest_index_at_iteration_2+1, indicators_over_Delta_iteration_2.length-1)].Delta\n]","pinned":false,"hidden":false,"mode":"ojs"},{"id":461,"value":"distances_iteration_3 = {\n let dataset = distances_iteration_2.slice(0);\n for(let i=1; i computeIndicators_2(Delta, g, pairs_of_nodes_sampled, connected_pairs));","pinned":false,"hidden":false,"mode":"ojs"},{"id":467,"value":"{\n const baseline = vl.markLine({interpolate: 'monotone', stroke: 'grey'})\n .data(indicators_over_Delta)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('C'),\n )\n \n const sampled = vl.markLine({stroke: 'black'})\n .data(indicators_over_Delta_iteration_3)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('C'),\n )\n \n const sampledDots = vl.markPoint({stroke: 'black', fill:'black'})\n .data(indicators_over_Delta_iteration_3)\n .encode(\n vl.x().fieldQ('Delta').title('Δ'),\n vl.y().fieldQ('C').title('C(Δ)').axis({format: '%'}),\n )\n \n return vl.layer(baseline, sampled, sampledDots)\n .title('C(Δ) Connected-closeness for Δ')\n .width(640)\n .height(120)\n .render();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":470,"value":"md`As you can see in this example, the search focuses on the important zone of the curve.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":473,"value":"md`## Wrap up\nLet's assemble these two optimizations into a full algorithm.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":476,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":482,"value":"connected_closeness_data = computeConnectedCloseness(g);","pinned":false,"hidden":false,"mode":"ojs"},{"id":488,"value":"{\n return draw(\n g,\n {\n size: 900,\n node_size: 0.8,\n edge_thickness: 0.4\n },\n connected_closeness_data\n ).canvas\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":535,"value":"md`#### Note\nDuring the rewriting of the algorithm, I realized that ${tex`P_{edge}`} differed on directed and undirected graphs, and fixed it accordingly.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":35,"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":37,"value":"Graph = require('graphology@0.17.1/dist/graphology.umd.min.js')","pinned":false,"hidden":false,"mode":"ojs"},{"id":544,"value":"GraphologyLibrary = require('graphology-library@0.3.0/dist/graphology-library.min.js')","pinned":false,"hidden":false,"mode":"ojs"},{"id":42,"value":"gexf = GraphologyLibrary.gexf","pinned":false,"hidden":false,"mode":"ojs"},{"id":45,"value":"CElegans_GEXF = FileAttachment(\"C Elegans.gexf\").text()","pinned":false,"hidden":false,"mode":"ojs"},{"id":51,"value":"md`### Require d3`","pinned":false,"hidden":false,"mode":"ojs"},{"id":54,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":57,"value":"md`### Load Vega Lite for plotting`","pinned":false,"hidden":false,"mode":"ojs"},{"id":60,"value":"import {vl} from '@vega/vega-lite-api'","pinned":false,"hidden":false,"mode":"ojs"},{"id":218,"value":"md`### Load Observable inputs`","pinned":false,"hidden":false,"mode":"ojs"},{"id":220,"value":"import {View} from \"@mbostock/synchronized-views\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":216,"value":"viewof Sp = new View(10)","pinned":false,"hidden":false,"mode":"ojs"},{"id":492,"value":"md`### Routines`","pinned":false,"hidden":false,"mode":"ojs"},{"id":495,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}