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