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).

index.tsindex.htmlstyles.cssdecomposition.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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377

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;

Onion Decomposition new ​

Onion Decomposition new