Appearance
Other centrality measures
This example shows how to compute different centrality measures on a graph and use them to style it. It provides degree centrality, closeness, betweenness and pagerank measures.
ts
import Ogma, { Node, Color } from '@linkurious/ogma';
import { pagerank } from './pagerank';
import { closeness } from './closeness';
import betweennes from '../../src/algorithms/betweenness';
type NodeData = {
centrality: number;
betweennes: number;
closeness: number;
degree: number;
pagerank: number;
};
const ogma = new Ogma<NodeData>({
container: 'graph-container'
});
const rule = ogma.styles.addRule({
nodeAttributes: {
radius: node => node?.getData('centrality'),
//color: '#0e379d',
text: {
backgroundColor: '#222',
color: '#fff',
padding: 5
}
}
});
const form = document.querySelector<HTMLFormElement>('#controls')!;
const onTypeChange = () => {
const type = form['centrality'].value;
const nodes = ogma.getNodes();
const values = nodes.getData(type);
nodes.setData('centrality', values);
rule.update({
nodeAttributes: {
color: ogma.rules.slices({
field: 'centrality',
values: [
// 6 RGB colors from dark blue to red
'#0e379d',
'#1e5fbd',
'#3a86ff',
'#ffbe0b',
'#fb5607',
'#ff006e'
],
stops: { min: Math.min(...values), max: Math.max(...values) }
}) as (node?: Node) => Color
}
});
form
.querySelectorAll('input')
.forEach(input => input.setAttribute('disabled', 'disabled'));
ogma.layouts
.force({
edgeStrength: 0,
charge: 0,
gravity: 0,
elasticity: 0.02
})
.then(() =>
form
.querySelectorAll('input')
.forEach(input => input.removeAttribute('disabled'))
);
};
form.addEventListener('change', onTypeChange);
const graph = await Ogma.parse.gexfFromUrl<NodeData>('files/airlines.gexf');
graph.nodes.forEach(node => {
node.data = {
pagerank: 5,
betweennes: 0,
closeness: 0,
degree: 0,
centrality: 0
};
});
await ogma.setGraph(graph);
await ogma.view.locateGraph();
const defaultSize = 5;
const nodes = ogma.getNodes();
// Pagerank centrality
// multiply by 500 to get a better visualization
nodes.setData(
'pagerank',
pagerank({ nodes }).map(v => defaultSize + v * 500)
);
// Closeness centrality
nodes.setData(
'closeness',
closeness({ nodes }).map(v => v * 10)
);
// Degree centrality
const maxDegree = Math.max(...nodes.getDegree());
nodes.setData(
'degree',
nodes.getDegree().map(d => (d / maxDegree + 1) * defaultSize)
);
nodes.setData(
'betweenness',
ogma.algorithms.betweenness({ nodes }).map(v => defaultSize + v * 100)
);
await onTypeChange();
html
<!doctype html>
<html>
<head>
<meta charset="utf-8" />
<link type="text/css" rel="stylesheet" href="styles.css" />
</head>
<body>
<div id="graph-container"></div>
<form id="controls" class="panel">
<p>
<label for="degree">
<span>Degree</span>
<input
type="radio"
id="degree"
value="degree"
checked
name="centrality"
/>
</label>
</p>
<p>
<label for="closeness">
<span>Closeness</span>
<input
type="radio"
id="closeness"
value="closeness"
name="centrality"
/>
</label>
</p>
<p>
<label for="betweenness">
<span>Betweenness</span>
<input
type="radio"
id="betweenness"
value="betweenness"
name="centrality"
/>
</label>
</p>
<p>
<label for="pagerank">
<span>PageRank</span>
<input
type="radio"
id="pagerank"
value="pagerank"
name="centrality"
/>
</label>
</p>
</form>
<script type="module" src="index.ts"></script>
</body>
</html>
css
html,
body {
font-family: 'Inter', sans-serif;
}
:root {
--base-color: #4999f7;
--active-color: var(--base-color);
--gray: #d9d9d9;
--white: #ffffff;
--lighter-gray: #f4f4f4;
--light-gray: #e6e6e6;
--inactive-color: #cee5ff;
--group-color: #525fe1;
--group-inactive-color: #c2c8ff;
--selection-color: #04ddcb;
--darker-gray: #b6b6b6;
--dark-gray: #555;
--dark-color: #3a3535;
--edge-color: var(--dark-color);
--border-radius: 5px;
--button-border-radius: var(--border-radius);
--edge-inactive-color: var(--light-gray);
--button-background-color: #ffffff;
--shadow-color: rgba(0, 0, 0, 0.25);
--shadow-hover-color: rgba(0, 0, 0, 0.5);
--button-shadow: 0 0 4px var(--shadow-color);
--button-shadow-hover: 0 0 4px var(--shadow-hover-color);
--button-icon-color: #000000;
--button-icon-hover-color: var(--active-color);
}
#graph-container {
top: 0;
bottom: 0;
left: 0;
right: 0;
position: absolute;
margin: 0;
overflow: hidden;
}
.ui {
position: absolute;
display: flex;
flex-direction: column;
gap: 0.5em;
}
#custom-group-btn {
top: 40px;
}
.panel {
background: var(--button-background-color);
border-radius: var(--button-border-radius);
box-shadow: var(--button-shadow);
padding: 10px;
}
.panel {
position: absolute;
top: 1em;
right: 1em;
width: 12em;
padding: 1em;
}
.panel h2 {
text-transform: uppercase;
font-weight: 400;
font-size: 14px;
margin: 0;
margin-bottom: 1em;
}
.panel {
margin-top: 1px;
}
.panel button {
background: var(--button-background-color);
border: none;
border-radius: var(--button-border-radius);
border-color: var(--shadow-color);
padding: 5px 10px;
cursor: pointer;
width: 100%;
color: var(--dark-gray);
border: 1px solid var(--light-gray);
}
.panel button:hover {
background: var(--lighter-gray);
border: 1px solid var(--darker-gray);
}
.panel button[disabled] {
color: var(--light-gray);
border: 1px solid var(--light-gray);
background-color: var(--lighter-gray);
}
#controls p label input {
float: right;
}
#controls p label span {
margin-right: 1em;
}
ts
import { Node, NodeList, NodeId } from '@linkurious/ogma';
// code is adapted from https://github.com/anvaka/ngraph.centrality/ MIT License
export function closeness({
nodes,
oriented = false
}: {
nodes: NodeList;
oriented?: boolean;
}) {
const Q: Node[] = [];
// list of predecessors on shortest paths from source
// distance from source
const dist = new Map<NodeId, number>();
const centrality = nodes.getId().reduce((acc, id) => {
acc.set(id, 0);
return acc;
}, new Map<NodeId, number>());
nodes.forEach(node => {
singleSourceShortestPath(node);
const currentNode = node.getId();
// Add all distances for node to array, excluding -1s
const distances = Array.from(dist.keys())
.map(key => dist.get(key)!)
.filter(val => val !== -1);
// Set number of reachable nodes
const reachableNodesTotal = distances.length;
// Compute sum of all distances for node
const totalDistance = distances.reduce((a, b) => a + b, 0);
if (totalDistance > 0)
centrality.set(currentNode, (reachableNodesTotal - 1) / totalDistance);
else centrality.set(currentNode, 0);
});
function singleSourceShortestPath(source: Node) {
nodes.getId().forEach(id => dist.set(id, -1));
dist.set(source.getId(), 0);
Q.push(source);
while (Q.length) {
const v = Q.shift()!;
v.getAdjacentNodes({ direction: oriented ? 'out' : 'both' }).forEach(
node => {
const w = node.getId();
if (dist.get(w) === -1) {
// Node w is found for the first time
dist.set(w, dist.get(v.getId())! + 1);
Q.push(node);
}
}
);
}
}
return nodes.getId().map(id => centrality.get(id)!);
}
ts
import { NodeList, NodeId } from '@linkurious/ogma';
// code is adapted from https://github.com/anvaka/ngraph.pagerank/ MIT License
interface NodeData {
id: NodeId;
rank: number;
prevRank: number;
indegree: number;
outdegree: number;
neighbors: NodeData[];
}
const nodeData = (initialRank: number, id: NodeId): NodeData => ({
id,
rank: initialRank,
prevRank: initialRank,
indegree: 0,
outdegree: 0,
neighbors: []
});
export function pagerank({
nodes,
internalJumpProbability = 0.85,
epsilon = 0.005
}: {
nodes: NodeList;
internalJumpProbability?: number;
epsilon?: number;
}) {
let done = false; // when done is true, the algorithm is converged
let distance = 0; // distance between two eigenvectors in adjacent timesteps
let leakedRank = 0; // we account leaked rank to solve spider traps and dead ends
const nodesCount = nodes.size;
const nodesData = initializeNodes(nodes);
let currentRank;
let node: NodeData;
do {
leakedRank = 0;
for (let j = 0; j < nodesCount; j++) {
node = nodesData[j];
currentRank = 0;
if (node.indegree === 0) node.rank = 0;
else {
const neighbors = node.neighbors;
for (let i = 0; i < neighbors.length; i++) {
currentRank += neighbors[i].prevRank / neighbors[i].outdegree;
}
node.rank = internalJumpProbability * currentRank;
leakedRank += node.rank;
}
}
// now reinsert the leaked PageRank and compute distance:
leakedRank = (1 - leakedRank) / nodesCount;
distance = 0;
for (let j = 0; j < nodesCount; j++) {
node = nodesData[j];
currentRank = node.rank + leakedRank;
distance += Math.abs(currentRank - node.prevRank);
node.prevRank = currentRank; // set up for the next iteration
}
done = distance < epsilon;
} while (!done);
const idToRank = new Map<NodeId, number>();
for (let j = 0; j < nodesCount; j++) {
node = nodesData[j];
idToRank.set(node.id, node.prevRank);
}
return nodes.map(node => {
const id = node.getId();
return idToRank.get(id)!;
});
}
function initializeNodes(nodes: NodeList) {
const nodesCount = nodes.size;
const initialRank = 1 / nodesCount;
const idToNumber = new Map<NodeId, number>();
const nodesData = nodes.getId().map((id, i) => {
idToNumber.set(id, i);
return nodeData(initialRank, id);
});
nodes.forEach(node => {
const id = node.getId();
const data = nodesData[idToNumber.get(id)!];
let inDegree = 0;
let outDegree = 0;
const neighbors = data.neighbors;
node.getAdjacentEdges().forEach(edge => {
const source = edge.getSource();
const target = edge.getTarget();
if (source === node) outDegree += 1;
else if (target === node) {
inDegree += 1;
neighbors.push(nodesData[idToNumber.get(source.getId())!]);
}
});
data.indegree = inDegree;
data.outdegree = outDegree;
});
return nodesData;
}