2c:null 2d:["$","title",null,{"children":"Graphs And Their Application | Chris L Buie | Observable"}] 32:T5f9,md` # This Isn't Your Excel's Graph. So, what do we mean by Graph anyway (at least in this context)?

Source: Graph Alogrithms Graphs are a specialized sub-discipline of discrete mathematics that provides a novel set of algorithms for exploring highly conected data sets. We can use these intuitive mathematical structures to study pairwise relationships between objects and entities. Graphs can be found dating back to 1736 when Leonhard Euler solved the “Seven Bridges of Königsberg” problem using a Graph. Pairwise relationships can be thought of as key/value pairs like Operator (key) = Exon Mobil (value).

Source: Graph Alogrithms Working with data in the form of Graphs, helps us gain actionable insights and allows us to make better data driven decisions. Here is an example using airline data.

Source: Cambridge Itelligence

`33:T605,md` # Graphs In the Wild: Chances are your life is already significantly impacted by graphs on a daily basis. Graphs are being used all around us. Here are just a handfull of examples to help build a little more intuition. * **Oil and Gas** - high-grade premium leasing opportunities by identifying transaction classes and networks. * **Marketing Analytics** – find the most influential people in a Social Network. Marketers can estimate the biggest bang for their buck by routing their message through the most influential people. * **Banking Transactions** – find unusual patterns helping to mitigate Fraudulent transactions. * **Counter Intelligence** - find transactions linked to terrorist activity by detected and analyzing the flow of money across interconnected networks. * **Supply Chain** – identify optimum routes for delivery routing and identify optimum locations for distribution centers. * **Epidemiology** – discovery pathogen delivery networks to isolate pandemics and the spread of dangerous pathogens. Think about the CDC and predicting the spread of COVID-19. * **Telecom** – identify the quantity and location of cellular towers to ensure maximum coverage. You can bet they are using these techniques to plan for 5G. * **Medical Research** - identify links and relationships in environmental and genetic variables that contribute to pervasive diseases. and on and on... Essentially, any kind of problem where casualty can be associated with several independent variables that have connectivity. `34:T7b3,md` # One last point... The network analysis shown in the following picture was created by Francesco D’Orazio to help predict the virality of content and inform distribution strategies. D’Orazio found a correlation between the concentration of a community’s distribution and the speed of diffusion of information.

www.pulsarplatform.com This is a fascinating example you can read more about here, but what you should note is this is significantly different than what an average distribution model would predict, where most nodes would have a similar number of connections. In practice many networks have been shown to have a power-law distribution with a few nodes being highly connected and most nodes being modestly connected. From this simple example, you can easily see the true power Graphs offer over other traditional approaches. You can quickly find the 5 nodes that have the true influence in the network and focus your efforts on them. Or you could waste countless resources working modestly connected nodes and never truly penetrate the network. However, Graphs are not perfect, Graphs tend to work poorly on random processes where average distributions hold true. And, like most things graphs, perform poorly on sparse data sets. In conclusion, we were are able to cover quite a bit of ground at a very high level. I hope this helps you think about the way we are analyzing some of our more complex data. In the future we will take an interactive deep dive into the various Graphs and algorithms we can you use to derive more insights. `35:T15c4,class StateMachine { constructor(rootElementId) { this.rootElementId = rootElementId; this.links = []; this.width = 600; this.height = 500; } build() { var linkDistance = 100; var nodes = {}; var links = this.links; var width = this.width, height = this.height; var getRandomVal = x => (Math.floor(Math.random() * x + 1)) - x / 2; var bornDistance = 3 * linkDistance; links.forEach(function (link) { link.source = nodes[link.source] || (nodes[link.source] = { name: link.source, x: width / 2 + getRandomVal(bornDistance), y: height / 2 + getRandomVal(bornDistance) }); link.target = nodes[link.target] || (nodes[link.target] = { name: link.target, x: width / 2 + getRandomVal(bornDistance), y: height / 2 + getRandomVal(bornDistance) }); link.value = +link.value; }); var force = d3.layout.force() .nodes(d3.values(nodes)) .links(links) .size([width, height]) .linkDistance(100) .charge(-2000) .on("tick", tick) .start(); var svg = d3.select("#" + this.rootElementId).append("svg") .attr("width", width) .attr("height", height); // build the arrow. svg.append("svg:defs").selectAll("marker") .data(["end"]) // Different link/path types can be defined here .enter().append("svg:marker") // This section adds in the arrows .attr("id", d => "end_" + d.name) .attr("viewBox", "0 -5 10 10") .attr("refX", 20) .attr("refY", -1.5) .attr("markerWidth", 5) .attr("markerHeight", 5) .attr("orient", "auto") .append("svg:path") .attr("d", "M0,-5L10,0L0,5"); // add the links and the arrows var path = svg.append("svg:g").selectAll("path") .data(force.links()) .enter().append("svg:path") .style("stroke", "rgba(0, 0, 0, 0.3)") .style("stroke-width", 2) .style("fill", "none") .attr("class", "link") .attr("marker-end", d => "url(#end_" + d.name + ")"); // define the nodes var node = svg.selectAll(".node") .data(force.nodes()) .enter().append("g") .attr("class", "node") .call(force.drag); // add the nodes node.append("circle") .attr("r", 8) .style("stroke", "#111111") .style("stroke-width", 2) .style("fill", "#9dc0f9") .attr("id", d => "c-" + d.name); // add the text node.append("text") .style("font-family", "Saira") .style("font-size", 20) .attr("x", 20) .attr("dy", ".35em") .text(d => d.name); // add the curvy lines function tick() { path.attr("d", function (d) { var dx = d.target.x - d.source.x, dy = d.target.y - d.source.y, dr = Math.sqrt(dx * dx + dy * dy); return "M" + d.source.x + "," + d.source.y + "A" + dr + "," + dr + " 0 0,1 " + d.target.x + "," + d.target.y; }); node .attr("transform", function (d) { return "translate(" + d.x + "," + d.y + ")"; }); } this.svg = svg; return this; } update(active) { console.log(this); var svg = this.svg svg.selectAll("circle") .each(function (d) { d.pulse = active.includes(d.name); pulsate(d3.select(this)); }); function pulsate(selection) { recursive_transitions(); function recursive_transitions() { if (selection.data()[0].pulse) { selection.transition() .duration(400) .style("fill", "#9dc0f9") .attr("stroke-width", 2) .attr("r", 8) .ease('sin-in') .transition() .duration(800) .style("fill", "#6dff8a") .attr('stroke-width', 3) .attr("r", 20) .ease('bounce-in') .each("end", recursive_transitions); } else { // transition back to normal selection.transition() .duration(800) .style("fill", "#9dc0f9") .attr("r", 8) .attr("stroke-width", 2) .attr("stroke-dasharray", "1, 0"); } } } return this; } withEdges(edges) { this.links = edges.map(edge => ({ source: edge[0], target: edge[1], value: 1.0 })); return this; } withActive(active) { this.active = active; return this; } withWindowSize(w, h) { this.width = w; this.height = h; return this; } destroy() { d3.select("#" + this.rootElementId).selectAll("*").remove(); return this; } } 36:[] 30:{"id":"2b85c668f403e5a0","slug":"graphs-and-their-application","title":"Graphs And Their Application","thumbnail":"85cb03e08ee7fb5ed5944b2b22dbbba36eec166394c1e75b47c4cf7c67a2a8eb","access_level":"public","create_time":"$D2020-02-04T18:49:21.350Z","update_time":"$D2021-10-01T16:20:47.766Z","view_time":null,"first_public_time":"$D2020-02-05T01:22:38.803Z","has_unpublished_edits":null,"fork":false,"stars":9,"starred":false,"owner":{"type":"team","id":"5ff335675a444f4e","login":"cbuie","name":"Chris L Buie","avatar_url":"https://avatars-next.observableusercontent.com/b68b101792a9b0a1bdd51d7424d01cd84dea6bd34ad829460c93e27aad96ebb2","tier":"starter_2024","bio":"Data Scientist at Warwick Investment Group. Passionate about science, predictive modeling, and data visualizations."},"version":344,"publish_version":344,"role":null,"authored":false,"authors":[{"type":"individual","id":"fb193f2e50e06492","login":"cbuie","name":"Chris L Buie","avatar_url":"https://avatars-next.observableusercontent.com/b68b101792a9b0a1bdd51d7424d01cd84dea6bd34ad829460c93e27aad96ebb2","tier":null,"bio":"Data Scientist at Warwick Investment Group. Passionate about science, predictive modeling, and data visualizations."}],"members":[{"type":"individual","id":"fb193f2e50e06492","login":"cbuie","name":"Chris L Buie","avatar_url":"https://avatars-next.observableusercontent.com/b68b101792a9b0a1bdd51d7424d01cd84dea6bd34ad829460c93e27aad96ebb2","tier":null,"role":"editor"}],"comments":[{"id":"720b8f46a5381fe0","reply_to_id":null,"content":"Hey Chris, nice work. Well laid out and clearly stated. \n\nNoticed a small typo in the last sentence of this cell. Think you meant causality rather than casualty. 👍","create_time":"$D2021-03-03T01:55:17.554Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"04c32d8a18696e81","login":"noble","name":"Noble","avatar_url":"https://avatars-next.observableusercontent.com/3bd89c10ca274fc7598152a62a193858ce1f1d1662a9dac1b180aa16b997b758","tier":null}}],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":{"id":"68626564663b860c","slug":"graph-theory","title":"Graph Theory","owner":{"id":"5ff335675a444f4e","login":"cbuie","name":"Chris L Buie"}},"type":"notebook","body":{"titling":"auto","title":"Graphs And Their Application","cells":[{"id":318,"value":"md`\n# Graphs And Their Application\n\n> *If a picture is said to speak a thousand words, a Graph can explain a million pictures.*\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":268,"value":"md `\n

\n\nSource: Cambridge Intelligence\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":0,"value":"md`\n
\nIn the era of big data with ever-expanding volumes of disparate data sources. Businesses and data practitioners face a compounding difficulty of deriving insights from complex non-tabular data structures. Some of today’s most pressing and opportune data challenges center around deriving insights from relationships found in mountains of data. Old theorems paired with modern computing platforms provide powerful tools for connecting and analyzing this data. Unanalyzed data contains undiscovered, important insights and represents an opportunity lost. Here we will discuss one non-conventional approach we can use to tap into underutilized datasets. \n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":76,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":167,"value":"md `\n# That's great, but why do I care?\n\nIt is important because Graph algorithms are useful in making sense of connected data. We see relationships within real-world systems from molecular interactions to who we know on LinkedIn, from communication systems to power grids, and from retail experiences to real estate transactions. Understanding networks and the connections within them offers incredible potential for insight and innovation that would otherwise be unavailable.\n\nGraph algorithms are uniquely suited to understanding structures and revealing patterns in datasets that are highly connected. Nowhere is the connectivity and interactivity so apparent than in this era of big data. The amount of data that is being generated, aggregated and comingled is incomprehensible. This is an area where graph algorithms can help us make sense of otherwise wasted data. \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":179,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":289,"value":"md`\n### Graph\n
\n*Next, we will build a graph like the one below and learn how to interact with it.*
\n*Coming soon...*\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":283,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":221,"value":"md`\n

\n### Requirments\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":206,"value":"d3 = require(\"d3@3\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":208,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":212,"value":"(() => {\n var edges = [\n [\"A\", \"B\"],\n [\"B\", \"C\"],\n [\"C\", \"D\"],\n [\"D\", \"E\"],\n [\"E\", \"F\"],\n [\"D\", \"B\"],\n [\"F\", \"A\"]\n ];\n \n var stateMachine = new StateMachine(\"diagram\")\n .withWindowSize(1000, 400)\n .withEdges(edges)\n .build();\n\n function play() {\n stateMachine.update([]);\n\n setTimeout(() => stateMachine\n .update([\"C\", \"E\"]), 4000);\n\n setTimeout(() => stateMachine\n .update([\"F\", \"A\"]), 8000);\n\n setTimeout(() => stateMachine\n .update([\"B\"]), 12000);\n\n setTimeout(() => play(), 16000);\n }\n\n play();\n})();","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W36","stdlib":"1"}} 31:"$30:body"