Skip to content
  1. Examples

Onion Decomposition new

This example shows how to use the onion decomposition to filter or group the nodes by their "importance" derived from onion decomposition (type of k-core decomposition).

ts
import Ogma, { NodeId, Point } from '@linkurious/ogma';
import decomposition from './decomposition';
import throttle from 'https://cdn.jsdelivr.net/npm/lodash.throttle@4.1.1/+esm';

type ItemId = string | number;

// Create an instance of Ogma and bind it to the graph-container.
const ogma = new Ogma({ container: 'graph-container' });
const graph = await ogma.generate.balancedTree({ height: 5 });
await ogma.setGraph(graph);
await ogma.layouts.force({ duration: 0 });
await ogma.view.locateGraph();

// use onion decomposition (https://www.nature.com/articles/srep31708)
const { layers, maxLayer, parent } = decomposition(graph);
const positions = ogma.getNodes().getPosition();
const ids = ogma.getNodes().getId();
const nodeToPosition = positions.reduce((map, pos, i) => {
  map.set(ids[i], pos);
  return map;
}, new Map<NodeId, { x: number; y: number }>());

///
// Styles
//

/**
 * Compute color based on node layer.
 */
const color = (nodeId: NodeId) => (layers[nodeId] - 1) / (maxLayer - 1);

// color nodes according to their layer
ogma.styles.addRule({
  nodeAttributes: {
    color: node => {
      if (!node) return undefined;
      return node.isVirtual()
        ? '#ccc'
        : `rgb(200, 200, ${255 - Math.round(255 * color(node.getId()))})`;
    },
    radius: node =>
      node && node.isVirtual() ? 20 + Math.sqrt(node.getSubNodes()!.size) : 20
  }
});

///
// Filtering
//

/**
 * Create the layer filtering transformation.
 */

// filter nodes according to their layer
let filterMinLayer = 0;
const layerFiltering = ogma.transformations.addNodeFilter({
  criteria: node => layers[node.getId()] > filterMinLayer,
  duration: 100,
  enabled: false
});

///
// Grouping
//

/**
 * Get ancestor `id` which has the highest layer below `minLayer`.
 */
const getAncestorId = (id: ItemId, minLayer: number): ItemId => {
  const parentId = parent[id]?.id;
  if (parentId === undefined) return id;
  return layers[parentId] > minLayer ? id : getAncestorId(parentId, minLayer);
};

/**
 * Create the layer grouping transformation.
 */
const addLayerGrouping = (getMinLayer: () => number) => {
  ogma.transformations.onGroupsUpdated(topLevelNodes => {
    const positions = topLevelNodes.map(node => {
      if (!node.isVirtual()) return nodeToPosition.get(node.getId())!;
      const subNodes = node.getSubNodes()!;
      const position = subNodes
        .map(n => nodeToPosition.get(n.getId())!)
        .reduce(
          (acc, pos: Point) => {
            acc!.x += pos!.x;
            acc!.y += pos!.y;
            return acc;
          },
          { x: 0, y: 0 } as Point
        )!;
      position.x /= subNodes.size;
      position.y /= subNodes.size;
      return position;
    });
    return Promise.resolve(positions);
  });
  return ogma.transformations.addNodeGrouping({
    groupIdFunction: node => `${getAncestorId(node.getId(), getMinLayer())}`,
    selector: node => layers[node.getId()] <= getMinLayer(),
    nodeGenerator: (subNodes, groupId) => ({
      id: 'layer group ' + groupId,
      data: {
        groupId,
        subNodes
      },
      attributes: {
        icon: '...'
      }
    }),
    enabled: true,
    duration: 200
  });
};

/**
 * Compute minimum layer based on view zoom.
 */
const getMinLayer = () => {
  const z = Math.round(1 / (0.5 * ogma.view.getZoom()));
  return z === 1 ? 0 : z; // grouping layer 1 makes no sense
};

