2e:null 2f:["$","title",null,{"children":"Small worlds | Benjamin F. Maier | Observable"}] 34:T1001, { var mu_initial = -3; var B = 6; var L = 3; var k = 6; var mu = mu_initial; var N = Math.pow(B,L); var links = get_mhrn_edge_list(B,L,k,Math.pow(B,mu)); var width = 350; var height = width; var ctx_mhrn = DOM.context2d(width,height); var ctx_klein = DOM.context2d(width,height); var ctx_small = DOM.context2d(width,height); var col_mhrn = scaleChromatic.interpolateGreens(0.6); var col_klein = scaleChromatic.interpolatePurples(0.6); var col_small = scaleChromatic.interpolateReds(0.6); var nw_mhrn = new bostock_network_view(ctx_mhrn, width,height,N,get_mhrn_edge_list(B,L,k,Math.pow(B,mu)), scaleChromatic.interpolateGreens, ); var nw_klein = new bostock_network_view(ctx_klein, width,height,N,get_classic_small_world_edge_list(mu,k,N,true), scaleChromatic.interpolatePurples, ); var nw_small = new bostock_network_view(ctx_small, width,height,N,get_classic_small_world_edge_list(mu,k,N,false), scaleChromatic.interpolateReds, ); var ctx_plot = DOM.context2d(width,height); var pl = new simplePlot(ctx_plot,width,height,30,16); pl.xlabel('log(node distance)'); pl.ylabel('log(connection probability)'); update_plot(); function count_shortrange_links (l) { let cnt = 0; l.forEach(function(d) { if (d.is_shortrange_link) cnt++; }); return cnt; } function update_networks() { let mhrn = get_mhrn_edge_list(B,L,k,Math.pow(B,mu)); let klein = get_classic_small_world_edge_list(mu,k,N,true); let small = get_classic_small_world_edge_list(mu,k,N,false); let cnt_mhrn = count_shortrange_links(mhrn); let cnt_klein = count_shortrange_links(klein); let cnt_small = count_shortrange_links(small); console.log("mhrn SR/LR:", cnt_mhrn, mhrn.length - cnt_mhrn); console.log("klein SR/LR:", cnt_klein, klein.length - cnt_klein); console.log("small SR/LR:", cnt_small, small.length - cnt_small); nw_mhrn.update_links(mhrn); nw_klein.update_links(klein); nw_small.update_links(small); } function update_plot() { let x = d3.range(1,(N-1)/2).map(_ => Math.log(_)); //let x = d3.range(1,(N-1)/2); let p_mhrn = get_mhrn_distribution(B,L,k,Math.pow(B,mu)); let p_klein = get_kleinberg_distribution(mu,k,N).slice(0,(N-1)/2); let p_small = get_small_world_distribution(mu,k,N).slice(0,(N-1)/2); pl.xlimlabels(['1','N / 2']); pl.ylimlabels(['min','1']); pl.plot("modular hierarchical SW*",x,p_mhrn.map(_ => Math.log(_) ),[],col_mhrn,2,true); pl.plot("power-law SW",x,p_klein.map(_ => Math.log(_) ),[],col_klein,2,true); pl.plot("conventional SW",x,p_small.map(_ => Math.log(_) ),[],col_small,2,true); pl.legend(); //pl.plot("mhrn",x,p_mhrn,[],col_mhrn,2,true); //pl.plot("kleinberg",x,p_klein,[],col_klein,2,true); //pl.plot("small-world",x,p_small,[],col_small,2,true); //pl.draw(); } function update_mu(newmu) { mu = newmu; update_plot(); } function update_k(newk) { k = newk; update_plot(); } var mu_slider = get_slider(-3,1,0.01,mu_initial,"non-locality parameter", "μ", update_networks, update_mu), k_slider = get_slider(4,7,0.01,k,"mean degree", "k", update_networks, update_k); return get_as_div([ ctx_plot.canvas, mu_slider, k_slider, get_as_table_row([ add_title(ctx_mhrn.canvas,'modular hierarchical small-world'), add_title(ctx_klein.canvas,'power-law small-world'), add_title(ctx_small.canvas,'conventional small-world'), ]), //document.createElement('br'), ]); }35:T536,function add_random_subgraph (n, p, G, edge_list, start_node) { if (p>=1.0) { for (var v=start_node; v0.0) { var v = 1; var w = -1; var log1mP = Math.log(1-p); while (v=v) && (v 0) { result = result + in_degree / links - Math.pow((degree / (2.0 * links)), 2); } }); return result; } function __neighcom(node, graph, status) { // compute the communities in the neighb. of the node, with the graph given by // node_to_com var weights = {}; var neighboorhood = get_neighbours_of_node(graph, node);//make iterable; neighboorhood.forEach(function (neighbour, i) { if (neighbour !== node) { var weight = graph._assoc_mat[node][neighbour] || 1; var neighbourcom = status.nodes_to_com[neighbour]; weights[neighbourcom] = (weights[neighbourcom] || 0) + weight; } }); return weights; } function __insert(node, com, weight, status) { //insert node into com and modify status status.nodes_to_com[node] = +com; status.degrees[com] = (status.degrees[com] || 0) + (status.gdegrees[node] || 0); status.internals[com] = (status.internals[com] || 0) + weight + (status.loops[node] || 0); } function __remove(node, com, weight, status) { //remove node from com and modify status status.degrees[com] = ((status.degrees[com] || 0) - (status.gdegrees[node] || 0)); status.internals[com] = ((status.internals[com] || 0) - weight - (status.loops[node] || 0)); status.nodes_to_com[node] = -1; } function __renumber(dict) { var count = 0; var ret = clone(dict); //deep copy :) var new_values = {}; var dict_keys = Object.keys(dict); dict_keys.forEach(function (key) { var value = dict[key]; var new_value = typeof new_values[value] === 'undefined' ? -1 : new_values[value]; if (new_value === -1) { new_values[value] = count; new_value = count; count = count + 1; } ret[key] = new_value; }); return ret; } function __one_level(graph, status) { //Compute one level of the Communities Dendogram. var modif = true; var nb_pass_done = 0; var cur_mod = __modularity(status); var new_mod = cur_mod; while (modif && nb_pass_done !== __PASS_MAX) { cur_mod = new_mod; modif = false; nb_pass_done += 1 graph.nodes.forEach(function (node, i) { var com_node = status.nodes_to_com[node]; var degc_totw = (status.gdegrees[node] || 0) / (status.total_weight * 2.0); var neigh_communities = __neighcom(node, graph, status); __remove(node, com_node, (neigh_communities[com_node] || 0.0), status); var best_com = com_node; var best_increase = 0; var neigh_communities_entries = Object.keys(neigh_communities);//make iterable; neigh_communities_entries.forEach(function (com, i) { var incr = neigh_communities[com] - (status.degrees[com] || 0.0) * degc_totw; if (incr > best_increase) { best_increase = incr; best_com = com; } }); __insert(node, best_com, neigh_communities[best_com] || 0, status); if (best_com !== com_node) { modif = true; } }); new_mod = __modularity(status); if (new_mod - cur_mod < __MIN) { break; } } } function induced_graph(partition, graph) { var ret = {nodes: [], edges: [], _assoc_mat: {}}; var w_prec, weight; //add nodes from partition values var partition_values = obj_values(partition); ret.nodes = ret.nodes.concat(make_set(partition_values)); //make set graph.edges.forEach(function (edge, i) { weight = edge.weight || 1; var com1 = partition[edge.source]; var com2 = partition[edge.target]; w_prec = (get_edge_weight(ret, com1, com2) || 0); var new_weight = (w_prec + weight); add_edge_to_graph(ret, {'source': com1, 'target': com2, 'weight': new_weight}); }); return ret; } function partition_at_level(dendogram, level) { var partition = clone(dendogram[0]); for (var i = 1; i < level + 1; i++) { Object.keys(partition).forEach(function (key, j) { var node = key; var com = partition[key]; partition[node] = dendogram[i][com]; }); } return partition; } function generate_dendogram(graph, part_init) { if (graph.edges.length === 0) { var part = {}; graph.nodes.forEach(function (node, i) { part[node] = node; }); return part; } var status = {}; init_status(original_graph, status, part_init); var mod = __modularity(status); var status_list = []; __one_level(original_graph, status); var new_mod = __modularity(status); var partition = __renumber(status.nodes_to_com); status_list.push(partition); mod = new_mod; var current_graph = induced_graph(partition, original_graph); init_status(current_graph, status); while (true) { __one_level(current_graph, status); new_mod = __modularity(status); if (new_mod - mod < __MIN) { break; } partition = __renumber(status.nodes_to_com); status_list.push(partition); mod = new_mod; current_graph = induced_graph(partition, current_graph); init_status(current_graph, status); } return status_list; } var core = function () { var status = {}; var dendogram = generate_dendogram(original_graph, partition_init); return partition_at_level(dendogram, dendogram.length - 1); }; core.nodes = function (nds) { if (arguments.length > 0) { original_graph_nodes = nds; } return core; }; core.edges = function (edgs) { if (typeof original_graph_nodes === 'undefined') throw 'Please provide the graph nodes first!'; if (arguments.length > 0) { original_graph_edges = edgs; var assoc_mat = make_assoc_mat(edgs); original_graph = { 'nodes': original_graph_nodes, 'edges': original_graph_edges, '_assoc_mat': assoc_mat }; } return core; }; core.partition_init = function (prttn) { if (arguments.length > 0) { partition_init = prttn; } return core; }; return core; } 39:T1284,class bostock_network_view { constructor(context, width, height, N, initial_links, colorsequence = scaleChromatic.interpolateGreens, node_charge = -10, link_distance = 10, start_as_circle = true) { this.nodes = []; if (start_as_circle) { let r = width/2; for(var n = 0; n < N; n++) { let phi = n / N * Math.PI * 2; let x = r * Math.cos(phi); //+ width/2; let y = r * Math.sin(phi); //+ height/2; this.nodes.push({"id": n, "x": x, "y": y}); } } this.h = height; this.w = width; this.links = []; this.context = context; this.node_charge = node_charge; this.link_distance = link_distance; this.color = d3.scaleSequential(colorsequence); this.communities; this.update_links(initial_links); var self = this; this.simulation = d3.forceSimulation(this.nodes) .force("charge", d3.forceManyBody().strength(node_charge)) .force("link", d3.forceLink(this.links).distance(link_distance)) .force("x", d3.forceX()) .force("y", d3.forceY()) .alphaTarget(0.3) .on("tick", function () { context.clearRect(0, 0, width, height); context.save(); context.translate(width / 2, height / 2); context.beginPath(); self.links.forEach(function(d){ context.moveTo(d.source.x, d.source.y); context.lineTo(d.target.x, d.target.y); }); context.strokeStyle = "#888"; context.stroke(); let comm_ids = Object.keys(self.communities); comm_ids.forEach(function(c){ self.communities[c].forEach( function (n) { context.beginPath(); context.fillStyle = self.color(c); let d = self.nodes[n]; context.moveTo(d.x + 3, d.y); context.arc(d.x, d.y, 3, 0, 2 * Math.PI); context.fill(); context.strokeStyle = "#888"; context.stroke(); }); }); context.restore(); }); d3.select(context.canvas) .call(d3.drag() .container(context.canvas) .subject(function () {return self.simulation.find(d3.event.x - width / 2, d3.event.y - height / 2, 6 );}) .on("start", function (){ if (!d3.event.active) self.simulation.alphaTarget(0.3).restart(); d3.event.subject.fx = d3.event.subject.x; d3.event.subject.fy = d3.event.subject.y; }) .on("drag", function(){ d3.event.subject.fx = d3.event.x; d3.event.subject.fy = d3.event.y; }) .on("end", function(){ if (!d3.event.active) self.simulation.alphaTarget(0.3); d3.event.subject.fx = null; d3.event.subject.fy = null; })); } update_links(l) { if (typeof this.simulation != "undefined") this.simulation.stop(); this.links.length = 0; //console.log(this.links); //for(var i = 0; i n.id)) .edges(edges); var community_assignment_result = community(); var node_ids = Object.keys(community_assignment_result); var max_community_number = 0; this.communities = {}; node_ids.forEach(function(d){ max_community_number = max_community_number < community_assignment_result[d] ? community_assignment_result[d] : max_community_number; let this_comm = community_assignment_result[d]; if (!self.communities.hasOwnProperty(this_comm)) self.communities[this_comm] = []; self.communities[this_comm].push(d); }); this.color = this.color.domain([0, max_community_number]); /* for(var i = 0; i0; neigh--){ var p_ = Math.pow(neigh,mu_-1.0); sum_p += p_; p.push(p_); } //norm distribution for(var neigh=0; neigh=1) && (neigh<=N_/2)) { excess_probability += p[neigh] - 1; p[neigh] = 1; p[N_-2-neigh] = 1; neigh += 1; } while ((excess_probability>0) && (neigh<=N_/2)) { var dP = 1 - p[neigh]; if (excess_probability>=dP) { p[neigh] = 1; p[N_-2-neigh] = 1; excess_probability -= dP; } else { p[neigh] += excess_probability; p[N_-2-neigh] += excess_probability; excess_probability = 0; } neigh += 1; } } return p; } 3c:T5e7,function get_onearmed_kleinberg_distribution(mu_,k_,N_,redistribute_excess_probability = true) { //fill distance probability array var p = []; var sum_p = 0.; //get right arm of distribution for(var neigh=1; neigh<=N_/2; neigh++){ var p_ = Math.pow(neigh,mu_-1.0); sum_p += p_; p.push(p_); } //get left arm of distribution var begin; if (N_ % 2 == 0){ begin = Math.floor(N_/2)-1; } else { begin = Math.floor(N_/2); } for(var neigh=begin; neigh>0; neigh--){ var p_ = Math.pow(neigh,mu_-1.0); sum_p += p_; p.push(p_); } //norm distribution for(var neigh=0; neigh=1) && (neigh<=N_/2)) { excess_probability += p[neigh] - 1; p[neigh] = 1; p[N_-2-neigh] = 1; neigh += 1; } while ((excess_probability>0) && (neigh<=N_/2)) { var dP = 1 - p[neigh]; if (excess_probability>=dP) { p[neigh] = 1; p[N_-2-neigh] = 1; excess_probability -= dP; } else { p[neigh] += excess_probability; p[N_-2-neigh] += excess_probability; excess_probability = 0; } neigh += 1; } } return p; }3d:[] 32:{"id":"477b65dfabf90f91","slug":"small-worlds","title":"Small worlds","thumbnail":"3068b37019763971202141a6fc3af1714c772b3da652c0affed6d925e8a63f15","access_level":"public","create_time":"$D2019-12-03T14:24:04.553Z","update_time":"$D2019-12-03T14:24:04.553Z","view_time":null,"first_public_time":"$D2020-09-21T14:00:28.220Z","has_unpublished_edits":null,"fork":true,"stars":2,"starred":false,"owner":{"type":"team","id":"763b0efc07f51c57","login":"benmaier","name":"Benjamin F. Maier","avatar_url":"https://avatars-next.observableusercontent.com/cac48e4cb4e4439e443d95f66101075002fe9bb7642fd54a20b09750ec2dc514","tier":"starter_2024"},"version":647,"publish_version":647,"role":null,"authored":false,"authors":[{"type":"individual","id":"98446b0507ca17fd","login":"benmaier","name":"Benjamin F. Maier","avatar_url":"https://avatars-next.observableusercontent.com/cac48e4cb4e4439e443d95f66101075002fe9bb7642fd54a20b09750ec2dc514","tier":null}],"members":[{"type":"individual","id":"98446b0507ca17fd","login":"benmaier","name":"Benjamin F. Maier","avatar_url":"https://avatars-next.observableusercontent.com/cac48e4cb4e4439e443d95f66101075002fe9bb7642fd54a20b09750ec2dc514","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"title":"Small worlds","cells":[{"id":0,"value":"md`# Small worlds`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":60,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":92,"value":"function get_slider(min,max,step,value,label,symbol,changecallback,inputcallback=null,bgcolor = '#f7f7f9') {\n var this_div = document.createElement(\"div\");\n this_div.setAttribute(\"style\", \"padding: 10px; margin-bottom: 5px; margin-top: 5px; background-color: \"+bgcolor+\";\");\n var slider = document.createElement(\"input\");\n slider.setAttribute(\"min\",min);\n slider.setAttribute(\"type\",\"range\");\n slider.setAttribute(\"max\",max);\n slider.setAttribute(\"step\",step);\n slider.setAttribute(\"value\",value);\n \n var this_label = document.createElement(\"span\");\n this_label.innerHTML = ' ' + label + ' ' + symbol + ' = ' + slider.value ;\n\n slider.onchange = function(){\n changecallback(+slider.value);\n };\n \n slider.oninput = function(){\n this_label.innerHTML = ' ' + label + ' ' + symbol + ' = ' + slider.value ;\n if (inputcallback !== null)\n inputcallback(+slider.value);\n };\n \n this_div.append(slider);\n this_div.append(this_label);\n return this_div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":143,"value":"function get_as_div(list_of_html_elements) {\n var this_div = document.createElement(\"div\")\n\n list_of_html_elements.forEach( function (el) {\n this_div.appendChild(el);\n });\n return this_div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":431,"value":"function get_as_table_row(list_of_html_elements) {\n var row = document.createElement(\"div\");\n row.setAttribute(\"style\", \"display: table; width: 100%; table-layout: fixed; border-spacing: 10px;\");\n list_of_html_elements.forEach( function (el) {\n el.style.display = 'table-cell';\n row.appendChild(el);\n });\n return row;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":400,"value":"function add_title(element,title)\n{\n var this_div = document.createElement(\"div\")\n\n let d = document.createElement(\"div\");\n d.setAttribute(\"style\",\"text-align: center; width: auto;\");\n let p = document.createElement(\"p\");\n p.innerHTML = title;\n d.appendChild(p);\n d.append(element);\n this_div.appendChild(d);\n //let br = document.createElement(\"br\");\n //d.appendChild(br);\n\n return this_div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":289,"value":"function get_as_float(element,float='left') {\n var this_div = document.createElement(\"div\");\n this_div.setAttribute(\"style\",\"float: \"+float+\"; margin-right: 10px;\");\n this_div.append(element);\n return this_div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"function getRandomInt(min, max) {\n min = Math.ceil(min);\n max = Math.floor(max);\n return Math.floor(Math.random() * (max - min +1)) + min; \n}\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":494,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"function binom(n,p) {\n var I = 0;\n var threshold = -Math.log(1.0-p);\n var S = 0;\n\n while (true) {\n var Y = -Math.log(Math.random());\n S += Y / (n-(I+1)+1.0);\n if ( S > threshold) {\n return I;\n } else {\n I = I + 1;\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":497,"value":"function get_mhrn_distribution (B,L,k,xi) {\n\n var n = Math.pow(B,L);\n\n var p1;\n if ( xi == 1.0 ) {\n p1 = k / (B-1.0) / L;\n } else {\n p1 = k / (B-1.0) * (1.0-xi) / (1.0-Math.pow(xi,L));\n }\n\n var p = [];\n for (var node = 0; node < Math.floor((B-1)/2); ++node)\n p.push(p1);\n \n for (var l=2; l<=L; l++)\n for (var node = 0; node < Math.floor((Math.pow(B,l) - Math.pow(B,l-1))/2); ++node)\n p.push( p1*Math.pow(xi/B,l-1) );\n \n return p;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"d3 = require('d3@v4.13')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":452,"value":"scaleChromatic = require('d3-scale-chromatic')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":37,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":25,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":235,"value":"$3a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":279,"value":"function get_small_world_distribution(mu,k_,N_) {\n k_ = Math.floor(k_/2);\n let new_k = 2*k_;\n N_ = Math.floor(N_);\n\n let pr;\n pr = new_k / (N_-1-new_k) * Math.pow(new_k / (N_-1-new_k),-mu)\n\n //var pr = (new_k-2) / (N_-1-new_k) * ( (Math.pow((N_-1)/2,mu) - 1) / (Math.pow(new_k/2,mu) - 1) - 1 );\n let p_near = new_k / (new_k - pr*new_k + pr * (N_ - 1));\n let p_far = p_near * pr ;\n \n console.log(p_near*new_k,p_far*(N_-1-new_k));\n //fill distance probability array\n var p = [];\n for(var i=0; i