|
<!DOCTYPE html> |
|
<meta charset="utf-8"> |
|
<title>An Interactive Introduction to Network Analysis and Representation</title> |
|
<style> |
|
|
|
html, body { |
|
height: 100%; |
|
width: 100%; |
|
color: #444; |
|
font: 1em/1 "Hoefler Text", "Georgia", Georgia, serif, sans-serif; |
|
padding: 10px; |
|
|
|
} |
|
|
|
ol { |
|
list-style-type: none; |
|
} |
|
|
|
h1 a:visited { |
|
text-decoration:none; |
|
color:#404040; |
|
font-weight:600; |
|
} |
|
|
|
h1 {font-weight:400;font-size:1.6em;line-height:0.9em;padding:0px 0 0;margin: 1em 0em .25em 0em;} |
|
h1 a{font-weight:100;letter-spacing:-0.05em;position:relative;} |
|
|
|
h2 {font-weight:50;font-size:1.2em;letter-spacing:-0.05em;position:relative; color:#888;margin: 0;} |
|
h2 a { |
|
text-decoration:none; |
|
color:#404040; |
|
font-weight:600; |
|
} |
|
|
|
h2 a:hover { |
|
color:#C71585; |
|
font-weight:600; |
|
} |
|
|
|
rect { |
|
fill: none; |
|
pointer-events: all; |
|
} |
|
|
|
.node { |
|
fill: #000; |
|
} |
|
|
|
.cursor { |
|
fill: none; |
|
stroke: brown; |
|
pointer-events: none; |
|
} |
|
|
|
.link { |
|
stroke: #999; |
|
} |
|
|
|
#viz { |
|
height: 100%; |
|
width: 50%; |
|
float: left; |
|
} |
|
|
|
#lesson { |
|
height: 100%; |
|
width: 45%; |
|
float: left; |
|
} |
|
|
|
#definitionbox { |
|
margin-top: 20px; |
|
margin-right: 100px; |
|
font-style: italic; |
|
font-size: 1.1em; |
|
color:#707070; |
|
height: 0; |
|
overflow: visible; |
|
} |
|
|
|
#citations { |
|
margin-top: 20px; |
|
} |
|
|
|
#codetext { |
|
font: 1em/1 "Courier New", Courier, monospace; |
|
} |
|
|
|
#footer { |
|
margin: 20px; |
|
height: 20px; |
|
width: 1000px; |
|
} |
|
|
|
|
|
</style> |
|
<script src="http://d3js.org/d3.v3.min.js"></script> |
|
|
|
<body> |
|
<a href="https://gist.github.com/emeeks/4588962"><img style="position: absolute; top: 0; right: 0; border: 0;" src="https://s3.amazonaws.com/github/ribbons/forkme_right_darkblue_121621.png" alt="Fork me on GitHub"></a> |
|
<div id="viz"> |
|
<form> |
|
Gravity <input id="gravitySlider" type="range" onchange="updateForce(); changeGravity()" min ="0" max="1" step =".01" value=".1" /> |
|
<input type="text" id="gravityInput" value=".1" /> |
|
</form> |
|
<form> |
|
Attraction (Links) <input id="attractionSlider" type="range" onchange="updateForce(); highlightEdges()" min ="-100" max="100" step ="1" value="50"/> |
|
<input type="text" id="attractionInput" value="50" /><input type="checkbox" id="edgeCheckbox" onclick="updateForce(); highlightEdges()" /> Weight |
|
</form> |
|
<form> |
|
Charge (Nodes) <input id="repulsionSlider" type="range" onchange="updateForce(); highlightNodes()" min ="-200" max="0" step ="1" value="-60" /> |
|
<input type="text" id="repulsionInput" value="-60" /> |
|
<input type="checkbox" id="nodeCheckbox" onclick="updateForce(); highlightNodes()" /> Size |
|
</form> |
|
<form> |
|
Size by |
|
<input id="degreeCheck" type="radio" name="resizeGroup" checked="true" onclick="resize('nothing')"> Nothing |
|
<input id="degreeCheck" type="radio" name="resizeGroup" onclick="resize('degree')"> Degree |
|
<input id="labelSlider" style="width: 50px" type="range" onchange="labelChange();" min ="0" max="20" step =".1" value="0"/> Labels |
|
</form> |
|
<form><input type="checkbox" id="directedCheck" onclick="changeDirectedness()"> Directed</form> |
|
<form><input type="button" value="Delete some edges" disabled=true> <input type="button" value="Delete some nodes" onclick="deleteRandomNodes()"> |
|
<input type="button" id="addNodesButton" value="Add nodes" onclick="addNodes()"></form> |
|
<div id="definitionbox" height="1px"> |
|
</div> |
|
</div> |
|
<div id="lesson"> |
|
<div id="lessontitle"> |
|
<h1>Introduction to Network Analysis and Representation</h1> |
|
<h2><a href="https://dhs.stanford.edu">Elijah Meeks</a> and Maya Krishnan</h2> |
|
</div> |
|
<div> |
|
<ol> |
|
<li><input type="button" value="Introduction" onclick='updateText("introduction")'></li> |
|
<li>Models</li> |
|
<li><input type="button" value="Random" onclick='randomGraph(50,.025); updateText("randomgraph")'><input type="button" value="Dramatic" onclick='loadGraph("hamlet_nodes.csv","hamlet_edges.csv","person"); updateText("drama")'><input type="button" value="Transportation" onclick='loadGraph("rome_nodes.csv","rome_edges.csv","city"); updateText("transport")'></li> |
|
<li><input type="button" value="Correspondence" disabled=true><input type="button" value="Genealogy" onclick='loadGraph("darwin_nodes.csv","darwin_edges.csv","person"); updateText("darwin")'><input type="button" value="Administration" onclick='loadGraph("dgsd_nodes.csv","dgsd_edges.csv","city"); updateText("dgsd")'></li> |
|
<li>Layouts</li> |
|
<li><input type="button" value="Force-Directed" onclick='updateForce(); updateText("forcealgo")'><input type="button" value="Plot" onclick='plotLayout(); updateText("plotlayout")'><input type="button" value="Hierarchical" disabled=true></li> |
|
<li>Metrics</li> |
|
<li><input type="button" value="Centrality" onclick='calculateCentrality(); updateText("centrality")' /><input type="button" value="Clustering Coefficient" onclick='clusteringCoefficient(); updateText("clustering")' /></li> |
|
<li><input type="button" value="Community Detection" disabled=true></li> |
|
<li>Exploration</li> |
|
<li><input type="button" value="Pathfinding" onclick='selectPath(); updateText("pathfinding")'><input type="button" value="Ego Network" onclick='showEgoNetwork(); updateText("egonetwork")'><input type="button" value="Spatial Problem" onclick='spatialProblem(); updateText("spatialproblem")' ></li> |
|
</ol> |
|
</div> |
|
<div id="lessontext"> |
|
</div> |
|
<div id="citations"> |
|
</div> |
|
<div id="codetext"> |
|
</div> |
|
</div> |
|
<div id="footer"></div> |
|
</body> |
|
|
|
<script> |
|
|
|
currentSizing = "nothing"; |
|
currentEdge = "fixed"; |
|
pathSource = ""; |
|
|
|
var width = 500, |
|
height = 600; |
|
|
|
var fill = d3.scale.category20(); |
|
|
|
//Set the initial state |
|
randomGraph(50,.025); |
|
updateText("introduction"); |
|
|
|
|
|
function updateText(lessonType) { |
|
switch(lessonType) |
|
{ |
|
case "introduction": |
|
d3.select("#codetext").html("<h3>Code</h3><p><a href='https://gist.github.com/emeeks/4588962'>You can see the code on Github here</a></p><p>This section is used to display relevant code for the actions that you've clicked on. All implementations of network functionality on this site are built in D3 using JavaScript, so they're not particularly high performance. Plus, they were coded by a humanist, and you know how that goes.</p>"); |
|
d3.select("#citations").html("<h3>Citations</h3><ol><li>1. BRUGHMANS, T. 2012. Thinking through networks: a review of formal network methods in archaeology. Journal of Archaeological Method and Theory.</li></ol>"); |
|
d3.select("#lessontext").html("<h2>Introduction</h2><p>Networks and network analysis has grown more prominent in both humanities scholarship and public discourse. In this context, networks--also known as graphs or node-link diagrams--are \"a set of vertices (also called points or nodes) which represent the entities of research interest, and a set of lines (or ties) between these vertices which represent their relationships.\" [1]</p><p>This interactive application is designed to provide an overview of various network analysis principles used for analysis and representation. It also provides a few examples of untraditional networks used in digital humanities scholarship. Finally, along with the various methods described interactively here are links to related scholarship.</p><p>Each network type is listed in the Models section, and can be paired with an analysis or representation method by simply clicking on a network type to load a new network, and then clicking on an analysis or visualization method.</p><p>Networks are represented using traditional force-directed techniques or by plotting along the xy axis based on numerical attributes of the nodes (longitude and latitude in the case of nodes that represent geographic entities). For the force directed layout, you can adjust the various force principles to see how this affects the representation of the network you're working with.</p><p>This implementation will likely remain a work-in-progress for some time, and if you notice any flaws or discrepencies, or have a suggestion, please contact <a href='mailto:[email protected]'>Elijah Meeks</a>.</p>"); |
|
break; |
|
case "transport": |
|
d3.select("#codetext").html("<h3>Code</h3><p>Loading a Transportation Network uses the same code to load all preset networks, so maybe this should focus on the CSV being loaded</p>"); |
|
d3.select("#citations").html("<h3>Citations</h3><ol><li><a href='http://journalofdigitalhumanities.org/1-3/modeling-networks-and-scholarship-with-orbis-by-elijah-meeks-and-karl-grossner/'>Meeks, E. & Grossner, G. \"Modeling Networks and Scholarship with ORBIS\" Journal of Digital Humanities 1.3 Summer 2012.</a></li><li>...</li></ol>"); |
|
d3.select("#lessontext").html("<h2>Transportation Networks</h2><p>This is a piece of the transportation network of the Roman World from <a href='http://orbis.stanford.edu'>ORBIS</a>. A transportation network typically uses edges to describe an annotated connection between two sites, though sometimes nodes do not represent sites in the traditional sense but rather any place where a switch can be made from one route to another, such as an intersection, on-ramp, or crossroads.</p><p>If plotted, the nodes are laid out by their geographic location</p><p><a href='http://thenounproject.com/noun/city/#icon-No1566'>City icon by Thibault Geffroy, from The Noun Project</a></p>"); |
|
break; |
|
case "randomgraph": |
|
d3.select("#codetext").html("<h3>Code</h3><p>Some code that produces a random graph, with random links and random spatial characteristics.</p>"); |
|
d3.select("#citations").html("<h3>Citations</h3><ol><li>Albert, R., and Barabasi, A-L. (2002). Statistical mechanics of complex networks. Reviews of modern physics 74 (January): 47-97.</li><li>...</li></ol>"); |
|
d3.select("#lessontext").html("<h2>Random Graph</h2><p>Random graphs are used as control sets to compare variation with the studied network. Random isn't the best word for these networks, as they can be generated by very specific and complicated rules, so as better to model the phenomena being studied.</p><p>If plotted, each node will be placed according to random xy values generated when the network is first created.</p><p>This graph is created with 50 nodes and a 2.5% for each node to be connected to each node (in both directions, so a 5% chance total if treated as an undirected graph). You can create a new random graph with different settings:</p><form>Nodes: <input type=\"text\" name=\"nrgNodeValue\" value=\"50\" /> Link Chance <input type=\"text\" name=\"nrgLinksValue\" value=\".025\" /><input type=\"button\" value=\"New Graph\" onclick='randomGraph(this.form.nrgNodeValue.value,this.form.nrgLinksValue.value);'></form>"); |
|
break; |
|
case "drama": |
|
d3.select("#codetext").html("<h3>Code</h3><p>Loading a Dramatic Network uses the same code to load all preset networks, so maybe this should focus on the CSV being loaded.</p>"); |
|
d3.select("#citations").html("<h3>Citations</h3><ol><li>Moretti, Franco. 'Network Theory, Plot Analysis', New Left Review 68 (March-April 2011)</li><li>...</li></ol>"); |
|
d3.select("#lessontext").html("<h2>Dramatic Network</h2><p>This network represents speech-intereactions in one of Shakespeare's most famous plays, Hamlet. An edge from one character to another indicates the former has spoken to the latter; the weight of the edge indicates the number of words spoken. This network was first constructed by hand by Franco Moretti in 'Network Theory, Plot Analysis', published in New Left Review 68 (March-April 2011). Since then, researchers in the Literary Lab have constructed networks from each of Shakespeare's plays, as well as the plays of Aeschylus, Euripides, Sophocles, Aristophanes, Seneca, Racine, Corneille, and Ibsen. For more information, see the Literary Lab's second pamphlet on this work, available <a href='http://litlab.stanford.edu/?page_id=255'>here</a>.</p><p>If plotted, the network is laid out according to number of speech events (y-axis) by amount of words spoken (x-axis)."); |
|
break; |
|
case "darwin": |
|
d3.select("#codetext").html("<h3>Code</h3><p>Loading a Genaological Network uses the same code to load all preset networks, so maybe this should focus on the CSV being loaded.</p>"); |
|
d3.select("#citations").html("<h3>Citations</h3><ol><li>...</li><li>...</li></ol>"); |
|
d3.select("#lessontext").html("<h2>Genealogical Network</h2><p>This network consists of individuals with the last name Darwin, from a genealogical network of British cultural elites. The network does not include any children or spouses with different surnames.</p><p>If plotted, nodes are laid out by birthdate (x-axis) and lifespan (y-axis)"); |
|
break; |
|
case "dgsd": |
|
d3.select("#codetext").html("<h3>Code</h3>"); |
|
d3.select("#citations").html("<h3>Citations</h3><ol><li>...</li><li>...</li></ol>"); |
|
d3.select("#lessontext").html("<h2>Political Administrative Network</h2><p>The Digital Gazetteer of the Song Dynasty describes the manner in which administrative units were organized during the Song Dynasty. Here we can see counties, prefectures, and towns in Fujian Circuit.</p><p>In a sense, this is an n-partite graph, meaning that the network consists of nodes of different types (n indicating the number of different types), since it represents distinct administrative entities the sets of which (counties, prefectures, towns, circuits) do not directly connect within each set. e.g. A county does not connect to a county but rather connects to a prefecture or town, which likewise do not ever connect to members of the same class but rather administrative units above or below them.</p><p>Networks that represent different classes or categories of nodes are more difficult to measure and represent than networks that represent single categories of nodes. Of course, if one's object of study is a broader category, such as 'administrative units' then it avoids this issue.</p><p>If plotted, the network is laid out geographically, with unknown locations inheriting the point location of their parent unit (except for the circuit itself, which is laid at the geographic center of the known points.</p><p><a href='http://thenounproject.com/noun/city/#icon-No1566'>City icon by Thibault Geffroy, from The Noun Project</a></p>"); |
|
break; |
|
case "pathfinding": |
|
d3.select("#codetext").html("<h3>Code</h3><p>This one is going to give you fits, because the same code is used for individual paths and aggregated statistics.</p>"); |
|
d3.select("#citations").html("<h3>Citations</h3><ol><li>...</li><li>...</li></ol>"); |
|
d3.select("#lessontext").html("<h2>Network Pathfinding</h2><p>Finding the shortest path between two nodes in a network provides the basis for several network statistics measures such as Betweenness, Network Diameter, and Closeness.</p> <p>Network pathfinding is accomplished using various pathfinding algorithms, the most common being Dijkstra's algorithm, which is suitable for small networks like this but not for the large networks typically analyzed with packages such as Gephi. For large networks, heuristics need to be employed to improve the efficiency of an algorithm. One such pathfinding algorithm that employs heuristics is <a href='http://en.wikipedia.org/wiki/A*_search_algorithm'>A*</a>.</p><p>Notice that the path between nodes in a network can change or cease to exist if the network is directed instead of undirected.</p>"); |
|
break; |
|
case "centrality": |
|
d3.select("#codetext").html("<h3>Code</h3><p>Part of this code is from Pathfinding.</p>"); |
|
d3.select("#citations").html("<h3>Citations</h3><ol><li>1. <a href='http://faculty.ucr.edu/~hanneman/nettext/C10_Centrality.html'>Hanneman, R. & Riddle, M. Introduction to Social Network Methods - Chapter 10. Centrality</a></li><li>...</li></ol>"); |
|
d3.select("#lessontext").html("<h2>Centrality</h2><p>Centrality is a general term indicating a measure of a node's location in a network relative to other nodes in the network.</p><p>One measure, shown first, is the average Least Cost Path to all the nodes in the network. This <input type='button' onclick='sizeByStats(\"Average Path Length\")' value='Average Path Length' /> is similar to (these should be buttons) Closeness or Farness centrality.</p><p>Another measure is <input type='button' onclick='sizeByStats(\"Betweenness\")' value='Betweenness Centrality' /> which tallies the number of times a node is crossed for every least cost path in the network.</p><p>There are many more centrality measures some of which are described in [1].</p>"); |
|
break; |
|
case "clustering": |
|
d3.select("#codetext").html("<h3>Code</h3><p>This code only does undirected</p>"); |
|
d3.select("#citations").html("<h3>Citations</h3><ol><li>...</li><li>...</li></ol>"); |
|
d3.select("#lessontext").html("<h2>Clustering</h2><p>The clustering coefficient of a node is determined by comparing the number of connections between connected nodes to the number of possible connections between connected nodes. A clustering coefficient of 1 indicates a clique, which is a set of nodes that are all connected to each other. The local clustering coefficient is the value for an individual node, while the global clustering coefficient is the average of this value for the entire network.</p>"); |
|
break; |
|
case "egonetwork": |
|
d3.select("#codetext").html("<h3>Code</h3><p>Ego network code.</p>"); |
|
d3.select("#citations").html("<h3>Citations</h3><ol><li>...</li><li>...</li></ol>"); |
|
d3.select("#lessontext").html("<h2>Ego Network</h2><p>Ego networks show the local area of a network around a node. In this case, it's fixed to any node within two steps of the node you click on.</p>"); |
|
break; |
|
case "spatialproblem": |
|
d3.select("#codetext").html("<h3>Code</h3><p>Part of this code is from showing ego networks.</p>"); |
|
d3.select("#citations").html("<h3>Citations</h3><ol><li>...</li><li>...</li></ol>"); |
|
d3.select("#lessontext").html("<h2>The Spatial Problem</h2><p>The spatial problem in network visualization is the misrepresentation of similarity using space. By placing nodes on a visual plane, the implication is that nodes that are near each other spatially are near each other topologically. Unfortunately, this is often not the case. Here we can see nodes that are near each other spatially but distant from each other topologically.</p><p>A weighted version of this problem would not use raw ego networks but rather a fixed cost, and can be used to highlight, especially in transportation networks, how topography influences topology.</p>"); |
|
break; |
|
case "forcealgo": |
|
d3.select("#codetext").html("<h3>Code</h3><p>This relies on the standard D3.js force-directed layout behavior.</p>"); |
|
d3.select("#citations").html("<h3>Citations</h3><ol><li>...</li><li>...</li></ol>"); |
|
d3.select("#lessontext").html("<h2>Force-Directed Layout</h2><p>A popular method for laying out networks is to assign repulsive and attractive forces to nodes and links so that the emergent behavior of the competing forces produces a network that is more legible than manually or hierarchically placing the nodes. These competing forces are typcially a repulsive force exerted by nodes (which can be based on a numerical attribute of the node or a fixed value), an attractive force exerted by shared links between nodes (which can be based on the strength of the length, typically known as \"weight\" or fixed) and a canvas gravity that draws nodes toward the center of the screen and prevents them from being pushed beyond the view of the user.</p><p>Force-directed layouts do not typically assign any value to a node being placed along the x- or y-axis beyond the confluence of forces acting upon it from nearby nodes and links. As a result, even a very stable and readable force-directed layout can be mirrored or rotated without otherwise changing. This has had the effect upon scholars of assuming that there was something wrong with a force-directed layout that placed a node on the 'top' or 'left' in one layout but on the 'bottom' or 'right' in another. Such behavior is part of the force-directed layout unless specifically designed otherwise.</p>"); |
|
break; |
|
case "plotlayout": |
|
d3.select("#codetext").html("<h3>Code</h3><p>The code first shuts down the force-directed algorithm, then transforms the location of the nodes and edges using typical transition() behavior, then updates the .x/.px/.y/.py attributes so that if the force-directed algorithm is reinitialized, it restarts with nodes and edges in the proper position.</p>"); |
|
d3.select("#citations").html("<h3>Citations</h3><ol><li>...</li><li>...</li></ol>"); |
|
d3.select("#lessontext").html("<h2>Plot Layouts</h2><p>Nodes are ultimately data points with lines drawn between them. As such, they can be plotted like any data points by setting their position based on such attributes. This is used for nodes that represent geographic entities by placing them using their geographic coordinates, and can be used in traditional scatterplot fashion using built-in functionality in network analysis and visualization packages such as Gephi.</p>"); |
|
break; |
|
|
|
} |
|
} |
|
|
|
function initializeGraph(newGraph) { |
|
newNodes = []; |
|
newLinks = []; |
|
//We need a hash to fit the link structure of D3's force-directed layout |
|
nodeHash = {}; |
|
|
|
for ( x = 0; x < newGraph.nodes.length; x++ ) { |
|
newNodes.push(newGraph.nodes[x]); |
|
nodeHash[String(newGraph.nodes[x].id)] = x; |
|
} |
|
|
|
for ( x = 0; x < newGraph.links.length; x++ ) { |
|
newLinks.push({id: x, source: newGraph.nodes[nodeHash[newGraph.links[x].source]], target: newGraph.nodes[nodeHash[newGraph.links[x].target]], "cost": newGraph.links[x].cost, "weight": newGraph.links[x].invcost }); |
|
} |
|
|
|
|
|
force = d3.layout.force() |
|
.size([width, height]) |
|
.nodes(newNodes) // initialize with a single node |
|
.links(newLinks) |
|
.linkDistance(60) |
|
.charge(-60) |
|
.on("tick", tick); |
|
|
|
var svg = d3.select("#viz").append("svg") |
|
.attr("width", width) |
|
.attr("height", height) |
|
.attr("id", "networkViz"); |
|
|
|
svg.append("rect") |
|
.attr("width", width) |
|
.attr("height", height) |
|
.attr("id","backgroundRect") |
|
.on("mousemove", mousemove); |
|
|
|
nodes = force.nodes(); |
|
links = force.links(); |
|
node = svg.selectAll(".node"); |
|
link = svg.selectAll(".link"); |
|
arrowhead = svg.selectAll(".link"); |
|
|
|
cursor = svg.append("circle") |
|
.attr("transform", "translate(-100,-100)") |
|
.attr("class", "cursor") |
|
.attr("r", 1) |
|
.style("opacity", 0); |
|
|
|
|
|
restart(); |
|
} |
|
|
|
function mousemove() { |
|
cursor.attr("transform", "translate(" + d3.mouse(this) + ")"); |
|
} |
|
|
|
function mousedown() { |
|
var point = d3.mouse(this), |
|
node = {id: nodes.length, label: "Node" + nodes.length, lat: .5, long: .25, weight: 1, x: point[0], y: point[1]}, |
|
n = nodes.push(node); |
|
|
|
// add links to any nearby nodes |
|
nodes.forEach(function(target) { |
|
var x = target.x - node.x, |
|
y = target.y - node.y; |
|
if (Math.sqrt(x * x + y * y) < 30) { |
|
links.push({id: links.length, source: node, target: target, cost: .5}); |
|
} |
|
}); |
|
|
|
restart(); |
|
} |
|
|
|
function tick() { |
|
link.attr("x1", function(d) { return d.source.x; }) |
|
.attr("y1", function(d) { return d.source.y; }) |
|
.attr("x2", function(d) { return d.target.x; }) |
|
.attr("y2", function(d) { return d.target.y; }); |
|
|
|
node.attr("transform",function(d) {return "translate(" + d.x + "," + d.y + ")"}) |
|
|
|
arrowhead |
|
.attr("cx", function(d) {return ((d.target.x * .9) + (d.source.x * .1))}) |
|
.attr("cy", function(d) {return ((d.target.y * .9) + (d.source.y * .1))}) |
|
|
|
|
|
} |
|
|
|
function addNodes() { |
|
// id="addNodesButton" value="Add nodes" |
|
if (d3.select("#addNodesButton").attr("value") == "Add nodes") { |
|
d3.select("#addNodesButton").attr("value", "Stop adding nodes"); |
|
d3.select("#backgroundRect").on("mousedown", mousedown); |
|
cursor.transition().duration(300).attr("r", 30).style("opacity", 1); |
|
d3.select("#definitionbox").html("Clicking on the canvas will add a new node and connect it to nearby nodes"); |
|
} |
|
else { |
|
d3.select("#addNodesButton").attr("value", "Add nodes"); |
|
d3.select("#backgroundRect").on("mousedown", null); |
|
cursor.transition().duration(300).attr("r", 1).style("opacity", 0); |
|
d3.select("#definitionbox").html("Clicking on the canvas will not add a new node"); |
|
} |
|
} |
|
|
|
function changeGravity() { |
|
d3.select("#definitionbox").html("Canvas gravity draws all nodes toward the center of the canvas, preventing them from flying out of view."); |
|
} |
|
|
|
function highlightNodes() { |
|
d3.selectAll("circle.node").transition().duration(300).style("stroke-width", 5); |
|
d3.selectAll("circle.node").transition().delay(300).duration(300).style("stroke-width", 0); |
|
|
|
if (document.getElementById('nodeCheckbox').checked == true) { |
|
document.getElementById("repulsionSlider").disabled=true; |
|
d3.select("#definitionbox").html("Nodes exert a repulsion on other nodes based on their degree centrality."); |
|
} |
|
else { |
|
document.getElementById("repulsionSlider").disabled=false; |
|
d3.select("#definitionbox").html("Nodes exert a fixed value of repulsion set with the slider."); |
|
} |
|
} |
|
|
|
function highlightEdges() { |
|
d3.selectAll("line.link").transition().duration(300).style("stroke", "black"); |
|
d3.selectAll("line.link").transition().delay(300).duration(300).style("stroke", "#999999") |
|
|
|
if (document.getElementById('edgeCheckbox').checked == true) { |
|
document.getElementById("attractionSlider").disabled=true; |
|
d3.select("#definitionbox").html("Nodes attract connected nodes based on the strength of the shared link."); |
|
} |
|
else { |
|
document.getElementById("attractionSlider").disabled=false; |
|
d3.select("#definitionbox").html("Nodes attract connected nodes based on the fixed value set on the slider."); |
|
} |
|
} |
|
|
|
function changeDirectedness() { |
|
if (document.getElementById('directedCheck').checked == true) { |
|
d3.select("#definitionbox").html("The network is now directed, edges are only followed source to target"); |
|
} |
|
else { |
|
d3.select("#definitionbox").html("The network is now undirected, edges are bidirectional"); |
|
} |
|
arrowhead.transition().duration(300).style("opacity", function() {return (document.getElementById('directedCheck').checked == true) ? 1: 0}).attr("r", 8); |
|
arrowhead.transition().delay(300).duration(300).attr("r", 2); |
|
} |
|
|
|
function restart() { |
|
link = link.data(links); |
|
arrowhead = arrowhead.data(links); |
|
|
|
node = node.data(nodes); |
|
|
|
nodeg = node.enter().insert("g", ".cursor") |
|
.attr("class", "node") |
|
.call(force.drag); |
|
|
|
nodeg.append("circle") |
|
.attr("r", 1) |
|
.attr("class", "node") |
|
.style("stroke-width", 0) |
|
.style("stroke", "#808080") |
|
; |
|
|
|
nodeg.append("text") |
|
.attr("x", -5) |
|
.attr("y", -5) |
|
.attr("class", "node") |
|
.text(function(d) {return d.label}) |
|
.style("display", "none") |
|
; |
|
|
|
nodeg.append("image") |
|
.attr("class", "node") |
|
.attr("xlink:href", function(d) { return ("dot.svg")}); |
|
|
|
node.exit().transition().duration(300).attr("r",1).remove(); |
|
|
|
link.enter().insert("line", ".node") |
|
.attr("class", "link"); |
|
|
|
link.exit().remove(); |
|
|
|
|
|
arrowhead.enter().insert("circle", ".node") |
|
.attr("class", "arrowhead") |
|
.attr("r",2) |
|
.style("opacity", function() {return (document.getElementById('directedCheck').checked == true) ? 1: 0}); |
|
|
|
arrowhead.exit().remove(); |
|
|
|
force.start(); |
|
//Apparently you have to delay the resizing to keep D3 from holding the elements that are supposed to be .removed() |
|
resize(currentSizing); |
|
|
|
|
|
} |
|
|
|
function getBetweenness() { |
|
// |
|
updateText("Betweenness"); |
|
} |
|
|
|
function updateForce() { |
|
force.stop(); |
|
|
|
var newGravity = document.getElementById('gravitySlider').value; |
|
var newCharge = document.getElementById('repulsionSlider').value; |
|
var newLStrength = document.getElementById('attractionSlider').value; |
|
|
|
document.getElementById('gravityInput').value = newGravity; |
|
document.getElementById('repulsionInput').value = newCharge; |
|
document.getElementById('attractionInput').value = newLStrength; |
|
|
|
force |
|
.charge(newCharge) |
|
.linkDistance(newLStrength) |
|
.gravity(newGravity) |
|
; |
|
|
|
|
|
if (document.getElementById('edgeCheckbox').checked == true) { |
|
var minWeight = d3.min(links, function(d) {return parseFloat(d["cost"])}); |
|
var maxWeight = d3.max(links, function(d) {return parseFloat(d["cost"])}); |
|
|
|
//notice this is the reverse of the max/min ramp in the styling, because we're not determining link strength but the inverse: Link Distance |
|
var edgeRamp = d3.scale.linear().domain([minWeight,maxWeight]).range([.5,3]).clamp(true); |
|
|
|
force.linkDistance(function(d) {return (edgeRamp(parseFloat(d["cost"])) * 30)}) |
|
} |
|
|
|
if (document.getElementById('nodeCheckbox').checked == true) { |
|
var minSize = d3.min(nodes, function(d) {return parseFloat(d["weight"])}); |
|
var maxSize = d3.max(nodes, function(d) {return parseFloat(d["weight"])}); |
|
var sizingRamp = d3.scale.linear().domain([minSize,maxSize]).range([1,10]).clamp(true); |
|
|
|
force.charge(function(d) {return (sizingRamp(parseFloat(d["weight"])) * -20)}) |
|
} |
|
|
|
force.start(); |
|
} |
|
|
|
function loadGraph(nodePath, edgePath, imagePath) { |
|
var newGraphObj = {nodes: [], links: []}; |
|
d3.csv(nodePath, function(error, nodescsv){ |
|
d3.csv(edgePath, function(error, edgescsv){ |
|
newGraphObj.nodes = nodescsv; |
|
newGraphObj.links = edgescsv; |
|
|
|
d3.select("#networkViz").remove(); |
|
initializeGraph(newGraphObj); |
|
changeImage(imagePath); |
|
}) |
|
}) |
|
} |
|
|
|
function establishLinks(inGraph) { |
|
var outGraph = {nodes: [], links: []}; |
|
//We need a hash to fit the link structure of D3's force-directed layout |
|
nodeHash = {}; |
|
|
|
for ( x = 0; x < inGraph.nodes.length; x++ ) { |
|
outGraph.nodes.push(inGraph.nodes[x]); |
|
nodeHash[String(inGraph.nodes[x].id)] = x; |
|
} |
|
|
|
for ( x = 0; x < inGraph.links.length; x++ ) { |
|
outGraph.links.push({source: inGraph.nodes[nodeHash[inGraph.links[x].source]], target: inGraph.nodes[nodeHash[inGraph.links[x].target]], "cost": inGraph.links[x].cost, "weight": inGraph.links[x].invcost }); |
|
} |
|
|
|
return outGraph; |
|
|
|
} |
|
|
|
function randomGraph(nodeNumber, linkChance) { |
|
|
|
newGraphObj = {nodes: [], links: []}; |
|
|
|
var x=0; |
|
while (x < nodeNumber) { |
|
var randomLat = Math.random(); |
|
var randomLong = Math.random(); |
|
var newNodeObj = {label: "Node"+x, id: x, lat: randomLat, long: randomLong} |
|
newGraphObj.nodes.push(newNodeObj); |
|
var y=0; |
|
while (y < nodeNumber) { |
|
if (y != x && Math.random() < linkChance) { |
|
var randomEdgeWeight = Math.random(); |
|
newLinkObj = {source: x, target: y, weight: randomEdgeWeight, cost: randomEdgeWeight} |
|
newGraphObj.links.push(newLinkObj); |
|
} |
|
y++; |
|
} |
|
x++; |
|
} |
|
|
|
d3.select("#networkViz").remove(); |
|
initializeGraph(newGraphObj); |
|
|
|
} |
|
|
|
function plotLayout() { |
|
force.stop(); |
|
minX = d3.min(nodes, function(d) {return parseFloat(d["long"])}); |
|
maxX = d3.max(nodes, function(d) {return parseFloat(d["long"])}); |
|
minY = d3.min(nodes, function(d) {return parseFloat(d["lat"])}); |
|
maxY = d3.max(nodes, function(d) {return parseFloat(d["lat"])}); |
|
|
|
heightRamp=d3.scale.linear().domain([minY,maxY]).range([550,50]).clamp(true); |
|
widthRamp=d3.scale.linear().domain([minX,maxX]).range([50,450]).clamp(true); |
|
|
|
d3.selectAll("g.node").transition().duration(1000).attr("transform",function(d) {return "translate(" + widthRamp(parseFloat(d["long"])) + "," + heightRamp(parseFloat(d["lat"])) + ")"}) |
|
|
|
for (x in nodes) { |
|
nodes[x].x = widthRamp(parseFloat(nodes[x].long)); |
|
nodes[x].px = widthRamp(parseFloat(nodes[x].long)); |
|
nodes[x].y = heightRamp(parseFloat(nodes[x].lat)); |
|
nodes[x].py = heightRamp(parseFloat(nodes[x].lat)); |
|
} |
|
|
|
link.transition().duration(1000).attr("x1", function(d) { return widthRamp(d.source.long); }) |
|
.attr("y1", function(d) { return heightRamp(d.source.lat); }) |
|
.attr("x2", function(d) { return widthRamp(d.target.long); }) |
|
.attr("y2", function(d) { return heightRamp(d.target.lat); }); |
|
|
|
arrowhead.transition().duration(1000) |
|
.attr("cx", function(d) {return ((d.target.x * .9) + (d.source.x * .1))}) |
|
.attr("cy", function(d) {return ((d.target.y * .9) + (d.source.y * .1))}) |
|
|
|
} |
|
|
|
function clearGraph() { |
|
|
|
} |
|
function deleteNodes(nodeArray) { |
|
var y = links.length - 1; |
|
while (y > -1) { |
|
if (nodeArray.indexOf(links[y].source.id) + nodeArray.indexOf(links[y].target.id) > -2) { |
|
links.splice(y,1); |
|
} |
|
y--; |
|
} |
|
var y = nodes.length - 1; |
|
while (y > -1) { |
|
if (nodeArray.indexOf(nodes[y].id) > -1) { |
|
nodes.splice(y,1); |
|
} |
|
y--; |
|
} |
|
|
|
restart(); |
|
|
|
} |
|
function deleteRandomNodes() { |
|
var randomNodeArray = getRandomSubarray(nodes, 5); |
|
var sampledIDValues = []; |
|
|
|
for (x in randomNodeArray) { |
|
sampledIDValues.push(randomNodeArray[x].id) |
|
} |
|
|
|
deleteNodes(sampledIDValues); |
|
} |
|
|
|
function getRandomSubarray(arr, size) { |
|
var shuffled = arr.slice(0), i = arr.length, temp, index; |
|
while (i--) { |
|
index = Math.floor(i * Math.random()); |
|
temp = shuffled[index]; |
|
shuffled[index] = shuffled[i]; |
|
shuffled[i] = temp; |
|
} |
|
return shuffled.slice(0, size); |
|
} |
|
|
|
function resize(byValue) { |
|
currentSizing = byValue; |
|
var minSize = d3.min(nodes, function(d) {return parseFloat(d["weight"])}); |
|
var maxSize = d3.max(nodes, function(d) {return parseFloat(d["weight"])}); |
|
var minWeight = d3.min(links, function(d) {return parseFloat(d["cost"])}); |
|
var maxWeight = d3.max(links, function(d) {return parseFloat(d["cost"])}); |
|
|
|
var sizingRamp = d3.scale.linear().domain([minSize,maxSize]).range([1,10]).clamp(true); |
|
var edgeRamp = d3.scale.linear().domain([maxWeight,minWeight]).range([.5,3]).clamp(true); |
|
|
|
switch(byValue) |
|
{ |
|
case "nothing": |
|
d3.selectAll("circle.node").attr("r", 5) |
|
|
|
d3.selectAll("image.node").attr("x", -2.5) |
|
.attr("y", -2.5) |
|
.attr("width", 5) |
|
.attr("height", 5); |
|
|
|
break; |
|
case "degree": |
|
d3.selectAll("circle.node").attr("r", function(d) {return sizingRamp(d["weight"])}) |
|
|
|
d3.selectAll("image.node").attr("x", function(d) { return -((sizingRamp(d["weight"]))/2)}) |
|
.attr("y", function(d) { return -((sizingRamp(d["weight"]))/2)}) |
|
.attr("width", function(d) { return (sizingRamp(d["weight"]))}) |
|
.attr("height", function(d) { return (sizingRamp(d["weight"]))}); |
|
|
|
break; |
|
} |
|
|
|
d3.selectAll("line.link").style("stroke-width", function(d) {return edgeRamp(d["cost"])}) |
|
} |
|
|
|
function pathfinding(sourceID, targetID, directedSearch, searchType) { |
|
var graphStats = {}; |
|
|
|
if (searchType == "aggregate") { |
|
var aggregatedCosts = {}; |
|
for (xx in nodes) { |
|
graphStats[nodes[xx].id] = {}; |
|
graphStats[nodes[xx].id]["Betweenness"] = 0; |
|
aggregatedCosts[nodes[xx].id] = {}; |
|
for (yy in nodes) { |
|
aggregatedCosts[nodes[xx].id][nodes[yy].id] = +Infinity; |
|
} |
|
} |
|
} |
|
else { |
|
for (xx in nodes) { |
|
graphStats[nodes[xx].id] = {}; |
|
graphStats[nodes[xx].id]["Betweenness"] = 0; |
|
} |
|
} |
|
|
|
// Two possibilities, either we're running an individual search, in which case we stop when we find the path, or we're aggregating values for the entire graph, in which case we run the paths from every node to every node |
|
var aggregatedSourceID = 0; |
|
while ((searchType == "individual" && pathFound != true) || (searchType != "individual" && aggregatedSourceID < nodes.length)) { |
|
|
|
// Set a fresh TargetID in this loop; |
|
var aggregatedTargetID = 0; |
|
|
|
//For aggregated statistics, we start at node 0 and calculate for all nodes |
|
if (searchType == "aggregate") {sourceID = nodes[aggregatedSourceID].id;} |
|
|
|
// we need to know for each source the vertices that have been calculated |
|
var visitedVertices = []; |
|
|
|
//but we store those vertices in an object array, this allows us to indexOf the previous array and jump to the specific cost for the calculated vertex(node) |
|
vertexCost = {}; |
|
|
|
// set the cost to infinity so that we know what we've calculated and what we haven't |
|
for (n in nodes) { |
|
vertexCost[nodes[n].id] = +Infinity; |
|
} |
|
|
|
// the source node is 0 |
|
vertexCost[sourceID] = 0; |
|
// and thus is calculated |
|
calculatedVertices = [sourceID]; |
|
// parentVertex is used to walk back through the network once we've calculated the shortest path because the aggregate of shortest paths is the shortest path in a network |
|
parentVertex = {}; |
|
|
|
// we need a signal to point out that we've found a path for the individual check |
|
var pathFound = false; |
|
//we set a high minimum value because we need to cycle through the links to pick the lowest cost link to calculate first |
|
var minimumValue = 9999; |
|
|
|
//these are variables for holding possible source/target pairs |
|
var sourceValue = ""; |
|
var targetValue = ""; |
|
|
|
//we store the links in a separate object so that we can reference them with source/target pairs to highlight them later |
|
var linkID = 0; |
|
linkList = {}; |
|
|
|
//there are two possibilities: we're looking for one route, in which case we want to stop when we find the path, or we're looking for all routes, in which case we want to stop when we reach the end of the list of nodes |
|
while ((searchType == "individual" && pathFound != true) || (searchType != "individual" && aggregatedTargetID < nodes.length)) { |
|
|
|
//set the targetID to the current aggregate target node in the loop, if running the aggregate search |
|
if (searchType == "aggregate") {targetID = nodes[aggregatedTargetID].id;} |
|
|
|
while (pathFound == false ) { |
|
minimumValue = 9999; |
|
sourceValue = ""; |
|
targetValue = ""; |
|
linkID = 0; |
|
|
|
for (z in links) { |
|
var otherVertex = "none"; |
|
var startVertex = "none"; |
|
//find the next edge to check and make sure it's the lowest value |
|
if (calculatedVertices.indexOf(links[z].source.id) > -1 && calculatedVertices.indexOf(links[z].target.id) == -1) { |
|
startVertex = links[z].source.id; |
|
otherVertex = links[z].target.id; |
|
} |
|
//undirected search looks at target->source as well |
|
else if (directedSearch == false && calculatedVertices.indexOf(links[z].target.id) > -1 && calculatedVertices.indexOf(links[z].source.id) == -1) { |
|
startVertex = links[z].target.id; |
|
otherVertex = links[z].source.id; |
|
} |
|
if (otherVertex != "none") { |
|
if ((parseFloat(links[z].cost) + vertexCost[startVertex]) < minimumValue) { |
|
minimumValue = (parseFloat(links[z].cost) + vertexCost[startVertex]); |
|
sourceValue = startVertex; |
|
targetValue = otherVertex; |
|
linkID = z; |
|
} |
|
} |
|
} |
|
|
|
// if the minimum value is still 9999, then that means no paths were discovered, and there is no path |
|
if (minimumValue == 9999) { |
|
// vertexCost[targetID] = +Infinity; |
|
calculatedVertices.push(targetID); |
|
pathFound = true; |
|
} |
|
else { |
|
vertexCost[targetValue] = minimumValue; |
|
parentVertex[targetValue] = sourceValue; |
|
calculatedVertices.push(targetValue); |
|
|
|
//For a multidimensional object, you have to check and add new objects on-the-fly |
|
if (!linkList[sourceValue]) { |
|
linkList[sourceValue] = {}; |
|
} |
|
linkList[sourceValue][targetValue] = linkID; |
|
|
|
if (targetValue == targetID) { |
|
pathFound = true; |
|
} |
|
} |
|
|
|
} |
|
|
|
var computedPathArray = []; |
|
computedEdgeArray = []; |
|
// this is causing a strange error, so if the type is aggregate, just skip it |
|
if (minimumValue != 9999 && parentVertex[targetID]) { |
|
|
|
var reversePath = targetID; |
|
computedPathArray = []; |
|
while (reversePath != sourceID) { |
|
computedPathArray.push(reversePath); |
|
computedEdgeArray.push(linkList[parentVertex[reversePath]][reversePath]); |
|
reversePath = parentVertex[reversePath]; |
|
graphStats[reversePath]["Betweenness"] += 1; |
|
} |
|
//we shouldn't increase the source or target value for any paths, so decrement the sourceID betweenness |
|
graphStats[sourceID]["Betweenness"] -= 1; |
|
computedPathArray.push(sourceID); |
|
computedEdgeArray.push(linkList[sourceID][parentVertex[reversePath]]); |
|
|
|
} |
|
else if (searchType == "individual") { |
|
computedPathArray = ["Path not found"]; |
|
computedEdgeArray = ["Path not found"]; |
|
} |
|
|
|
|
|
aggregatedTargetID++; |
|
var alreadyComputed = true; |
|
if (aggregatedTargetID < nodes.length) { |
|
|
|
while (alreadyComputed == true && (nodes[aggregatedTargetID]) ) { |
|
|
|
//find out if we've already computed the new target as part of an earlier path |
|
if (calculatedVertices.indexOf(nodes[aggregatedTargetID].id) > -1) { |
|
aggregatedTargetID++; |
|
} |
|
else { |
|
alreadyComputed = false; |
|
} |
|
} |
|
|
|
} |
|
|
|
} |
|
var sumOfConnectedNodes = 0; |
|
var totalOfConnectedDistance = 0; |
|
for (x in vertexCost) { |
|
if (vertexCost[x]) { |
|
if (vertexCost[x] != +Infinity) { |
|
sumOfConnectedNodes++; |
|
totalOfConnectedDistance += vertexCost[x]; |
|
} |
|
} |
|
} |
|
|
|
graphStats[sourceID]["Total Connectivity"] = sumOfConnectedNodes; |
|
if(sumOfConnectedNodes == 0) { |
|
graphStats[sourceID]["Average Path Length"] = 0; |
|
} |
|
else { |
|
graphStats[sourceID]["Average Path Length"] = totalOfConnectedDistance / sumOfConnectedNodes; |
|
} |
|
|
|
aggregatedSourceID++; |
|
} |
|
if (searchType == "individual") { |
|
return {nodes: computedPathArray, paths: computedEdgeArray}; |
|
} |
|
else { |
|
return graphStats; |
|
} |
|
} |
|
|
|
function selectPath() { |
|
d3.selectAll("g.node").on("click",setSource).style("cursor", "pointer") |
|
d3.select("#definitionbox").html("Select a node to compute a path from"); |
|
} |
|
|
|
function setSource(d) { |
|
pathSource = d.id; |
|
d3.selectAll("g.node").on("click",setTarget); |
|
d3.select("#definitionbox").html(d.id + "selected - select a node to compute the path to"); |
|
|
|
} |
|
|
|
function setTarget(d) { |
|
|
|
var directedValue = document.getElementById('directedCheck').checked; |
|
|
|
var computedPathArray = pathfinding(pathSource,d.id,directedValue,"individual"); |
|
|
|
if (computedPathArray.nodes[0] == "Path not found") { |
|
d3.select("#definitionbox").html("No path"); |
|
d3.selectAll("circle.node").transition().duration(300).style("fill", function(p) {return [d.id,pathSource].indexOf(p.id) > -1 ? "blue" : "black"}); |
|
d3.selectAll("line.link").transition().duration(300).style("stroke","black"); |
|
} |
|
else { |
|
computedPathArray.paths.reverse(); |
|
computedPathArray.nodes.reverse(); |
|
d3.select("#definitionbox").html("<span style='color:blue;'>Path from " + pathSource + " to " + d.id +"</span>"); |
|
d3.selectAll("circle.node").transition().delay(function(d) {return computedPathArray.nodes.indexOf("" + d.id) > -1 ? (computedPathArray.nodes.indexOf("" + d.id) * 500) + 500 : 0}).duration(300).style("fill", function(d) {return computedPathArray.nodes.indexOf(d.id) > -1 ? "blue" : "pink"}); |
|
d3.selectAll("line.link").transition().delay(function(d) {return computedPathArray.paths.indexOf("" + d.id) > -1 ? (computedPathArray.paths.indexOf("" + d.id) * 500) + 500 : 0}).duration(300).style("stroke", function(d) {return computedPathArray.paths.indexOf("" + d.id) > -1 ? "blue" : "pink"}); |
|
} |
|
d3.selectAll("g.node").on("click", null).style("cursor","auto"); |
|
|
|
pathSource = ""; |
|
|
|
} |
|
|
|
function sizeByStats(statname) { |
|
var minStat = 9999; |
|
var maxStat = 0; |
|
for (x in nodes) { |
|
if (graphStats[nodes[x].id]["Total Connectivity"] != 0) { |
|
minStat = Math.min(minStat, graphStats[nodes[x].id][statname]); |
|
maxStat = Math.max(maxStat, graphStats[nodes[x].id][statname]); |
|
} |
|
} |
|
|
|
d3.select("#definitionbox").html("Nodes are now sized by " + statname); |
|
|
|
var sizeRamp = d3.scale.linear().domain([minStat,maxStat]).range([2,10]).clamp(true); |
|
d3.selectAll("circle.node").transition().duration(300).attr("r", function(d,i) {return graphStats[nodes[i].id][statname] > 0 ? sizeRamp(graphStats[nodes[i].id][statname]) : 1}); |
|
d3.selectAll("image.node").transition().duration(300) |
|
.attr("height", function(d,i) {return graphStats[nodes[i].id]["Total Connectivity"] > 0 ? sizeRamp(graphStats[nodes[i].id][statname]) : 1}) |
|
.attr("width", function(d,i) {return graphStats[nodes[i].id]["Total Connectivity"] > 0 ? sizeRamp(graphStats[nodes[i].id][statname]) : 1}) |
|
.attr("x", function(d,i) {return graphStats[nodes[i].id]["Total Connectivity"] > 0 ? -(sizeRamp(graphStats[nodes[i].id][statname]) / 2) : -.5}) |
|
.attr("y", function(d,i) {return graphStats[nodes[i].id]["Total Connectivity"] > 0 ? -(sizeRamp(graphStats[nodes[i].id][statname]) / 2) : -.5}); |
|
|
|
} |
|
|
|
function calculateCentrality() { |
|
var directedValue = document.getElementById('directedCheck').checked; |
|
d3.select("#definitionbox").html("Calculating paths..."); |
|
//Here's closeness, at least |
|
graphStats = pathfinding(0,0,directedValue,"aggregate"); |
|
|
|
sizeByStats("Average Path Length"); |
|
|
|
|
|
// var sizeRamp = d3.scale.linear().domain([minConnected,maxConnected]).range([1,10]).clamp(true); |
|
// d3.selectAll("circle.node").attr("r", function(d,i) {return sizeRamp(graphStats[nodes[i].id]["Total Connectivity"])}); |
|
|
|
} |
|
|
|
function findEgoNetwork(searchNode, egoNetworkDegree, isDirected, searchType) { |
|
var egoNetwork = {}; |
|
for (x in nodes) { |
|
if (nodes[x].id == searchNode || searchType == "aggregate") { |
|
egoNetwork[nodes[x].id] = [nodes[x].id]; |
|
var z = 0; |
|
while (z < egoNetworkDegree) { |
|
var thisEgoRing = egoNetwork[nodes[x].id].slice(0); |
|
for (y in links) { |
|
if (thisEgoRing.indexOf(links[y].source.id) > -1 && thisEgoRing.indexOf(links[y].target.id) == -1) { |
|
egoNetwork[nodes[x].id].push(links[y].target.id) |
|
} |
|
else if (isDirected == false && thisEgoRing.indexOf(links[y].source.id) == -1 && thisEgoRing.indexOf(links[y].target.id) > -1) { |
|
egoNetwork[nodes[x].id].push(links[y].source.id) |
|
} |
|
} |
|
z++; |
|
} |
|
} |
|
} |
|
if (searchType == "aggregate") { |
|
//if it's checking the entire network, pass back the entire object of arrays |
|
return egoNetwork; |
|
} |
|
else { |
|
//Otherwise only give back the array that corresponds with the search node |
|
return egoNetwork[searchNode]; |
|
} |
|
} |
|
|
|
function showEgoNetwork() { |
|
d3.selectAll("g.node").on("click",findEgo).style("cursor", "pointer"); |
|
d3.select("#definitionbox").html("Select a node to see its 2-Degree Ego Network"); |
|
} |
|
|
|
|
|
function findEgo(d) { |
|
d3.select("#definitionbox").html("<span style='color:blue;'>All nodes within 2 steps of</span><span style='color:purple;'> " + d.label + "</span>"); |
|
d3.selectAll("g.node").on("click",null).style("cursor", "auto"); |
|
var directedValue = document.getElementById('directedCheck').checked; |
|
var computedEgoArray = findEgoNetwork(d.id, 2, directedValue,"individual"); |
|
|
|
d3.selectAll("circle.node").style("fill", function(p) {return p.id == d.id ? "purple" : computedEgoArray.indexOf(p.id) > -1 ? "blue" : "pink"}) |
|
|
|
} |
|
|
|
function spatialProblem() { |
|
var closeNodes = []; |
|
|
|
//We can decrement the ego network size |
|
var egoNetworkSize = 5; |
|
while (closeNodes.length == 0) { |
|
egoNetworkSize--; |
|
|
|
var computedEgoObject = findEgoNetwork(0, egoNetworkSize, false,"aggregate"); |
|
var problemDistance = 20; |
|
//The while statement means run this until we get to a distance where there are some nodes that violate this principle |
|
while (closeNodes.length == 0 && (problemDistance < 60 || egoNetworkSize == 2)) { |
|
for (x in nodes) { |
|
for (y in nodes) { |
|
if (computedEgoObject[nodes[x].id].indexOf(nodes[y].id) == -1) { |
|
if (Math.sqrt(Math.pow((nodes[x].x - nodes[y].x),2) + Math.pow((nodes[x].y - nodes[y].y),2)) < problemDistance) { |
|
closeNodes.push(nodes[x].id); |
|
closeNodes.push(nodes[y].id); |
|
} |
|
} |
|
} |
|
} |
|
problemDistance += 20; |
|
} |
|
} |
|
|
|
d3.select("#definitionbox").html("<span style='color:blue;'>Nodes separated by more than "+egoNetworkSize+" steps but closer than " + problemDistance + "px</span>"); |
|
|
|
d3.selectAll("circle.node").transition().duration(300).style("fill", function(d) {return closeNodes.indexOf(d.id) > -1 ? "blue" : "pink"}).style("stroke-width", function(d) {return closeNodes.indexOf(d.id) > -1 ? 5 : 0}); |
|
d3.selectAll("circle.node").transition().delay(300).duration(300).style("stroke-width", 0); |
|
} |
|
|
|
function labelChange() { |
|
|
|
//This function now accounts for the size of the circle but bases that size off of the fixed childNode position of the circle in the g element (position [0] in this implementation) |
|
|
|
var newLabelSize = document.getElementById('labelSlider').value / 5; |
|
if (newLabelSize > 0) { |
|
d3.selectAll("text.node").style("display", "block").style("font-size", function(d) {return parseFloat(newLabelSize) * d3.select(this.parentNode.childNodes[0]).attr("r");}); |
|
} |
|
else { |
|
d3.selectAll("text.node").style("display", "none") |
|
} |
|
} |
|
|
|
function changeImage(newImageName) { |
|
d3.selectAll("image.node").attr("xlink:href", function(d) { return ("" + newImageName + ".svg")}); |
|
} |
|
|
|
function clusteringCoefficient() { |
|
|
|
//this implementation is currently only undirected |
|
|
|
//we'll store the value we compute in an object to use it to size the results |
|
var localClusteringCoefficient = {}; |
|
var maxClustering = 0; |
|
var minClustering = 99999; |
|
for (x in nodes) { |
|
localClusteringCoefficient[nodes[x].id] = 1; |
|
var connectedNodes = []; |
|
// find the nodes connected to this node and put them in an array |
|
for (y in links) { |
|
if (links[y].source.id == nodes[x].id) { |
|
connectedNodes.push(links[y].target.id); |
|
} |
|
else if (links[y].target.id == nodes[x].id) { |
|
connectedNodes.push(links[y].source.id); |
|
} |
|
} |
|
//only update the local clustering coefficient if we find more than 1 link (needs to be updated for directed graphs) |
|
if (connectedNodes.length > 1) { |
|
// each node connected to the node could possibly be connected to every other node |
|
var totalPossibleClustering = (connectedNodes.length - 1) * connectedNodes.length; |
|
var discoveredLinks = 0; |
|
for (y in links) { |
|
if (connectedNodes.indexOf(links[y].source.id) > -1 && connectedNodes.indexOf(links[y].target.id) > -1) { |
|
discoveredLinks++; |
|
} |
|
else if (connectedNodes.indexOf(links[y].target.id) > -1 && connectedNodes.indexOf(links[y].source.id) > -1) { |
|
discoveredLinks++; |
|
} |
|
} |
|
|
|
//Local clustering coefficient is equal to the number of connected nodes divided by the connectivity of those nodes between each other |
|
localClusteringCoefficient[nodes[x].id] = discoveredLinks / totalPossibleClustering; |
|
maxClustering = Math.max(localClusteringCoefficient[nodes[x].id], maxClustering); |
|
minClustering = Math.min(localClusteringCoefficient[nodes[x].id], minClustering); |
|
} |
|
} |
|
d3.selectAll("circle.node") |
|
|
|
var sizeRamp = d3.scale.linear().domain([minClustering,maxClustering]).range([2,10]).clamp(true); |
|
d3.selectAll("circle.node").transition().duration(300).attr("r", function(d,i) {return sizeRamp(localClusteringCoefficient[nodes[i].id])}); |
|
d3.selectAll("image.node").transition().duration(300) |
|
.attr("height", function(d,i) {return sizeRamp(localClusteringCoefficient[nodes[i].id])}) |
|
.attr("width", function(d,i) {return sizeRamp(localClusteringCoefficient[nodes[i].id])}) |
|
.attr("x", function(d,i) {return -(sizeRamp(localClusteringCoefficient[nodes[i].id]) / 2)}) |
|
.attr("y", function(d,i) {return -(sizeRamp(localClusteringCoefficient[nodes[i].id]) / 2)}); |
|
|
|
} |
|
|
|
function hierarchicalLayout() { |
|
for ( y = 0; y < nodes.length; y++ ) { |
|
nodes[y].fixed = false; |
|
} |
|
|
|
tick(); |
|
force.stop(); |
|
|
|
var orbitRank = 0; |
|
|
|
orbitArray = {}; |
|
|
|
orbitArray[centerID] = 0; |
|
|
|
var totalLinks = links.length; |
|
var openLinks = 0; |
|
orbitalRings = [1] |
|
|
|
while (openLinks < totalLinks){ |
|
for ( z = 0; z < links.length; z++) { |
|
if (links[z].target.fixed == true && links[z].target.fixed == true) { |
|
openLinks++; |
|
} |
|
else if (links[z].target.fixed == true) { |
|
assignedID = (links[z].source.id); |
|
assignedValue = (orbitArray[links[z].target.id] + 1); |
|
links[z].source.fixed = true; |
|
orbitArray[assignedID] = assignedValue; |
|
orbitalRings[orbitArray[links[z].target.id] + 1]++; |
|
} |
|
else if (links[z].source.fixed == true) { |
|
assignedID = (links[z].target.id); |
|
assignedValue = (orbitArray[links[z].source.id] + 1); |
|
links[z].target.fixed = true; |
|
orbitArray[assignedID] = assignedValue; |
|
orbitalRings[orbitArray[links[z].source.id] + 1]++; |
|
} |
|
} |
|
} |
|
|
|
} |
|
</script> |