// group nodes according to their layer
const layerGrouping = addLayerGrouping(getMinLayer);

// update the minimum layer to show on zoom change
let lastMinLayer = getMinLayer();
let isRefreshing = false;
const onZoom = throttle(() => {
  if (isRefreshing) return;
  const minLayer = getMinLayer();
  if (lastMinLayer === minLayer) return;
  isRefreshing = true;
  layerGrouping.refresh().then(() => {
    lastMinLayer = minLayer;
    isRefreshing = false;
  });
}, 100);
ogma.events.on('zoom', onZoom);

///
// User Interface
//

const form = document.querySelector<HTMLFormElement>('#ui')!;
const filterSection =
  document.querySelector<HTMLDivElement>('#filter-section')!;
let mode = 'grouping';

let refreshing = false;
/**
 * Reads mode toggle status from the form
 */
const updateUI = async () => {
  if (refreshing) return;
  refreshing = true;
  const select = form['mode-switch'];
  const currentMode = Array.prototype.filter.call(select, function (input) {
    return input.checked;
  })[0].value; // IE inconsistency
  if (currentMode !== mode) {
    layerGrouping.toggle();
    await layerFiltering.toggle();
    refreshing = false;
  }
  if (currentMode === 'filtering') {
    filterMinLayer = parseInt(form['layer'].value);
    filterSection.style.display = 'block';
    await layerFiltering.refresh();
    refreshing = false;
  } else {
    filterSection.style.display = 'none';
    refreshing = false;
  }
  mode = currentMode;
};
updateUI();
// listen for changes on the form
form.addEventListener('input', updateUI);
html
<!doctype html>
<html>
  <head>
    <meta charset="utf-8" />
    <link rel="preconnect" href="https://fonts.googleapis.com" />
    <link rel="preconnect" href="https://fonts.gstatic.com" crossorigin />
    <link
      href="https://fonts.googleapis.com/css2?family=IBM+Plex+Sans:ital,wght@0,100;0,200;0,300;0,400;0,500;0,600;0,700;1,100;1,200;1,300;1,400;1,500;1,600;1,700&display=swap"
      rel="stylesheet"
    />
    <link type="text/css" rel="stylesheet" href="styles.css" />
  </head>
  <body>
    <div id="graph-container"></div>
    <script type="module" src="index.ts"></script>
    <form class="toolbar" id="ui">
      <div class="section mode">
        <div class="switch switch--horizontal">
          <input
            id="graph"
            type="radio"
            name="mode-switch"
            value="grouping"
            checked="checked"
          />
          <label for="graph">Grouping</label>
          <input id="geo" type="radio" name="mode-switch" value="filtering" />
          <label for="geo">Filtering</label>
          <span class="toggle-outside">
            <span class="toggle-inside"></span>
          </span>
        </div>
      </div>
      <div id="filter-section" class="section filter">
        <h3>Filter</h3>
        <p>
          <label for="layer">Layer</label>
          <input type="range" min="0" max="7" value="0" name="layer" step="1" />
        </p>
      </div>
    </form>
  </body>
</html>
css
body {
  margin: 0;
  padding: 0;
  width: 100%;
  height: 100%;
  font-family: 'IBM Plex Sans', Arial, Helvetica, sans-serif;
}

*,
*:before,
*:after {
  box-sizing: border-box;
}

#graph-container {
  top: 0;
  bottom: 0;
  left: 0;
  right: 0;
  position: absolute;
  margin: 0;
  overflow: hidden;
}

.toolbar {
  display: block;
  position: absolute;
  top: 2em;
  right: 2em;
  padding: 1em;
  box-shadow: 0 1px 5px rgba(0, 0, 0, 0.65);
  border-radius: 4px;
  background: #ffffff;
  color: #222222;
  font-weight: 300;
  z-index: 9999;
}

.toolbar .section {
  position: relative;
  display: block;
}

.toolbar .section h3 {
  display: block;
  font-weight: 300;
  border-bottom: 1px solid #ddd;
  color: #606060;
  font-size: 1rem;
}

