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.

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;
}

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)!);
}

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;
}

Other centrality measures ​

Other centrality measures