2d:null 2e:["$","title",null,{"children":"Basic network generators | Mathieu Jacomy | Observable"}] 33:Taeb, function generateSquareLattice(min_order, grid_scale) { if (grid_scale === undefined) { grid_scale = 1 } var g = new Graph({multi: false, type:'undirected', allowSelfLoops: false}) g.addNode('r0c0', { row: 0, col: 0, type: 'intersection' }) var rank = 1 while (g.order < min_order || (rank-1)%grid_scale != 0) { var i for (i=0; i0 && (rank%grid_scale == 0 || (i-1)%grid_scale == 0)) { g.addEdge('r'+rank+'c'+i, 'r'+rank+'c'+(i-1)) g.addEdge('r'+i+'c'+rank, 'r'+(i-1)+'c'+rank) } } } if (rank%grid_scale == 0) { g.addNode('r'+rank+'c'+rank, { row: rank, col: rank, type: 'intersection' }) g.addEdge('r'+rank+'c'+rank, 'r'+rank+'c'+(rank-1)) g.addEdge('r'+rank+'c'+rank, 'r'+(rank-1)+'c'+rank) } rank++ } if (grid_scale==1) { g.nodes().forEach(function(nid){ if (g.degree(nid) == 4) { g.setNodeAttribute(nid, 'type', 'normal') } else if (g.degree(nid) == 3) { g.setNodeAttribute(nid, 'type', 'border') } else if (g.degree(nid) == 2) { g.setNodeAttribute(nid, 'type', 'corner') } }) g.setAttribute('creator', 'Generator of test networks') g.setAttribute('name', 'Square Lattice '+g.order) g.setAttribute('description', 'A grid of nodes. Except at the border, each node has four neighbors.') } else { g.nodes().forEach(function(nid){ if (g.getNodeAttribute(nid, 'type') == 'intersection') { if (g.degree(nid) == 3) { g.setNodeAttribute(nid, 'type', 'intersection-border') } else if (g.degree(nid) == 2) { g.setNodeAttribute(nid, 'type', 'intersection-corner') } } }) g.setAttribute('creator', 'Generator of test networks') g.setAttribute('name', 'Square Lattice Length='+grid_scale+' '+g.order) g.setAttribute('description', 'A grid of nodes connected by paths of length '+grid_scale) } return g } 34:T4a0, function generateTriangularLattice(min_order) { var g = new Graph({multi: false, type:'undirected', allowSelfLoops: false}) g.addNode('r0c0', { row: 0, col: 0 }) var rank = 1 while (g.order < min_order) { var i for (i=0; i<=rank; i++) { g.addNode('r'+rank+'c'+i, { row: rank, col: i }) if (i>0) { g.addEdge('r'+rank+'c'+i, 'r'+rank+'c'+(i-1)) g.addEdge('r'+rank+'c'+i, 'r'+(rank-1)+'c'+(i-1)) } if (i1)?('s'):(''))+' between each pair') return g } 36:T539, function generateBridgedLattices(min_order, lattice_count) { var g = new Graph({multi: false, type:'undirected', allowSelfLoops: false}) var l, i, j for (l=0 ; l0) { g.addEdge('l'+l+'r'+rank+'c'+i, 'l'+l+'r'+rank+'c'+(i-1)) g.addEdge('l'+l+'r'+rank+'c'+i, 'l'+l+'r'+(rank-1)+'c'+(i-1)) } if (i { // 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 settings.size = settings.size || 150; settings.node_size = settings.node_size || 5; settings.node_color = settings.node_color || 'rgba(0, 0, 0, 1)'; settings.edge_color = settings.edge_color || 'rgba(80, 80, 80, 0.8)'; settings.edge_thick = settings.edge_thick || 2; // Create canvas const canvas = document.createElement('canvas'); canvas.width = settings.size; canvas.height = settings.size; const ctx = canvas.getContext('2d'); // Clone network, so that we do not modify the original const g = _g.copy(); // Prepare network data addMissingVisualizationData(); rescaleGraphToGraphicSpace(); // Paint a white background ctx.fillStyle="white"; ctx.beginPath(); ctx.rect(0, 0, settings.size, settings.size); ctx.fill(); ctx.closePath(); // Scale canvas ctx.scale(settings.size/1000, settings.size/1000); // Draw each edge ctx.lineCap="round"; ctx.lineJoin="round"; ctx.strokeStyle = settings.edge_color; ctx.fillStyle = 'rgba(0, 0, 0, 0)'; ctx.lineWidth = settings.edge_thick; g.edges().forEach(function(eid){ const ns = g.getNodeAttributes(g.source(eid)); const nt = g.getNodeAttributes(g.target(eid)); 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); // Functions 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); // 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}); } } // Return result return { canvas, ctx }; }39:[] 31:{"id":"eba8121f484faae4","slug":"basic-network-generators","title":"Basic network generators","thumbnail":"90d535961e53fcf5c56a731f9a37dbd052d39d5f2408a8312aa2908d2e087251","access_level":"public","create_time":"$D2020-03-12T09:20:09.962Z","update_time":"$D2020-05-11T18:09:52.872Z","view_time":null,"first_public_time":"$D2020-03-12T11:36:48.613Z","has_unpublished_edits":null,"fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"314a0a5985c09d6c","login":"jacomyma","name":"Mathieu Jacomy","avatar_url":"https://avatars-next.observableusercontent.com/4496a2bc190392af306e4fcc2cc12dec9fe2acc458657e9bb35aecbeb5322d71","tier":"starter_2024"},"version":305,"publish_version":305,"role":null,"authored":false,"authors":[{"type":"individual","id":"5877bce6260ce3ea","login":"jacomyma","name":"Mathieu Jacomy","avatar_url":"https://avatars-next.observableusercontent.com/4496a2bc190392af306e4fcc2cc12dec9fe2acc458657e9bb35aecbeb5322d71","tier":null}],"members":[{"type":"individual","id":"5877bce6260ce3ea","login":"jacomyma","name":"Mathieu Jacomy","avatar_url":"https://avatars-next.observableusercontent.com/4496a2bc190392af306e4fcc2cc12dec9fe2acc458657e9bb35aecbeb5322d71","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":null,"type":"notebook","body":{"title":"Basic network generators","cells":[{"id":0,"value":"md`# Basic network generators\nA collection of basic network generators from [this page](https://jacomyma.github.io/generator-test-networks/#!/home), where you can just visualize and download generated networks, it that is what you want.\n\nThe generators require [Graphology](https://graphology.github.io/):\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"Graph = require('graphology@0.17.1/dist/graphology.umd.min.js')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"md`\nThey all use the number of nodes as the setting (also called *order* of the graph), but sometimes the actual number of nodes in the generated graph is slightly different, depending on the generation routine.\n\n

\n## Clique\nAll nodes are connected together.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":" function generateClique(order) {\n var g = new Graph({multi: false, type:'undirected', allowSelfLoops: false})\n var i, j\n for (i=0; i\n## Stable\nThere are no links.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":55,"value":" function generateStable(order) {\n var g = new Graph({multi: false, type:'undirected', allowSelfLoops: false})\n var i, j\n for (i=0; i\n## Star\nOne central node and the other nodes are only connected to that one.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":58,"value":" function generateStar(order) {\n var g = new Graph({multi: false, type:'undirected', allowSelfLoops: false})\n g.addNode('n0', {\n type: 'center'\n })\n var i\n for (i=1; i\n## Chain\nEach node has two neighbors except at each end of the chain.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":60,"value":" function generateChain(order) {\n var g = new Graph({multi: false, type:'undirected', allowSelfLoops: false})\n var i\n for (i=0; i0 && i0) {\n g.addEdge('n'+i, 'n'+(i-1))\n }\n }\n g.setAttribute('creator', 'Generator of test networks')\n g.setAttribute('name', 'Chain '+order)\n g.setAttribute('description', 'Each node has two neighbors except at each end of the chain')\n return g\n }\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":119,"value":"previewNetwork(generateChain(50))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":100,"value":"md`

\n## Circle\nEach node has two neighbors, in a circular chain.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":62,"value":" function generateCircle(order) {\n var g = new Graph({multi: false, type:'undirected', allowSelfLoops: false})\n var i\n for (i=0; i\n## Square Lattice\nA grid of nodes.\n\nThe grid_scale setting defines the size of the grid cells, in node count.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":64,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":123,"value":"previewNetwork(generateSquareLattice(50, 1))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":175,"value":"md`**Example with grid_scale = 3:**`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":177,"value":"previewNetwork(generateSquareLattice(50, 3))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":103,"value":"md`

\n## Triangular Lattice\nA grid of triangles.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":66,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":125,"value":"previewNetwork(generateTriangularLattice(50))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":105,"value":"md`

\n## Bridged Cliques\nCliques (group of fully connected nodes) connected by edges.\n\nAdditional settings: cliques_count and bridges_count.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":68,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":208,"value":"md`**Example with cliques_count = 2 and bridges_count = 5:**`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":127,"value":"previewNetwork(generateBridgedCliques(50, 2, 5))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":214,"value":"md`**Example with cliques_count = 4 and bridges_count = 1:**`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":217,"value":"previewNetwork(generateBridgedCliques(50, 4, 1))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":107,"value":"md`

\n## Bridged Stars\nStars linked by bridges between their cores.\n\nAdditional setting: star_count.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":70,"value":" function generateBridgedStars(min_order, star_count) {\n var g = new Graph({multi: false, type:'undirected', allowSelfLoops: false})\n var nodes_per_star = Math.ceil( min_order / star_count )\n var s, i, j\n for (s=0 ; s\n## Bridged Lattices\nTriangular lattices linked by bridges at one of their corners.\n\nAdditional setting: lattice_count.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":72,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":131,"value":"previewNetwork(generateBridgedLattices(50, 2))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":111,"value":"md`

\n## Random\nNodes connected with the settable probability p.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":74,"value":" function generateRandom(order, p) {\n var b, c, i, j\n var g = new Graph({multi: false, type:'undirected', allowSelfLoops: false})\n for (i=0; i\n## Stochastic Block Model\nBlocks with random links with controled probability. See [SBM](https://en.wikipedia.org/wiki/Stochastic_block_model).\n\nAdditional settings:\n* block_count\n* p_in is the probability that two nodes of the same block are linked\n* p_out is the probability that two nodes of the *different* blocks are linked\n\nNote: we usually ensure that p_in + p_out = 1\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":76,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":135,"value":"previewNetwork(generateSBM(50, 3, 0.9, 0.1))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":292,"value":"md`

\n# How to import\n\nYou can import those generators in your notebooks, the syntax is straightforward.\n\n

import {generateSBM} from \"@jacomyma/basic-network-generators\"

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"md`

\n\n--- \n\n# Appendix\n\nThe routine used to draw the network previews.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"value":"previewNetwork = function(g){\n // Apply a random layout\n g.nodes().forEach(nid => {\n g.setNodeAttribute(nid, 'x', 1000*Math.random())\n g.setNodeAttribute(nid, 'y', 1000*Math.random())\n })\n \n // Apply Force Atlas 2\n let settings = {}\n settings.linLogMode = false;\n settings.outboundAttractionDistribution = false;\n settings.adjustSizes = false;\n settings.edgeWeightInfluence = 0;\n settings.scalingRatio = 10;\n settings.strongGravityMode = true;\n settings.gravity = 0.01;\n settings.slowDown = 2;\n settings.barnesHutOptimize = false;\n settings.barnesHutTheta = 0.5;\n fa2.assign(g, {iterations: 1000, settings: settings});\n \n // Render\n return drawNetwork(g).canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":24,"value":"md`The drawing routine requires a layout algorithm. We use Force Atlas 2.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":301,"value":"GraphologyLibrary = require('graphology-library@0.3.0/dist/graphology-library.min.js')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"value":"fa2 = GraphologyLibrary.layoutForceAtlas2","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W39","stdlib":"1","titling":"auto"}} 32:"$31:body"