.toolbar .section .clearable-input {
  border-radius: 4px;
  padding: 5px;
  border: 1px solid #dddddd;
}

.toolbar .section .line-color,
.ogma-tooltip .line-color {
  display: inline-block;
  width: 1rem;
  height: 1rem;
  margin-right: 0.25rem;
  border-radius: 50%;
  color: #ffffff;
  text-align: center;
  font-size: 0.65rem;
  line-height: 1rem;
  font-weight: bold;
  vertical-align: text-top;
}

.toolbar .section .awesomplete > ul {
  max-height: 500px;
  overflow-y: auto;
  width: 350px;
  right: 0;
  left: auto;
  transform-origin: 50% 0;
}

.toolbar .section p {
  padding-left: 18px;
  padding-right: 18px;
}

.toolbar .section p label {
  width: 4rem;
  display: inline-block;
}

.toolbar .mode {
  text-align: center;
}

.toolbar .disabled {
  display: none;
}

.ogma-tooltip-header .title {
  font-weight: bold;
  text-transform: uppercase;
}

#canvas {
  position: absolute;
  top: 0;
  left: 0;
  touch-action: none;
  z-index: -1;
}

/* --- Tooltip */
.ogma-tooltip {
  max-width: 240px;
  max-height: 280px;
  background-color: #fff;
  border: 1px solid #999;
  box-shadow: 0 2px 6px rgba(0, 0, 0, 0.3);
  border-radius: 6px;
  cursor: auto;
  font-size: 12px;
  pointer-events: none;
  z-index: 9999;
}

.ogma-tooltip-header {
  font-variant: small-caps;
  font-size: 120%;
  color: #000;
  border-bottom: 1px solid #999;
  padding: 10px;
}

.ogma-tooltip-body {
  padding: 10px;
  overflow-x: hidden;
  overflow-y: auto;
  max-width: inherit;
  max-height: 180px;
}

.ogma-tooltip-body th {
  color: #999;
  text-align: left;
}

.ogma-tooltip-footer {
  padding: 10px;
  border-top: 1px solid #999;
}

.ogma-tooltip > .arrow {
  border-width: 10px;
  position: absolute;
  display: block;
  width: 0;
  height: 0;
  border-color: transparent;
  border-style: solid;
}

.ogma-tooltip.top {
  margin-top: -12px;
}

.ogma-tooltip.top > .arrow {
  left: 50%;
  bottom: -10px;
  margin-left: -10px;
  border-top-color: #999;
  border-bottom-width: 0;
}

.ogma-tooltip.bottom {
  margin-top: 12px;
}

.ogma-tooltip.bottom > .arrow {
  left: 50%;
  top: -10px;
  margin-left: -10px;
  border-bottom-color: #999;
  border-top-width: 0;
}

.ogma-tooltip.left {
  margin-left: -12px;
}

.ogma-tooltip.left > .arrow {
  top: 50%;
  right: -10px;
  margin-top: -10px;
  border-left-color: #999;
  border-right-width: 0;
}

.ogma-tooltip.right {
  margin-left: 12px;
}

.ogma-tooltip.right > .arrow {
  top: 50%;
  left: -10px;
  margin-top: -10px;
  border-right-color: #999;
  border-left-width: 0;
}

/* -- CSS flip switch */
.switch {
  width: 100%;
  position: relative;
}

