2b:null 2c:["$","title",null,{"children":"Spectral Clustering | Chuncheng | Observable"}] 31:Tad4,{ // num; // Init the Simulation let nodes = 0, links = 0; if ("nodes" in cache) { nodes = cache["nodes"]; links = cache["links"]; } else { nodes = graph.vert.map((d) => Object.create(d)); links = graph.edge.map((d) => Object.create(d)); } cache["nodes"] = nodes; cache["links"] = links; // console.log(nodes, links); const simulation = d3 .forceSimulation(nodes) .force( "link", d3 .forceLink(links) .id((d) => { return d.id; }) .strength((d) => { let a = nodes[d.source.index].grp, b = nodes[d.target.index].grp; let c = 1; if (a != b) { c = 0.5; } else { c = 1; } return c * d.str * f; }) ) .force("charge", d3.forceManyBody()) .force("center", d3.forceCenter(width / 2, height / 2)); // Init the SVG const svg = d3.create("svg").attr("width", width).attr("height", height); const scaleX = d3.scaleLinear().domain([-0.1, 1.1]).range([0, width]); const scaleY = d3.scaleLinear().domain([-0.1, 1.1]).range([0, height]); const scaleC = d3.scaleLinear().domain([0, 10]).range([0, 1]); const scaleSize = d3 .scaleSymlog() .domain(d3.extent(graph.vert, (d) => d.deg)) .constant(10) .range([5, 10]); // Draw Links and Nodes const linksDisp = svg .append("g") .selectAll("line") .data(links) .enter() .append("line") .attr("x1", (d) => scaleX(graph.vert[d.source.index].x)) .attr("y1", (d) => scaleY(graph.vert[d.source.index].y)) .attr("x2", (d) => scaleX(graph.vert[d.target.index].x)) .attr("y2", (d) => scaleY(graph.vert[d.target.index].y)) .attr("stroke", "gray") .attr("stroke-width", 1); const nodesDisp = svg .append("g") .selectAll("circle") .data(nodes) .join("circle") .attr("cx", (d) => scaleX(d.x)) .attr("cy", (d) => scaleY(d.y)) .attr("r", (d) => scaleSize(d.deg)) .attr("fill", (d) => d3.schemeCategory10[d.grp % 10]) .attr("stroke", "white") .attr("stroke-width", 2) .on("mouseover", (event, d) => { console.log(d, event.target); d3.select(event.target).attr("stroke", "black").attr("stroke-width", 3); }) .on("mouseleave", (event, d) => { d3.select(event.target).attr("stroke", "white").attr("stroke-width", 2); }) .call(drag(simulation)); simulation.on("tick", () => { linksDisp .attr("x1", (d) => d.source.x) .attr("y1", (d) => d.source.y) .attr("x2", (d) => d.target.x) .attr("y2", (d) => d.target.y); nodesDisp.attr("cx", (d) => d.x).attr("cy", (d) => d.y); }); invalidation.then(() => simulation.stop()); return svg.node(); }32:T678,mkGraph = (num = 100) => { const rnd = d3.randomUniform(0, 1); const distances = {}; const strs = {}; const vert = []; const edge = []; const degree = []; const lapMat = []; for (let i = 0; i < num; i++) { distances[i] = {}; strs[i] = {}; degree.push(0); lapMat[i] = []; for (let j = 0; j < num; j++) { lapMat[i].push(0); } } for (let i = 0; i < num; i++) { for (let j = i + 1; j < num; j++) { // let r = rndLink(); let str = d3.randomUniform(1, 5)(); degree[i] += str; degree[j] += str; strs[i][j] = str; strs[j][i] = str; } vert.push(Object.assign({ x: rnd(), y: rnd(), id: i, grp: 0 })); } const ignores = []; let paths = dijkstrajs.single_source_shortest_paths(strs, 0); for (let i in paths) { let a = parseInt(i); let b = parseInt(paths[i]); edge.push(Object.assign({ source: a, target: b, str: strs[a][b] })); // edge.push(Object.assign({ source: b, target: a, str: strs[b][a] })); lapMat[a][b] = -strs[a][b]; lapMat[b][a] = -strs[b][a]; } // for (let i = 0; i < num; i++) { // for (let j = 0; j < num; j++) { // if (lapMat[i][j] == 0 && i != j) lapMat[i][j] = -11111; // } // } for (let i = 0; i < num; i++) { vert[i].deg = degree[i]; for (let j = 0; j < num; j++) { if (i != j) lapMat[i][i] -= lapMat[i][j]; } } const clusters = kmClusters(lapMat); for (let i in clusters) { for (let j in clusters[i]) { vert[clusters[i][j]].grp = i; } } return Object.assign({ vert: vert, distances: distances, edge: edge, lapMat: lapMat }); }33:[] 2f:{"id":"96572bbde5b392b2","slug":"spectral-clustering","title":"Spectral Clustering","thumbnail":"0181d4208fa2ca4b3b38b900d753122703d048231f3190bd695a456029a6e076","access_level":"public","create_time":"$D2021-09-23T12:49:39.026Z","update_time":"$D2021-09-27T13:07:43.024Z","view_time":null,"first_public_time":"$D2021-09-23T13:18:27.074Z","fork":{"id":"bd116742b1f91cf4","slug":"simple-d3","title":"Simple D3","owner":{"id":"f35c755083683fe5","login":"observablehq","name":"Observable"}},"stars":0,"starred":false,"owner":{"type":"team","id":"bcd65cef1cb4d2ed","login":"listenzcc","name":"Chuncheng","avatar_url":"https://avatars-next.observableusercontent.com/bb3c68e77a708a587ffc2d663bb83421f20d67991dbe6c1623c6e5d2fb73d15e","tier":"starter_2024"},"version":910,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"16328058352682a8","login":"listenzcc","name":"Chuncheng","avatar_url":"https://avatars-next.observableusercontent.com/bb3c68e77a708a587ffc2d663bb83421f20d67991dbe6c1623c6e5d2fb73d15e","tier":null}],"members":[{"type":"individual","id":"16328058352682a8","login":"listenzcc","name":"Chuncheng","avatar_url":"https://avatars-next.observableusercontent.com/bb3c68e77a708a587ffc2d663bb83421f20d67991dbe6c1623c6e5d2fb73d15e","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"title":"Spectral Clustering","cells":[{"id":0,"value":"# Spectral Clustering\n\nThe notebook **will** explain the reason of the **Spectral Clustering**.\nThe colors refer the clustering.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":489,"value":"viewof num = Inputs.range([20, 50], { label: \"num:\", value: 0, step: 1 })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":715,"value":"viewof k = Inputs.range([3, 10], { label: \"k:\", value: 0, step: 1 })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":870,"value":"viewof f = Inputs.range([0.1, 0.8], { label: \"f:\", value: 0 })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":495,"value":"$31","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":886,"value":"cache = () => {\n num;\n k;\n return Object.assign({});\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":777,"value":"lastKColumn = (mat, kk = k) => {\n for (let i = 0; i < mat.length; i++) {\n mat[i] = mat[i].slice(-kk);\n\n let n = norm2(mat[i]);\n for (let j = 0; j < kk; j++) {\n mat[i][j] /= n;\n }\n }\n return mat;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":780,"value":"norm2 = (vec) => {\n let s = 0;\n for (let i = 0; i < vec.length; i++) {\n s += vec[i] ** 2;\n }\n return s ** 0.5;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":690,"value":"kmClusters = (lapMat) => {\n let { u, q, v } = svd.SVD(lapMat);\n\n u = lastKColumn(u);\n\n let km = kmeans.clusterize(u, { k: k }, (err, res) => {\n if (err) console.error(err);\n });\n let { groups } = km;\n\n let clusters = [];\n for (let i in groups) {\n clusters.push(groups[i].clusterInd);\n }\n return clusters;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":452,"value":"graph = mkGraph(num)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":446,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":430,"value":"rndLink = () => {\n const distance = d3.randomUniform(1, 10)();\n const width = 1 / distance;\n return Object.assign({ width: width, distance: distance });\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":275,"value":"drag = (simulation) => {\n function dragstarted(event) {\n if (!event.active) simulation.alphaTarget(0.3).restart();\n event.subject.fx = event.subject.x;\n event.subject.fy = event.subject.y;\n }\n\n function dragged(event) {\n event.subject.fx = event.x;\n event.subject.fy = event.y;\n }\n\n function dragended(event) {\n if (!event.active) simulation.alphaTarget(0);\n event.subject.fx = null;\n event.subject.fy = null;\n }\n\n return d3\n .drag()\n .on(\"start\", dragstarted)\n .on(\"drag\", dragged)\n .on(\"end\", dragended);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"height = width * 0.8","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":434,"value":"dijkstrajs = require(\"https://bundle.run/dijkstrajs@1.0.2\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":149,"value":"shuffle = require(\"https://bundle.run/shuffle-array@1.0.1\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":90,"value":"kmeans = require(\"https://bundle.run/node-kmeans@1.1.9\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":88,"value":"svd = require(\"https://bundle.run/svd-js@1.1.1\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":83,"value":"d3 = require(\"d3\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W33","stdlib":"1","titling":"auto"}} 30:"$2f:body"