.switch input {
  position: absolute;
  top: 0;
  z-index: 2;
  opacity: 0;
  cursor: pointer;
}
.switch input:checked {
  z-index: 1;
}
.switch input:checked + label {
  opacity: 1;
  cursor: default;
}
.switch input:not(:checked) + label:hover {
  opacity: 0.5;
}
.switch label {
  color: #222222;
  opacity: 0.33;
  transition: opacity 0.25s ease;
  cursor: pointer;
}
.switch .toggle-outside {
  height: 100%;
  border-radius: 2rem;
  padding: 0.25rem;
  overflow: hidden;
  transition: 0.25s ease all;
}
.switch .toggle-inside {
  border-radius: 2.5rem;
  background: #4a4a4a;
  position: absolute;
  transition: 0.25s ease all;
}
.switch--horizontal {
  width: 15rem;
  height: 2rem;
  margin: 0 auto;
  font-size: 0;
  margin-bottom: 1rem;
}
.switch--horizontal input {
  height: 2rem;
  width: 5rem;
  left: 5rem;
  margin: 0;
}
.switch--horizontal label {
  font-size: 1rem;
  line-height: 2rem;
  display: inline-block;
  width: 5rem;
  height: 100%;
  margin: 0;
  text-align: center;
}
.switch--horizontal label:last-of-type {
  margin-left: 5rem;
}
.switch--horizontal .toggle-outside {
  background: #dddddd;
  position: absolute;
  width: 5rem;
  left: 5rem;
}
.switch--horizontal .toggle-inside {
  height: 1.5rem;
  width: 1.5rem;
}
.switch--horizontal input:checked ~ .toggle-outside .toggle-inside {
  left: 0.25rem;
}
.switch--horizontal input ~ input:checked ~ .toggle-outside .toggle-inside {
  left: 3.25rem;
}

/* ---- Clearable inputs */
.clearable-input {
  position: relative;
  display: inline-block;
  padding-right: 1.4em;
}
.clearable-input + .clear {
  position: absolute;
  top: 4px;
  right: 4px;
  font-size: 1rem;
  padding: 0;
  line-height: 0.8rem;
  border-radius: 50%;
  background: #dddddd;
  color: #808080;
  cursor: pointer;
  width: 1rem;
  height: 1rem;
  text-align: center;
}

.clearable-input + .clear:hover {
  background: #aaaaaa;
  color: #ffffff;
}

.clearable-input::-ms-clear {
  display: none;
}

.hidden {
  display: none;
}

#options {
  position: absolute;
  top: 350px;
  right: 20px;
  padding: 10px;
  background: white;
  z-index: 400;
  display: none;
}

#options label {
  display: block;
}

#options .controls {
  text-align: center;
  margin-top: 10px;
}

#options .content {
  line-height: 1.5em;
}

.control-bar {
  font-family: Helvetica, Arial, sans-serif;
  box-shadow: 0 1px 5px rgba(0, 0, 0, 0.65);
  border-radius: 4px;
}

.attribution {
  position: absolute;
  right: 0px;
  bottom: 0px;
  padding: 0px;
  z-index: 1000;
  font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;
  font-size: 11px;
  padding: 1px 5px;
  background: rgba(255, 255, 255, 0.7);
}

.hide {
  display: inline;
}

.show {
  display: none;
}
ts
import { RawGraph, RawNode, NodeId } from '@linkurious/ogma';

/**
 * "Multi-scale structure and topological anomaly detection via
 * a new network statistic: The onion decomposition"
 * Laurent Hébert-Dufresne et al 2016 Scientific Reports 6 31708
 *
 * Note:
 * The degree can be turned into weighted degree by adding the edge weight
 * to the degree while accumulating it in the first loop
 */
function decomposition({ nodes, edges }: RawGraph) {
  const layers: Record<NodeId, number> = {};
  const parent: Record<NodeId, RawNode<any>> = {};
  const component: Record<NodeId, number> = {};
  const coreness: Record<NodeId, number> = {};

  let core = 0;
  let layer = 1;
  let maxLayer = 1;

  // degrees
  const idToIndex: Record<NodeId, number> = {};
  for (let i = 0; i < nodes.length; i++) {
    const node = nodes[i];
    idToIndex[node.id!] = i;
  }

  const D = new Uint32Array(nodes.length);
  for (let i = 0; i < edges.length; i++) {
    const edge = edges[i];
    const source = idToIndex[edge.source];
    const target = idToIndex[edge.target];

    // this is very important, cause it's difficult to catch later
    if (source === undefined) {
      throw new Error(`Can't find node '${edge.source}'`);
    } else if (target === undefined) {
      throw new Error(`Can't find node '${edge.target}'`);
    } else {
      D[idToIndex[source]]++;
      D[idToIndex[target]]++;
    }
  }

  // adjacency list
  const A: number[][] = new Array(nodes.length);
  for (let i = 0; i < edges.length; i++) {
    const edge = edges[i];
    const source = idToIndex[edge.source];
    const target = idToIndex[edge.target];
    A[source] = A[source] || [];
    A[target] = A[target] || [];

    A[source].push(target);
    A[target].push(source);
  }

  const visited = new Uint8Array(nodes.length);
  let compId = 0;
  for (let i = 0; i < nodes.length; i++) {
    if (visited[i] === 0) {
      const Q = [i];
      while (Q.length !== 0) {
        const cur = Q.pop()!;
        if (visited[cur] === 0) {
          Q.push.apply(Q, A[cur]);
          visited[cur] = 1;
          component[nodes[cur].id!] = compId;
        }
      }
      compId++;
    }
  }

  // initialize queue
  const V: number[] = new Array(nodes.length);
  for (let i = 0; i < nodes.length; i++) {
    layers[nodes[i].id!] = 0;
    V[i] = i;
  }

  while (V.length !== 0) {
    // positions of the layer nodes in the nodes array
    const indexes = [];
    const Vc = [];

    // select nodes by degree
    for (let i = 0; i < V.length; i++) {
      if (D[V[i]] <= core) {
        indexes.push(i);
        Vc.push(V[i]);
      }
    }

    // assign layer and coreness
    for (let i = 0; i < Vc.length; i++) {
      const v = nodes[Vc[i]];
      const vid = v.id!;
      coreness[vid] = core;
      layers[vid] = layer;

      // remove
      const adjacent = A[Vc[i]];
      if (adjacent) for (let j = 0; j < adjacent.length; j++) D[adjacent[j]]--;
    }

    for (let i = 0; i < Vc.length; i++) {
      const v = nodes[Vc[i]];
      const adjacent = A[Vc[i]];
      if (adjacent) {
        for (let j = 0; j < adjacent.length; j++) {
          const adj = adjacent[j];
          const alayer = layers[nodes[adj].id!];
          if (alayer === undefined || alayer > layer) {
            parent[v.id!] = nodes[adj];
            break;
          }
        }
      }
    }

    // remove layer nodes from nodes array
    indexes.reverse(); // reverse order not to mess up indexes with .splice()
    for (let i = 0; i < indexes.length; i++) V.splice(indexes[i], 1);

    layer += 1;
    if (maxLayer < layer) maxLayer = layer;

    if (V.length > 0) {
      let minDegree = Infinity;
      for (let i = 0; i < V.length; i++) {
        const degree = D[V[i]];
        if (degree < minDegree) minDegree = degree;
      }

      if (minDegree >= core + 1) {
        core = minDegree;
        layer = 1;
      }
    }
  }

  // parent node correction
  for (let i = 0; i < nodes.length; i++) {
    const node = nodes[i];
    const nodeId = node.id!;
    const layer = layers[nodeId];
    if (parent[nodeId] === undefined || layers[parent[nodeId].id!] === layer) {
      const Q = [idToIndex[node.id!]];
      for (let k = 0; k < nodes.length; k++) visited[k] = 0;
      while (Q.length !== 0) {
        const id = Q.pop()!;
        if (visited[id]) continue; // avoid loops
        if (layers[nodes[id].id!] > layer) {
          parent[nodeId] = nodes[id];
          break;
        }
        const adjacent = A[id];
        visited[id] = 1;
        if (adjacent) Q.push.apply(Q, adjacent);
      }
    }
  }

  return { layers, maxLayer, parent, component, coreness };
}

export default decomposition;